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

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)
------------------------------------------------------------------------------

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