Olivier Danvy and
Henning Korsholm Rohde:
On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation.
Information Processing Letters 99(4)158-162 (August
2006). Elsevier B.V.
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.
|
|
[dvi,ps,pdf]
|
Published versions
|
|
|
- Journal version (August 2006). © Elsevier B.V.
|
[dvi,ps,pdf]
|
|
- Technical
report BRICS-RS-05-29,
University of Aarhus, Denmark (August 2005).
|
[dvi,ps,pdf]
|
|
- Technical
report BRICS-RS-05-14,
University of Aarhus, Denmark (April 2005). Obsolete.
|
[dvi,ps,pdf]
|