Re: [Caml-list] Efficient scanning of large strings from files

[Philippe Veber <philippe.veber@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2262 bytes --]

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örök Edwin <edwin+ml-ocaml@etorok.net>

> On 03/16/2012 04:49 PM, Jérémie Dimino wrote:
> > Le Fri, 16 Mar 2012 14:03:38 +0100,
> > Philippe Veber <philippe.veber@gmail.com> a écrit :
> >
> >> 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érôme 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
>
>

[-- Attachment #2: Type: text/html, Size: 3398 bytes --]