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. _______________________________________________ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "[EMAIL PROTECTED]"
