Title | ||
---|---|---|
A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms |
Abstract | ||
---|---|---|
A new taxonomy of sublinear (multiple) keyword pattern matching algorithms is presented. Based on an earlier taxonomy by the second and third authors, this new taxonomy includes not only suffix-based algorithms, but also factor- and factor-oracle-based algorithms. In particular, we show how suffix-based (Commentz-Walter like), factor- and factor-oracle-based sublinear keyword pattern matching algorithms can be seen as instantiations of a general sublinear algorithm skeleton. During processing, such algorithms shift or jump through the text in a forward or left-to-right direction, and read backward or right-to-left starting from positions in the text, i.e. they read suffixes of certain prefixes of the text. They use finite automata for efficient computation of string membership in a certain language. In addition, we show shift functions defined for the suffix-based algorithms to be reusable for factor- and factor-oracle-based algorithms. The taxonomy is based on deriving the algorithms from a common starting point by adding algorithm and problem details, to arrive at efficient or well-known algorithms. Such a presentation provides correctness arguments for the algorithms as well as clarity on how the algorithms are related to one another. In addition, it is helpful in the construction of a toolkit of the algorithms. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.scico.2010.04.012 | Sci. Comput. Program. |
Keywords | Field | DocType |
pattern matching,finite automata | Sublinear function,Suffix,Computer science,Correctness,Algorithm,Finite-state machine,Theoretical computer science,Prefix,Probabilistic analysis of algorithms,Pattern matching,Computation | Journal |
Volume | Issue | ISSN |
75 | 11 | 0167-6423 |
Citations | PageRank | References |
7 | 0.67 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Loek G. Cleophas | 1 | 45 | 11.31 |
Bruce W. Watson | 2 | 338 | 53.24 |
Gerard Zwaan | 3 | 19 | 4.58 |