Revisiting Multiple Pattern Matching

Authors

  • Robert Susik Institute of Applied Computer Science, Lodz University of Technology, 90 924 Lódź, Poland
  • Szymon Grabowski Institute of Applied Computer Science, Lodz University of Technology, 90 924 Lódź, Poland
  • Kimmo Fredriksson School of Computing, University of Eastern Finland, FI-70211 Kuopio, Finland

DOI:

https://doi.org/10.31577/cai_2019_4_937

Keywords:

Text algorithms, pattern matching, multiple pattern matching, q-grams, bit-parallelism, compressed pattern matching

Abstract

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