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.
>