|
On Obtaining the Boyer-Moore String-Matching Algorithm by Partial
Evaluation
Olivier Danvy
April 2005 |
Abstract:
We present the first derivation of the search phase of the
Boyer-Moore string-matching algorithm by partial evaluation of an inefficient
string matcher. The derivation hinges on identifying the
`bad-character-shift' heuristic as a binding-time improvement, bounded static
variation. An inefficient string matcher incorporating this binding-time
improvement specializes into the search phase of the Horspool algorithm,
which is a simplified variant of the Boyer-Moore algorithm. Combining the
bad-character-shift binding-time improvement with our previous results yields
a new binding-time-improved string matcher that specializes into the search
phase of the Boyer-Moore algorithm
Available as PostScript, PDF, DVI. |