Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| Is there a paper which merges the Aho-Corasik and Boyer-Moore algorith cfc@shell01.TheWorld.com (Chris F Clark) (2006-09-16) |
| Re: Is there a paper which merges the Aho-Corasik and Boyer-Moore algo bonzini@gnu.org (Paolo Bonzini) (2006-09-18) |
| Re: Is there a paper which merges the Aho-Corasik and Boyer-Moore algo gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-09-18) |
| Re: Is there a paper which merges the Aho-Corasik and Boyer-Moore algo henry@spsystems.net (2006-09-21) |
| Re: Is there a paper which merges the Aho-Corasik and Boyer-Moore algo bonzini@gnu.org (Paolo Bonzini) (2006-09-21) |
| Re: Is there a paper which merges the Aho-Corasik and Boyer-Moore algo cfc@shell01.TheWorld.com (Chris F Clark) (2006-09-21) |
| Re: Is there a paper which merges the Aho-Corasik and Boyer-Moore algo loekcleophas@gmail.com (loekcleophas@gmail.com) (2006-09-30) |
| From: | "Paolo Bonzini" <bonzini@gnu.org> |
| Newsgroups: | comp.compilers |
| Date: | 18 Sep 2006 09:48:53 -0400 |
| Organization: | Compilers Central |
| References: | 06-09-089 |
| Keywords: | theory |
| Posted-Date: | 18 Sep 2006 09:48:53 EDT |
> Specifically, I've been working on string matching problems recently,
> and thus the classic Aho-Corasik (AC) and Boyer-Moore (BM) algorithms.
> In addition, I've known for a "long time" that the trick of working
> backwards ala BM could be applied to a AC style matcher to obtain the
> same potential sub-linear performance.
I think GNU fgrep is doing something very similar.
The source code is at
http://cvs.savannah.gnu.org/viewcvs/grep/src/kwset.c?rev=HEAD&root=grep&view=markup
and it cites "A String Matching Algorithm Fast on the Average,"
Technical Report, IBM-Germany, Scientific Center Heidelberg,
Tiergartenstrasse 15, D-6900 Heidelberg, Germany. This paper is
available through Springer.
Paolo
Return to the
comp.compilers page.
Search the
comp.compilers archives again.