From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q2J9CEeG019365 for ; Mon, 19 Mar 2012 10:12:15 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvcDAAL4Zk/RVdy2mGdsb2JhbABDpH40iCQBiGoIIgEBAQEBCAkNBxQnggkBAQECAQEMBgIsARsSCwEDAQsGBQsNDSEhAQERAQUBChIGExIQh2MFC5xECowSgnGENj+IdAEFC4lKhycEkjqDLosvgxo9hAk X-IronPort-AV: E=Sophos;i="4.73,611,1325458800"; d="scan'208";a="136707000" Received: from mail-vx0-f182.google.com ([209.85.220.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 19 Mar 2012 10:12:13 +0100 Received: by vcmm1 with SMTP id m1so12004242vcm.27 for ; Mon, 19 Mar 2012 02:12:11 -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=KGMqlbzJ9+P7YlEfpxJA9tgRRYbgPo1WI61H/SuvxWc=; b=r5YHNVKDdW/qMMO47/4+I0EkO/6T0AX4jxdUiw7BlxRv6FtwO0ayrIMfMTuOJZwHtw GlK6voJTsRsg9hpdZ9wJMRVBCb/lRsBqIrB42xHq+cx70sluS+HNONlGlEHg2JVBITQM lHfyXSDtxTSrgSPGXyz1ruTpNLF/k0ItRnjXJleRwPF9Q9nrS4dBU2XwYoMeimDYVbNO ekDEnxqQrRakSA5VKRW3M7mqJQnYOy8S1k30Ed0TtVT3pEX+Cokl0QTRP3mWFuYyv6fu ODt5MMVMUQWcXVudpnJBvRDA0pgoDQPV2lrASxCaz3tvulzX0Y1+ZtQi2xrVm2a5t26B snbQ== Received: by 10.52.70.2 with SMTP id i2mr5004359vdu.54.1332148331832; Mon, 19 Mar 2012 02:12:11 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.31.136 with HTTP; Mon, 19 Mar 2012 02:11:51 -0700 (PDT) In-Reply-To: <4F664F7B.6020405@etorok.net> References: <20120316154901.76602deb@caladan.esterel-technologies.com> <4F664F7B.6020405@etorok.net> From: Philippe Veber Date: Mon, 19 Mar 2012 10:11:51 +0100 Message-ID: To: =?ISO-8859-1?Q?T=F6r=F6k_Edwin?= Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=20cf307f39901b66af04bb94f460 X-Validation-by: philippe.veber@gmail.com Subject: Re: [Caml-list] Efficient scanning of large strings from files --20cf307f39901b66af04bb94f460 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Thanks Edwin and Oliver, I wasn't aware of these libraries. I'll definitely have a look. Thanks again everybody for your help on this! ph. 2012/3/18 T=F6r=F6k Edwin > On 03/16/2012 04:49 PM, J=E9r=E9mie Dimino wrote: > > Le Fri, 16 Mar 2012 14:03:38 +0100, > > Philippe Veber a =E9crit : > > > >> 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, > > > > You can use a non-backtracking regexp library to find offsets of the > > substrings, then seek in the file to extract them. You can use for > > example the libre library from J=E9r=F4me Vouillon [1]. It only accept > > strings as input but it would be really easy to make it work on input > > channels (just replace "s.[pos]" by "input_char ic"). > > > > [1] http://sourceforge.net/projects/libre/ > > https://github.com/avsm/ocaml-re.git > > > > A nice library for regular expression matching is LibTRE (BSD licensed), > and it has a way to parse arbitrary data with callbacks: > http://laurikari.net/tre/documentation/reguexec/ > > According to the paper it is also good at finding substring matches > with its tagged NFA: > http://laurikari.net/ville/regex-submatch.pdf > > If you don't use back-references (!tre_have_backrefs) then it guarantees > linear-time matching. > > I couldn't find an OCaml wrapper for it, but should be simple enough to > write one. > > Best regards, > --Edwin > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > > --20cf307f39901b66af04bb94f460 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Thanks Edwin and Oliver, I wasn't aware of these libraries. I'll de= finitely have a look.
Thanks again everybody for your help on this!
p= h.

2012/3/18 T=F6r=F6k Edwin <edwin+ml-ocaml@eto= rok.net>
On 0= 3/16/2012 04:49 PM, J=E9r=E9mie Dimino wrote:
> Le Fri, 16 Mar 2012 14:03:38 +0100,
> Philippe Veber <philipp= e.veber@gmail.com> a =E9crit :
>
>> 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 b= ound
>> 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<= br> >> regexp. Typically you'd like to access substrings of size k fr= om left
>> to right. I guess such a thing should involve buffered inputs and<= br> >> avoid copying strings as much as possible. My question is as follo= ws:
>> has anybody written a library to access these substrings gracefull= y
>> and with decent performance? Cheers,
>
> You can use a non-backtracking regexp library to find offsets of the > substrings, then seek in the file to extract them. You can use for
> example the libre library from J=E9r=F4me Vouillon [1]. It only accept=
> strings as input but it would be really easy to make it work on input<= br> > channels (just replace "s.[pos]" by "input_char ic"= ;).
>
> =A0 [1] http://sourceforge.net/projects/libre/
> =A0 =A0 =A0 https://github.com/avsm/ocaml-re.git
>

A nice library for regular expression matching is LibTRE (BSD l= icensed),
and it has a way to parse arbitrary data with callbacks:
http://laurikari.net/tre/documentation/reguexec/

According to the paper it is also good at finding substring matches
with its tagged NFA:
http://laurikari.net/ville/regex-submatch.pdf

If you don't use back-references (!tre_have_backrefs) then it guarantee= s linear-time matching.

I couldn't find an OCaml wrapper for it, but should be simple enough to= write one.

Best regards,
--Edwin

--
Caml-list mailing list. =A0Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs


--20cf307f39901b66af04bb94f460--