Replacing GNU grep revisited

[David Schultz]

On Wed, Jun 25, 2003, Sean Farley wrote:
> On Wed, 25 Jun 2003, Christopher Weimann wrote:
> 
> > There is at least one aspect of freegrep that doesn't even come
> > close to GNU grep, fgrep.
> 
> I just added fgrep handling.  It better be slower. :)  At least it will
> now try a faster method on the patterns before hitting the regex
> library.  It is still slow.
> 
> > I ran both of these more than once so it is not a fluke.  After
> > looking at it further it seems that freegrep does not use the
> > Aho-Corasick algorithim for fgrep but just uses brute force.
> 
> Yes, it uses brute force.  I am considering either Aho-Corasick,
> Commentz-Walter (used in GNU fgrep) or the Boyer-Moore variation used in
> Glimpse and an older agrep.  The last algorithm is supposedly the
> fastest, but I do not know if these algorithms are patent-free or not.

Cool!  I didn't realize you were so into this...

The only good string matching algorithm I actually understand is
KMP, but really smart people tell me Boyer-Moore is the fastest in
the average case.  It *can* be worse than KMP, depending on the
input, but for nearly all inputs it supposedly works quite well.
There shouldn't be any patent issues associated with it.