Revisiting Multiple Pattern Matching
DOI:
https://doi.org/10.31577/cai_2019_4_937Keywords:
Text algorithms, pattern matching, multiple pattern matching, q-grams, bit-parallelism, compressed pattern matchingAbstract
We consider the classical exact multiple string matching problem. The proposed solution is based on a combination of a few ideas: using q-grams instead of single characters, pattern superimposition, bit-parallelism and alphabet size reduction. We discuss the pros and cons of various alternatives to achieve the possibly best combination of techniques. The main contribution of this paper are different alphabet mapping methods that allow to reduce memory requirements and use larger q-grams. The experimental results show that the presented algorithm is competitive in most practical cases. One of the tests shows also that tailoring our scheme to search over a byte-encoded text results in speedups in comparison to searching over a plain text.Downloads
Download data is not yet available.
Downloads
Published
2019-12-30
How to Cite
Susik, R., Grabowski, S., & Fredriksson, K. (2019). Revisiting Multiple Pattern Matching. Computing and Informatics, 38(4), 937–962. https://doi.org/10.31577/cai_2019_4_937
Issue
Section
Articles