Since 2014
On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation
|
|
| Creator |
Danvy, Olivier
Rohde, Henning Korsholm |
|
| Description |
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.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
2005-04-11
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/21880
10.7146/brics.v12i14.21880 |
|
| Source |
BRICS Report Series; No 14 (2005): RS-14 On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation
BRICS Report Series; No 14 (2005): RS-14 On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/21880/19307
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|