Re: Is there a paper which merges the Aho-Corasik and Boyer-Moore algorithms?

"Paolo Bonzini" <bonzini@gnu.org>
18 Sep 2006 09:48:53 -0400

          From comp.compilers

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)
| List of all articles for this month |

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


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.