From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q2GEnABS003174 for ; Fri, 16 Mar 2012 15:49:10 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnUCAKtRY0/RVdy2mGdsb2JhbABCti8IIgEBAQEBCAkNBxQnggkBAQEDARICLAEbHQEDAQsGBQQHAwouIQEBEQEFARwGEyKHYwWcKwqMEoJxhSg/iHQBBQuJSF6GTASSL4M3iy6DGj2ECYFb X-IronPort-AV: E=Sophos;i="4.73,598,1325458800"; d="scan'208";a="149797702" Received: from mail-vx0-f182.google.com ([209.85.220.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 16 Mar 2012 15:49:06 +0100 Received: by vcmm1 with SMTP id m1so8517815vcm.27 for ; Fri, 16 Mar 2012 07:49:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=Ud4W9htIN4auQ/4ypw2SVlPp9m3eaQVeGgiuQ6z4yrY=; b=TVMNY5JvIoYm1dpXOpjift7VI/fw5k29f4oC4HMRDT3/vHA4wbZs7Wcy8k3i48Yn5p UlxHqLEqcpWWA1QDEgDtQdSAjMfzyq3nUYA6bmQXvLJz/EK+u2VxcbOLWZZWuMUEjs6G kDdbl7+iv9Izx2vrJZ75WfDJr09y81zaxLqZeAXatcdGL9OwhI3GnuZvgE6sjSb0oY7v QMMRgXc3VLZ2B4krSrk8GVbZUzZjOgs4Uz+wK/WwyUZc9bps/z9D5JHDFMkEUDDo5RuL gXvx3shdDXs4dG9x00o7DDNNdYg6eiIngsaf35ABsXNEbNP61hoY/wQEFUZEs7APhcy8 lDeA== Received: by 10.220.148.139 with SMTP id p11mr421254vcv.48.1331909345833; Fri, 16 Mar 2012 07:49:05 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.31.136 with HTTP; Fri, 16 Mar 2012 07:48:45 -0700 (PDT) In-Reply-To: <4F634AD1.20402@gmail.com> References: <4F634AD1.20402@gmail.com> From: Philippe Veber Date: Fri, 16 Mar 2012 15:48:45 +0100 Message-ID: To: Edgar Friendly Cc: "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=f46d042f90466e736d04bb5d4f2c X-Validation-by: philippe.veber@gmail.com Subject: Re: [Caml-list] Efficient scanning of large strings from files --f46d042f90466e736d04bb5d4f2c Content-Type: text/plain; charset=ISO-8859-1 2012/3/16 Edgar Friendly > On 03/16/2012 09:03 AM, Philippe Veber wrote: > >> Dear camlers, >> >> Say that you'd like to search a regexp on a file with lines so long that >> you'd rather not load them entirely at once. If you can bound the size >> of a match by k << length of a line, then you know that you can only >> keep a small portion of the line in memory to search the regexp. >> Typically you'd like to access substrings of size k from left to right. >> I guess such a thing should involve buffered inputs and avoid copying >> strings as much as possible. My question is as follows: has anybody >> written a library to access these substrings gracefully and with decent >> performance? >> Cheers, >> Philippe. >> >> This is tricky to do, as incremental matching implies DFA-based > matching, but returning matching substrings implies backtrack-based > matching. The re2 library returns matching substrings by matching forward > to find the end of patterns, and then matching backwards on the reversed > regex from that point to find their beginning. I don't know if even it > supports this on incremental input. > > Subject to the assumption that starting to match implies either finishing > or aborting a match (i.e. once you've started to match your regex, no other > match will start before either this match attempt finishes successful or > not), this is not unreasonable to do. Without this assumption, it requires > tracking many match start locations and somehow knowing which of them match > or fail to match. I'm not sure this has been done before. > > E. > Thank you Edgar for your answer (and also Christophe). It seems my question was a bit misleading: actually I target a subset of regexps whose matching is really trivial, so this is no worry for me. I was more interested in how accessing a large line in a file by chunks of fixed length k. For instance how to build a [Substring.t Enum.t] from some line in a file, without building the whole line in memory. This enum would yield the substrings (0,k-1), (1,k), (2,k+1), etc ... without doing too many string copy/concat operations. I think I can do it myself but I'm not too confident regarding good practices on buffered reads of files. Maybe there are some good examples in Batteries? Thanks again, ph. --f46d042f90466e736d04bb5d4f2c Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

2012/3/16 Edgar Friendly <thelema314@gmail.com>=
On 03/16/2012 09:03 AM, Philippe Ve= ber wrote:
Dear camlers,

Say that you'd like to search a regexp on a file with lines so long tha= t
you'd rather not load them entirely at once. If you can bound the size<= br> of a match by k << length of a line, then you know that you can only<= br> keep a small portion of the line in memory to search the regexp.
Typically you'd like to access substrings of size k from left to right.=
I guess such a thing should involve buffered inputs and avoid copying
strings as much as possible. My question is as follows: has anybody
written a library to access these substrings gracefully and with decent
performance?
Cheers,
=A0 Philippe.

This is tricky to do, as incremental matching implies DFA-based matching, b= ut returning matching substrings implies backtrack-based matching. =A0The r= e2 library returns matching substrings by matching forward to find the end = of patterns, and then matching backwards on the reversed regex from that po= int to find their beginning. =A0I don't know if even it supports this o= n incremental input.

Subject to the assumption that starting to match implies either finishing o= r aborting a match (i.e. once you've started to match your regex, no ot= her match will start before either this match attempt finishes successful o= r not), this is not unreasonable to do. =A0Without this assumption, it requ= ires tracking many match start locations and somehow knowing which of them = match or fail to match. =A0I'm not sure this has been done before.

E.
Thank you Edgar for your answer (and also = Christophe). It seems my question was a bit misleading: actually I target a= subset of regexps whose matching is really trivial, so this is no worry fo= r me. I was more interested in how accessing a large line in a file by chun= ks of fixed length k. For instance how to build a [Substring.t Enum.t] from= some line in a file, without building the whole line in memory. This enum = would yield the substrings (0,k-1), (1,k), (2,k+1), etc ... without doing t= oo many string copy/concat operations. I think I can do it myself but I'= ;m not too confident regarding good practices on buffered reads of files. M= aybe there are some good examples in Batteries?

Thanks again,
=A0 ph.


--f46d042f90466e736d04bb5d4f2c--