Revisiting Multiple Pattern Matching

Year, pages: 2020, 937 - 962

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.

Susik, R., Grabowski, S., Fredriksson, K. 2020. Revisiting Multiple Pattern Matching. In Computing and Informatics, vol. 38, no.4, pp. 937-962. 1335-9150. DOI: https://doi.org/10.31577/cai_2019_4_937

Susik, R., Grabowski, S., Fredriksson, K. (2020). Revisiting Multiple Pattern Matching. Computing and Informatics, 38(4), 937-962. 1335-9150. DOI: https://doi.org/10.31577/cai_2019_4_937

Publisher: Ústav informatiky SAV