Multiple keyword pattern matching using position encoded pattern lattices
Fritz Venter, Bruce W. Watson, Derrick G. Kourie · 2012
Abstract. Formal concept analysis is used as the basis for two new multiplekeywordstringpatternmatchingalgorithms. Thealgorithms addressedarebuiltuponaso-called position encoded pattern lattice (PEPL). The algorithms presented are in conceptual form only; no experimental results are given. The first algorithm to be presented is easily understood and relies directly on the PEPL for matching. Its worst case complexity depends on both the length of the longest keyword, and the length of the search text. Subsequently a finite-automaton-like structure, called a PEPL automaton, is defined which is derived from the PEPL, and which forms the basis for a second more efficient algorithm. In this case, worst case behaviour depends only on the length of the input stream. The second algorithm’s worst case performance is the same as the matching phase of the well-known (advanced) Aho-Corasick multiple-keyword pattern matching algorithm—widely regarded as the multiple keyword pattern matching algorithm of choice in contexts such as network intrusion detection. The first algorithm’s performance is comparable to that of the matching phase of the lesser-known failure-function version of Aho-Corasick.