Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427737 | Information Processing Letters | 2012 | 5 Pages |
Abstract
Many efficient string matching algorithms make use of q-grams and process the text in windows which are read backward. In this paper we provide a framework for analyzing the average case complexity of these algorithms taking into account the statistical dependencies between overlapping q-grams. We apply this to the q-gram Boyer–Moore–Horspool algorithm adapted to various string matching problems and show that the algorithm is optimal on average.
► We study the average case complexity of string matching algorithms that use q-grams. ► We take into account the statistical dependencies of overlapping q-grams. ► We show that q-gram Boyer–Moore–Horspool style algorithms are average optimal.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Leena Salmela,