Date: Wed, 25 Jun 2003 23:43:50 -0700 From: David Schultz <das@FreeBSD.ORG> To: Sean Farley <sean-freebsd@farley.org> Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: Replacing GNU grep revisited Message-ID: <20030626064350.GB94891@HAL9000.homeunix.com> In-Reply-To: <20030625132648.J72955@thor.farley.org> References: <20030621103502.K18572@thor.farley.org> <20030625000344.A54424@smtp.k12us.com> <20030625132648.J72955@thor.farley.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030626064350.GB94891>