21 Sep 2006 10:32:09 -0400

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: | henry@spsystems.net (Henry Spencer) |

Newsgroups: | comp.compilers,comp.theory |

Date: | 21 Sep 2006 10:32:09 -0400 |

Organization: | SP Systems, Toronto, Canada |

References: | 06-09-089 |

Keywords: | theory |

Chris F Clark <cfc@shell01.TheWorld.com> wrote:

*>...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..*

*>Still, it seems to me to be an obvious thing to do, so I would be*

*>surprised if someone else hasn't already solved this problem...*

It's the Commentz-Walter algorithm, published (although rather obscurely)

in 1979. CW is to AC as BM is to Knuth-Morris-Pratt, roughly speaking, a

backwards-first optimization. Or alternatively :-), CW is to BM as AC is

to KMP, a multi-string generalization.

Commentz-Walter, B., "A string matching algorithm fast on the average",

in Maurer ed., Proc 6th Internat. Coll. on Automata, Languages, and

Programming, Springer-Verlag 1979, pp118-132. The inaccessibility of this

paper (and the internal IBM Germany tech report it was based on) are a

large part of why CW is little known.

I'm tempted to say that a more accessible description is findable in

Crochemore&Rytter, "Text Algorithms", Oxford 1994, but I won't :-),

because that book is a nightmare to read -- in particular, it is riddled

with really nasty typos that make it very difficult to follow the more

subtle algorithms unless you already know what's going on.

Bruce Watson's 1995 Eindhoven PhD thesis, "Taxonomies and Toolkits of

Regular Language Algorithms", is a much more readable and far more

definitive reference -- including extensions of BM to full regular

expressions -- but as far as I know, it suffers from the same problem of

relative inaccessibility.

There is reportedly a good description of CW in Aho's chapter in

van Leeuwen ed., "Handbook of Theoretical Computer Science", vol. A,

but I have not checked this.

--

spsystems.net is temporarily off the air; | Henry Spencer

mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.