Formal concept analysis is used as the basis for two new multiple keyword string pattern matching algorithms. The algorithms addressed are built upon a so-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.
The (multiple) keyword pattern matching problem (in which the patterns are
finite strings, or ‘keywords’) consists of finding all occurrences (including
overlapping ones) of the keywords within an input string. Typically, the input string
is much larger than the set of keywords and the set of keywords are fixed,
meaning they can be preprocessed to produce data-structures for later use while
processing the input string. We also make these assumptions in this paper, as this
problem variant corresponds to many real-life applications in security,
computational biology, etc [
In this text, the idea of “position encoding” of a set of patterns is introduced.
This strategy serves as an alternative to traditional algorithms used to match
c 2012 by the paper authors. CLA 2012, pp. 281–292. Copying permitted only for
private and academic purposes. Volume published and copyrighted by its editors.
Local Proceedings in ISBN 978–84–695–5252–0,
Universidad de M´alaga (Dept. Matem´atica Aplicada), Spain.
a set of patterns. These algorithms typically rely on common pattern prefixes,
suffixes and/or factors in general. The Aho-Corasick [
Formal concept analysis (FCA) is used to leverage the potential benefits of position encoding. A formal context in which O is the set of objects, A is the set of attributes, and I is an incidence relation between the objects and the attributes will be denoted by K = hO, A, Ii. The concept lattice, B, derived from the context hO, A, Ii will be denoted by B(hO, A, Ii). The extent, intent and set of own objects of a concept c in a concept lattice will be denoted by extent(c), intent(c), and ownobj(c) respectively. The infimum of a set of concepts C will be denoted by inf(C). Finally, ⊤(b) denotes the attribute top of attribute b—i.e. ⊤(b) is the largest concept whose intent contains b. In Section 2, it is shown how FCA can be used to construct a concept lattice from a position encoded set of patterns. Such a lattice is called a position encoded pattern lattice (PEPL). A first algorithm, called PMatch, is developed in Section 3, which takes such a PEPL together with text stream to be searched as input and produces the desired match occurrences as output, albeit in a rather inefficient way. As an alternative, a so-called PEPL automaton is defined in Section 4, based on the information in a PEPL. A second algorithm given in Section 5 uses this automaton and the text stream to be searched as input and also produces the desired match occurrences as output. However, in this instance the theoretical performance of the algorithm corresponds to that of Aho-Corasick. In a final section, we reflect on the implications of these results. 2
Position Encoded Pattern Lattices (PEPLs) The length of string p will be denoted by |p| and its (i + 1)st element by pi for i ∈ [0, |p|). A match occurrence of a single pattern p in target s is a pair hp, ti, such that ∀ k ∈ [0, |p|), pk = st+k. The problem of matching a set of patterns P on target s can be defined as the requirement to construct the set of all match occurrences, denoted by MO in our algorithms.
Definition 1 (Position encoding of a set of patterns). The position encoding of string w is the set of position-symbol pairs denoted by →w• and is given by →w• = (S k : k ∈ [1, |w|] : {hk, wk−1i}). →• →• The position encoding of a set of strings P is denoted P and is given by P = →• (S w : w ∈ P : w ) →• For example, the position encoding of “pack” is pack = {h1, pi, h2, ai, h3, ci, h4, ki}, →• and of “packet” it is packet = {h1, pi, h2, ai, h3, ci, h4, ki, h5, ei, h6, ti}. In this case, the position encoding of the set of patterns P = {pack, packet} and of →• →• “packet” happens to be the same, i.e. P = packet.
Given any set of patterns, we can now constitute a formal context K# along the following lines. Regard the words in the set of patterns as a set of objects. Let the position-symbol pairs of the position encoding of the set of patterns serve as attributes of these objects: a given word has as its attributes all the position-symbol pairs that make up its position-encoding.
As an example, consider the set of patterns P = {abc, aabc, abcc}. Table 1 shows the cross table that represents the position encoded formal context derived from →• →• →• P . This context can be denoted by hP, P , I P i, where I P is the incidence relation between objects and attributes depicted in the cross table. The formal concept lattice to be derived from such a context will be called a Position En→• →• →• coded Pattern Lattice (PEPL), denoted by P (hP, P , I P i) or, more concisely, →• by P . The cover graph of the underlying PEPL is shown in Figure 2.
→• →• h1, ai h2, ai h2, bi h3, bi h3, ci h4, ci hP, P , I P i abc aabc abcc × × × ×
× × × × × × h2, aih3, bi
4 aabc
If a search of text s is currently at position s[t], and it is found that s[t + n] = a, then attribute hn, ai is said to positively check against s at t.
It is evident that the intent of a PEPL concept has the following property: If all the attributes in the intent have been positively checked against a search text s at position t, then the (one or more) words that are own objects of the concept match the text, starting at position t. This is clearly the case for concepts 3, 4 and 5 with own objects “abc”, “aabc” and “abcc” respectively. 3
PEPL-based Matching Using PMatch
Algorithm 1 described below is based on the insights of the previous section. Its
→• →• →•
top level procedure is called PMatch, which takes as input a PEPL P (hP, P , I P i)
→•
(or simply P ) and a text, s. It then finds in s all match occurrences of words
in P , recording them in MO. The algorithm is articulated in Dijkstra’s guarded
command language (GCL), widely used for its conciseness and precision [
→• proc PMatch( P , s)
MO, j : = ∅, minlength(P ); { Traverse target string s from left to right } for (t ∈ [0, |s| − j + 1)) →
matchIntent(t, ⊤, nil) rof corp{ post : MO is the set of match occurrences of P in s } proc matchIntent(t, c, p) if (p = nil) → ∆ : = intent(c) [] (p 6= nil) → ∆ : = intent(c) \ intent(p) f i; do (∃hi, αi : hi, αi ∈ ∆ : (s[t + i − 1] = α)) →
∆ : = ∆ \ {hi, αi} corp od; if (∆ = ∅) → MO : = MO ∪ ownobj(c) × {t};
for all c′ ∈ children(c) → matchIntent(t, c′, c) rof [] (∆ 6= ∅) → skip f i To illustrate how Algorithm 1 works, consider the keywords to match P = →• →• {abc, aabc, abcc} and the target s = aaabcdabccd. The formal context hP, P , I P i →• is given in Fig. 1 and the cover graph for the corresponding PEPL, P , is in Fig. 2. For convenience, the intents and own object sets of each concept are made explicit in Table 1. Table 2 provides a trace summary of calls to matchIntent. The first column shows t, the offset into s from which matching positions are calculated. The second and third columns show the lattice concept visited and its concept participating in the call to matchIntent. The fourth column marked ∆ gives the set difference between the intent of the child and parent concept. A column per symbol in the string aaabcdabccd then follows. The last column gives the own object set to be to be used to update MO when a match has been found. Note that since minlength(P ) = 3 and |s| = 11, the trace ranges over t ∈ [0, 9). Each row is a matching step of the algorithm—i.e. every row represents a call of the function matchIntent . As an example, the first row indicates that the matching position t = 0 and the attribute set to match is ∆ = {h1,ai}. The first (and only) element of the set is hi,αi = h1,ai. This means that position t + i = 1 is checked for the symbol α = a, which is indeed the case as indicated by the “T” (for the boolean value true) shown in the first column for the target string. All “T” entries in the table indicate that attributes in ∆ have been successfully matched in the do-loop of matchIntent. Once ∆ has been reduced to ∅, MO has to be updated. Of course, if the concept has no own object—as is the case for the top concept marked 1—then nothing is added to MO (i.e. ownobj(c)×{t} = ∅). Subsequent calls to match without updating t, recursively deal with children concepts of the one currently under test. The second row of the table therefore logs the results the call to matchIntent made via match in respect of concept 2, the leftmost child of concept 1. In this case, the intent difference set is ∆ = {h4,ci}, and since ∄hi, αi : {h4,ci} : (s[t + i − 1] = α), (or, more explicitly, s[0 + 4 − 1] = b and not c) matchIntent cannot reduce ∆ to ∅. This is indicated by “F” (for false) as an entry in the relevant column of the table. Control now returns to match, where the next child of concept 1, namely concept 3, is considered. Further rows of the table illustrate the execution steps of Algorithm 1 for the rest of the target string.
PMatch eliminates sets of words from P that do not match in s without ever backing up in s, i.e. t is monotonically increasing. In this sense PMatch is an online algorithm, similar to the AC algorithm. However, PMatch sometimes revisits symbols in s. Such revisits are reflected by the multiple entries in various columns representing symbols in aaabcdabccd in Table 2.
The execution complexity of the matching process per position checked in s is bounded by the size of the PEPL. Table 2 shows how all concepts are visited when t = 6. An (rather conservative) upper bound of the complexity of Algorithm 1 is →• therefore (| P | × |s|). The advanced AC algorithm is of course more efficient than this. Not only does it check every symbol in s exactly once; it also avoids the application of the expensive set difference operator that is applied in matchIntent of Algorithm 1. Instead, the advanced AC simply makes an automaton transition and considers whether an accepting state has been entered. In the upcoming sections, we refine our algorithm to arrive at a PEPL-based algorithm with similar performance characteristics to advanced AC. 4
For PEPL based matching to achieve the same order-of-magnitude performance as the advanced AC algorithm, this section defines a structure called a PEPL Automaton.
Firstly, the position encoded formal context for the set of keywords P is augmented. This augmented context has additional entries to reflect information about each keyword p ∈ P whose first symbol matches the symbol at the mth index of some other keyword, where m > 0. Definition 2 (Augmentation operator). For two strings p and y we define the operator denoted # as p#y = ({(p)y} if y 6= ε ∧ p 6= ε ∅
otherwise Definition 3 (Augmentation of a string). We define the augmentation of string y with respect to string x as
hx, yi# = ([ p, s, r, t : ((x = p · s ∧ y = s · r ∧ s 6= ε) ∨ (x = p · y · t)) : p#y ) Thus, for each proper suffix3 s of x that is also prefix of y, we compute the singleton set p#y (but possibly the empty set) and add all such singleton sets into one big set. Note that there may be several such sets. For example, if x = aa and y = aaaa then the following decompositions of x are relevant : x = ε · aa; x = a · a; so that hx, yi# = ε#aaaa ∪ a#aaaa = ∅ ∪ {(a)aaaa}} = {(a)aaaa} Definition 4 (String-augmentation of a language). We define the stringaugmentation of language V with respect to string w as follows.
hV, wi# = ([ v : v ∈ V : hv, wi#)
h{x, y}, yi# = {(a)aaaa, (aa)aaaa, (aaa)aaaa} h{x, y}, xi# = {(a)aa, (aa)aa, (aaa)aa} h{x}, yi# = {(a)aaaa} h{y}, xi# = {(a)aa, (aa)aa, (aaa)aa} P # = P ∪ ([ p : p ∈ P : hP \ {p}, pi#) {x, y}# = {x, y} ∪ h{x}, yi# ∪ h{y}, xi# Definition 5. For a set of patterns P we define the augmented patterns as = {aa, aaaa} ∪ {(a)aaaa}{(a)aa, (aa)aa, (aaa)aa} = {aa, aaaa, (a)aaaa, (a)aa, (aa)aa, (aaa)aa} 3 By proper suffix, we mean that the empty string is not taken as a suffix. Given set of patterns P , we can constitute a formal context denoted K# for a PEPL using objects from the augmented set of patterns P # and attributes from →• P #.
Example 1. As an example, consider again the set of patterns P = {abc, aabc, abcc} augmented with the set of patterns P # derived as follows: P # = P ∪ h{aabc, abcc}, abci# ∪ h{abc, abcc}, aabci# ∪ h{abc, aabc}, abcci# = P ∪ {(a)abc} ∪ ∅ ∪ {(a)abcc} = P ∪ {(a)abc, (a)abcc} = {abc, aabc, abcc, (a)abc, (a)abcc}
•→ •→ •→ •→ – δ P : Q P × V P 9 Q P × |P #Max| is the automaton’s transition function. The mapping is generally determined by the recursive relationship: h5, ci h3, bi h2, ai h4, ci h1, ai h3, ci h2, bi h5, ci h3, bi h2, ai h4, ci h1, ai h3, ci h2, bi 3 4 2 5 1 6 7 •→ δ P (id(c), hi, αi) = id(c′)/i′ where variables c′ and i′ are defined as follows: hc, ii hc′, i′i = h⊤(h1, αi), 2i
h⊤, 1i hinf({c, ⊤(hi, αi)}), i + 1i if A(c, i, α) ∧ B(c, i, α) if A(c, i, α) ∧ ¬B(c, i, α) ∧ ⊤(h1, αi) 6= ⊥ if A(c, i, α) ∧ ¬B(c, i, α) ∧ ⊤(h1, αi) = ⊥ otherwise where A(c, i, α) ≡ inf({c, ⊤(hi, αi)}) = ⊥ and B(c, i, α) ≡ hi − 1, αi ∈ intent(c) The the first level recursion starts off with c = ⊤. The notation q/x means that when a transition to state q is made, the automaton produces the additional value x.
•→ – q0 P = ⊤ is the automaton’s start state, which is also the top concept of the PEPL.
•→ •→ – F P = (S q, c : q = id(c) ∧ c ∈ Q P ∧ |ownobj(c)| > 0 : {q}) is the automaton’s set of final states.
The above definition embeds sufficient information to derive algorithmically a DFA whose transition diagram can be superimposed on the cover graph of the PEPL. It is assumed below that an function, getFA, is available which delivers a PEPL •→ •→ automaton M P when provided with a PEPL. As an example, getFA( P ) will •→ return M P , the PEPL-Automaton (partially) shown in Fig. 3b, superimposed •→ over the cover graph for P . Note that in order to avoid clutter, a number of arcs have not been shown in Fig. 3b. For example, the many of transitions to ⊤ have been left out. 5
Matching Using a PEPL-Automaton Viewed as a DFA, a PEPL automaton could be used to test whether a given sequence of its alphabet are in the regular set of patterns that it describes. For example, it can easily be seen in Figure 3 that, starting from ⊤, successive transitions on elements of the string hh1, ai, h2, bi, h3, cii lead to the final state 6, affirming that this sequence is indeed part of the set of patterns described by the automaton, and and since abc is an own object of 6, affirming that abc is in the original set of patterns, P .
However, the PEPL is not primarily intended to be used in this way. Instead, the PEPL is used in Algorithm 2 to find all match opportunities in P in a text s. The algorithm’s do processes symbols of s, updating variables c and i to keep track of partial matches in that part of s already processed. This is expressed as loop invariant Inv(c, i, t) ≡ – M O contains all matches in s[0,t−i+1). (These are the matches already processed.) – And s[t−i+1,t) matches the first i − 1 characters of all patterns in extent(c).
(These are the partial matches in progress.) To illustrate matching as executed by Algorithm 2, consider the steps logged in Table 4 when matching the set of patterns abc,aabc,abcc against the target string aaabcdabccd. The first five entries of each row in this table shows the values of variables t, s[t], c, i as they have been updated as a result of the statements in the body of the main loop in Algorithm 2. The next set of entries in the respective row are all empty except for the position where s[t] has been matched. At such a position a “T” or “F” is shown depending on the result of the match. The next entry in the row shows the size of the intent of c. The last entry in this row gives the patterns matched at the step represented by the row.
•→ proc PAutMatch( P , s)
MO : = ∅;
•→ •→ M P : = getFA( P );
•→ •→ hc, ii, t : = hq0 P , 1i, 0; { Recall that q0 P = ⊤ } od corp { post : MO is the set of match occurrences of P in s } As an example we present an explanation of the steps up to the first matched patterns being recorded. Consider the first row of Table 4. This row represents the first step of the matching process. After this step, a transition is made from the start state (c = ⊤) to the same state (c′ = ⊤). The transition is due to the •→ transition function δ P (c, hi, s[t]i) returning the value ⊤/2 for the offset variable i = 1 and symbol s[t = 0] = a. The last entry in the row is empty as the top node does not contain any own objects. The next row shows the transition •→ δ P (⊤, h2, ai) = 3/3 due to value of the variable t being incremented from its value in the previous step. This process continues until the patterns aabc, (a)abc are recorded when the variables i and t are both (coincidentally) equal to 4 and state 4 is reached in the 5th row of the table. Recall that a match is recorded for a state that is represented by a concept such that the size of such concept’s intent (as shown in the second last entry) is the same as the offset variable i. We have arrived at a particularly efficient algorithm, thanks to two observations •→ about PAutMatch . Firstly, transitions in the PEPL-Automaton (δ L ) can be done in constant time using a lookup table. Secondly, the if statement can be made in constant time, and consists of simple integer arithmetic to advance through the lattice and target s, and an update of MO (only if a match has been found). The latter can be done using a precomputed lookup table, as is done in the advanced AC algorithm. These two characteristics are also found in the advanced AC algorithm, and is unavoidable in pattern matching algorithms, giving us the same exact (worst- and best-case) running time of |s|. The example in Table 4 illustrates how, in contrast to the example in Table 2, each symbol in the string aaabcdabccd is visited exactly once to match the keywords {abc, aabc, abcc}. 6
The application of FCA in pattern matching was first introduced in [