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

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

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

Yes indeed!

2012/3/16 Francois????Charles Matthieu????Berenger <Berenger@riken.jp>

> ｈｉ philippe,
>
> i am curious, is your string a dna sequencｅｓｏ ｔｈａｔ ｓ ｗｈｙ ｉｔ ｉｓ ｓｏ ｌｏｎｇ？
>
> ｒｅｇａｒｄｓ，ｆ
>
>
> On Fri, 16 Mar 2012 10:14:41 -0400
> Edgar Friendly <thelema314@gmail.com> wrote:
>
> > 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.
> >
> > --
> > 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: 3210 bytes --]