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

> > I think GNU fgrep is doing something very similar.
>
> As well as I remember, the GNU grep use BM on the longest
> fixed string in the query, and then apply the regexp once that
> is found. For the large number of grep patterns that are fixed
> strings, this is especially useful. I haven't looked at the -F
> option, though.


GNU grep has three matchers and uses them in this order:
- kwset.c (used to find the longest fixed string, or alone for -F)
- DFA
- NFA (used to confirm a match, when backreferences are used)


kwset.c implements both Boyer-Moore and Commentz-Walter string
searches. The former is used when there is a single search, the latter
if there are many of them. In practice, when you use "-e" it will use
Commentz-Walter:


    grep -e foo.*x -e bar.*yz


will use Commentz-Walter to look for a line having "foo" or "bar" (the
longest fixed string in the two regex foo.*x and bar.*yz), then confirm
the match with a DFA. Instead,


    fgrep foo
    fgrep -e foo -e bar


will only need a Boyer-Moore or Commentz-Walter search, respectively.


Paolo

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