Quote: average case for 2 string matching algorithms, Boyer-Moore-Horspool faster than hardware character match for most pattern lengths

topics > all references > references a-b > QuoteRef: baezRA8_1989 , p. abstract

pattern matching
search algorithms

Quotation Skeleton

We present bounds for the average case of … random and English text suggests that the bounds … which, in practice, is faster than the Boyer-Moore … [p. 76] Horspool in 1980 [Software Practice and Experience] presented a simpler … Moreover, the same results show that this algorithm … character, for almost all pattern lengths. [p. 89: The variant has better worst case performance than BMH, fewer comparisons on average than the KMP algorithm, and simpler preprocessing than BM, in practice it is slightly faster than BMH].   Google-1   Google-2

Copyright clearance needed for quotation.

Additional Titles

Quote: string-matching variant combines Knuth-Morris-Pratt (fewer comparisons) and Boyer-Moore-Horspool (better in worst case and preprocessing)

Related Topics up

Topic: pattern matching (42 items)
Topic: search algorithms (40 items)

Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.