16 Sep 2006 15:59:22 -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: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers,comp.theory |

Followup-To: | comp.compilers |

Date: | 16 Sep 2006 15:59:22 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

Keywords: | question, theory |

Posted-Date: | 16 Sep 2006 15:59:22 EDT |

Technically, this isn't strictly a compilers question, but since it is

close enough and it is the group I read most, I asked there first.

I've Googled on the topic and haven't seen such a paper, but it is

likely that it could exist and I just didn't recognize it from the

title.

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've never pursued this idea

because for my main work (lexing and parsing), one has to look at

every character anyway, so the speedup was irrelevant. However, I now

have an actual string search problem to solve and the other night I

worked out the rough details of combining the two algorithms.

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 and

published a solution (and possibly solved it better than my rough

idea). No point reinventing the wheel if someone else already has,

especially if they also invented ball bearings and universal joints

too.

So, if someone could point me to some relevant papers, it would be

much appreciated.

Thanks,

-Chris

*****************************************************************************

Chris Clark Internet : compres@world.std.com

Compiler Resources, Inc. Web Site : http://world.std.com/~compres

23 Bailey Rd voice : (508) 435-5016

Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.