Date: Mon, 23 Aug 2010 10:12:12 +0200 From: =?utf-8?Q?Dag-Erling_Sm=C3=B8rgrav?= <des@des.no> To: Mike Haertel <mike@ducky.net> Cc: freebsd-current@freebsd.org, gabor@freebsd.org Subject: Re: why GNU grep is fast Message-ID: <867hjhzr1f.fsf@ds4.des.no> In-Reply-To: <201008222211.o7MMBeC8065026@ducky.net> (Mike Haertel's message of "Sun, 22 Aug 2010 15:11:40 -0700") References: <201008210231.o7L2VRvI031700@ducky.net> <86k4nikglg.fsf@ds4.des.no> <201008221822.o7MIMCRN050408@ducky.net> <86lj7yl6n6.fsf@ds4.des.no> <201008222211.o7MMBeC8065026@ducky.net>
next in thread | previous in thread | raw e-mail | index | archive | help
Mike Haertel <mike@ducky.net> writes: > Dag-Erling Sm=C3=B8rgrav <des@des.no> writes: > > You don't really need to "isolate the containing line" unless you have > > an actual match, do you? > Theoretically no. However, suppose the pattern was /foo.*blah/. > The Boyer-Moore search will be for "blah", since that's the longest > fixed substring. But verifying a match for the full regexp either > requires a regexp matcher with the feature "start here, at THIS point > in the middle of the RE and THAT point in the middle of the buffer, > and match backwards and forwards", or else running a more standard > RE matcher starting from the beginning of the line. Stupidly enough, I only considered the case where the fixed search string is at the end of the regexp :) For the general case, you'd have to either build a second FSA that mirrors the first, or design your engine and data structures in such a way that the FSA can be traversed in either direction. Then you note which states correspond to the beginning and end of the fixed substring, and run the FSA forward from the end and backward from the beginning. That could prove advantageous when the input consists of very long lines and the frequency of partial matches is relatively high; large files with very long lines are very common in bioinformatics. > As you mentioned, you can avoid searching forwards for the next > newline if your RE matcher supports using newline as an exit marker. Umm, I don't understand why it needs to support using *anything* as an exit marker. The newline character will simply not match any of the transitions from whichever state the FSA is currently in, and neither will the null character. The only bit that needs to know about them is the bit that handles end-of-line and end-of-word anchors. DES --=20 Dag-Erling Sm=C3=B8rgrav - des@des.no
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?867hjhzr1f.fsf>