The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.
A deterministic finite automaton (DFA) defines a set of strings, called its
language. It is represented as a graph with symbol-labelled transitions between
states. There are efficient algorithms to determine whether an input string
belongs to the DFA’s language. An approach to reducing DFA memory
requirements is the use of so-called failure deterministic finite automata (FDFAs, also
defined in Section 2). An FDFA can be used to define the same language as a
DFA with a reduced number of transitions and hence, reduced space required
to store transition information. Essentially, this is achieved by replacing certain
DFA state transitions by so-called failure transitions. A small additional
computational cost is incurred in recognising whether given strings are part of the
language. By using a trie (the term used for a DFA graph that is a tree) and
failure transitions, Aho and Corasick [
An alternative approach to constructing FDFAs from an arbitrary DFA has been
proposed by Kumar et al [
An alphabet is a set of symbols, Σ, of size |Σ|, and Σ∗ denotes the set of all sequences over this alphabet, including the empty sequence, denoted by . A string (or word), s, is an element of Σ∗ and its length is denoted |s|. Note that | | = 0. The concatenation of strings p and q is represented as pq. If s = pqw then q is a substring of s, p and pq are prefixes of s and q and qw are suffixes of s. Moreover, q is a proper substring iff ¬((p = ) ∨ (w = )). Similarly, pq is a proper prefix iff w 6= and qw is a proper suffix iff p 6= .
A deterministic finite automata (DFA) is a quintuple, D = (Q, Σ, δ, F, qs), where Q is a finite set of states; Σ is an alphabet; δ ∈ Q × Σ 9 Q is the (possibly partial) symbol transition function mapping symbol/state pairs to states; qs ∈ Q is the start state; and F ⊆ Q is a set of final states. If δ is a total function, then the DFA is called complete. In the case of a complete DFA, the extension of δ is defined as δ∗ ∈ Q × Σ∗ −→ Q where δ∗(p, ) = p and if δ(p, a) = q and w ∈ Σ∗, then δ∗(p, aw) = δ∗(q, w). A finite string, w, is said to be accepted by the DFA iff δ∗(qs, w) ∈ F . The language of a DFA is the set of accepted strings. A failure DFA (FDFA) is a six-tuple, (Q, Σ, δ, f, F, qs), where D = (Q, Σ, δ, F, qs) is a (not necessarily complete) DFA and f ∈ Q 9 Q is a (possibly partial) failure transition function. For all a ∈ Σ and p ∈ Q, the functions δ and f are related in the following way: f(p) = q for some q ∈ Q if δ(p, a) is not defined. The extension of δ in an FDFA context is similar to its DFA version in that δ∗ ∈ Q × Σ∗ −→ Q and δ∗(p, ) = p. However: δ∗(p, aw) =
δ∗(q, w) if δ(p, a) = q
δ∗(q, aw) if δ(p, a) is not defined and f(p) = q
An FDFA is said to accept string w ∈ Σ∗ iff δ∗(qs, w) ∈ F . An FDFA’s language
is its set of accepted strings. It can be shown that every complete DFA has a
language-equivalent FDFA and vice-versa. When constructing an FDFA from a
DFA, care must be taken to avoid so-called divergent cycles of failure transitions
because they lead to an infinite sequence of failure traversals in string processing
algorithms. (Details are provided in [
Subfigure 1a depicts a complete DFA for which Q = {q1, q2, q3} and Σ = {a, b, c}. Its start state is q1 and q3 is the only final state. Its symbol transitions are depicted as solid arrows between states. Subfigure 1b shows a language-equivalent FDFA where dashed arrows indicate the failure transitions. Note, for example that ab is in the language of both automata. In the DFA case, δ∗(q1, ab) = δ∗(q1, b) = δ∗(q3, ) In the FDFA case, δ∗(q1, ab) = δ∗(q1, b) = δ∗(q2, b) = δ∗(q3, b) = δ∗(q3, ).
(a) D = (Q, Σ, δ, q1, {q3})
(b) F = (Q, Σ, δ, f, q1, {q3}) start a q1 f
f
q2
c
f
b
q3
(d) State/out-transition lattice
start
a
q1
c
a
b
q2
c
a,c
b
b
q3
This text relies on standard formal concept analysis terminology and definitions.
(See, for example [
The expression, |ext(c)| − 1 represents the number of states in step 2 above. At each such state, |int(c)| symbol transitions are removed and a failure arc is inserted. Thus, |int(c)| − 1 is the total number of transitions saved at each of |ext(c)| − 1 states so that ar(c) is indeed the total number of arcs saved by the above transformation.
The positive arc redundancy (PAR) set consists of all concepts whose arc redundancy is greater than zero. 3
For the DFA-Homomorphic Algorithm (DHA) to convert a DFA into a language
equivalent FDFA, a three stage transformation of the DFA is undertaken.
Initially, the DFA is represented as a state/out-transition context. From the derived
concept lattices, the PAR set is extracted to serve as input for the DHA.
The basic DHA proposed in [
Three variants of the algorithm are proposed with respect to the third line. For convenience we represent each variant by a conjunct on the right hand side of an assignment where c is the assignment target. This, of course, is a slight abuse of notation since c is not the outcome of a logical operation, but the selection of a concept from the PAR set according to a criterion represented by h mar(PAR), h me(PAR) or h mi(PAR). Each selection option a different greedy heuristic for choosing concept c from the PAR set. By greedy we mean that an element from the set is selected, based on some maximal or minimal feature, without regard to possible opportunities lost in the forthcoming iterations by making these selections. In addition to these heuristics, a single heuristic is proposed for the fifth line relating to choosing the target state, t, for the failure transitions. These choices are illustrated as colour-coded assignment statements shown in the skeleton Algorithm 2 and are now briefly explained. The rationale for these heuristics will be discussed a section below.
O := Q; PAR := {c | ar(c) > 0}; do ((O 6= ∅) ∧ (PAR 6= ∅)) → c := SelectConcept(PAR); PAR : = PAR\{c}; t := getAnyState(ext(c)); ext0(c) := ext(c)\{t}; for each (s ∈ ext0(c) ∩ O) → if a failure cycle is not created → for each ((a, r) ∈ int(c)) → δ : = δ \ {hs, a, ri} rof ; f(s) : = t;
O : = O\{s} ; od rof fi
O := Q; PAR := {c | ar(c) > 0}; do ((O 6= ∅) ∧ (PAR 6= ∅)) → c := h mar(PAR) ∨ h me(PAR) ∨ h mi(PAR) PAR : = PAR\{c} t := ClosestT oRoot(c) ext0(c) := ext(c)\{t}; for each (s ∈ ext0(c) ∩ O) → if a failure cycle is not created → for each ((a, r) ∈ int(c)) →
δ : = δ \ {hs, a, ri} od rof fi rof ; f(s) : = t; O : = O\{s} ; The heuristics for choosing concept c from the PAR set in each iteration are as follows: The h mar heuristic: c is a PAR concept with a maximum arc redundancy. The h mi heuristic: c is a PAR concept with a maximum intent size. The h me heuristic: c is a PAR concept with a minimum extent size. Once one of these heuristics has been applied, the so-called ClosestToRoot heuristic is used to select a state t in ext(c) to become the target state of failure transitions from each of the remaining states in ext(c). The heuristic means that t is selected as the state in ext(c) that is closest6 to aco’s start state. Transition modifications are subsequently made on the FDFA produced to date, provided that a divergent failure cycle is not produced. 6 Since a trie has no cycles, the notion of “closest” here simply means a state with the shortest path from the start state to that state.
The experiments were conducted on an Intel i5 dual core CPU machine, running Linux Ubuntu 14.4. Code was written in C++ and compiled under the GCC version 4.8.2 compiler.
It can easily be demonstrated that if there are no overlaps between proper prefixes and proper suffixes of keywords in a keyword set, then the associated acf FDFA’s failure transitions will all loop back to its start state, and out ClosestToRoot heuristic will behave similarly. To avoid keyword sets that lead to such trivial acf FDFAs, the following keyword set construction algorithm was devised.
Keywords (also referred to as patterns) are from an alphabet set of size 10. Their lengths range from 5 to 60 characters. Keyword sets of sizes 5, 10, 15, . . . , 100 respectively are generated. For each of these 20 different set sizes, twelve alternative keyword sets are generated. Thus in total 12 × 20 = 240 keyword sets are available.
To construct a keyword set of size N , an initial N random strings are generated7.
Each such string has random content taken from the alphabet and random length
in the range 5 and 30. However, for reasons given below, only a limited number of
these N strings, say M , are directly inserted into the keyword set. The set is then
incrementally grown to the desired size, N , by repeating the following:
Select a prefix of random length, say p, from a randomly selected string
in the current keyword set. Remove a string, say w, from the set of strings
not yet in the keyword set. Insert either pw or wp into the keyword set.
Steps are taken to ensure that there is a reasonable representation of each of
these three differently constructed keywords in a given keyword set.
These keyword sets served as input to the SPARE-PARTS toolkit [
http : //www .fastar .org/wiki /index .php?title = Conference Papers#2015 .
the FDFA corresponding to kth keyword set of size 5j that was generated by
the algorithm variant i ∈ FA\{aco}, where k ∈ [
0 0 1 0 8 0 ()s% 60 vnag i S rcsA 40 ●
● ● 20 ● mmiar ● kamucefm 0 ● 20 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 40 60 Pattern Set Size 80
100 Fig. 2: |δja.co| − (|δji.| + |fij.|) |δja.co|
The fact that the percentage transition savings of the various FDFA variants closely correspond to that of acf does not mean that the positioning of the failure and symbol transitions should show a one-to-one matching. The extent to which the transitions precisely match one another is shown in Figure 3. These box-andmi
me rcsA 15 l ob m tyS 10 vaen l ique 5 on fI .oN 0 rcsA250 lbom200 y tnS150 e l ivua100 q Ifne 50 o .oN 0 mar ● ● ● kum 5 01 51 02 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 001
Pat ern Set Size 5 01 51 02 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 001
Pat ern Set Size (a) |δjakcf| − |δjakcf ∩ δjk|
i 5 01 51 02 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 001
Pat ern Set Size 5 01 51 02 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 001
Pat ern Set Size 5 01 51 02 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 001
Pat ern Set Size 5 01 51 02 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 001
Pat ern Set Size me ● ● kum ● ● ●● ●
● 5 01 51 02 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 001
Pat ern Set Size whisker plots show explicitly the median, 25th and 75th percentiles as well as outliers of each of the 12 sample keyword sets of a given size. Subfigure 3a shows the number of symbol transitions in acf FDFAs that do not correspond with those in mi, me, mar and kum respectively. Subfigure 3b shows the percentage of acf failure transitions matching those of the FDFAs generated by mi, me, mar and kum respectively.
The symbol transitions for the mi heuristic are practically identical to those of acf, differing by at most two. Differences are not significantly related to sample size. Differences for me are somewhat larger, increasing slightly with larger sample size, though still relatively modest in relation to the overall number of FDFA transitions. (There are |Q| − 1 transitions in the underlying trie.) In the cases of mar and kum, the differences are approximately linearly dependent on the size of the keyword set, reaching over 9000 and 250 respectively for keywords sets of size 100.
The failure transition differences in regard to mi and me show a very similar pattern as keyword size increases. Only in isolated instances do they fully match those of acf, but the matching correspondence drops from a median of more than 95% in the case of the smallest keywords sets to a median of about 50% for the largest keyword sets. The median kum failure transition correspondence with acf is in a range of about 12-18% for all pattern set sizes. However, in the case of mar, the degree of correspondence is much worse: at best the median value is just over 60% for small keyword sets, dropping close to zero for medium range keyword set sizes, and then increasing slightly to about 10% for the largest keyword sets.
Overall, Figures 2 and 3 reveal that there is a variety of ways in which failure transitions may be positioned in an FDFA, and that lead to very good—in many cases even optimal—transition savings. It is interesting to note that even in the kum FDFAs, the total number of transition savings is very close to optimal, despite relatively large differences in the positioning of the transitions. However, the figures also show that this flexibility in positioning failure transitions to achieve good arc savings eventually breaks down, as in the case of the mar FDFAs.
One of the reasons for differences between acf FDFAs and the others is that some implementations of the acf algorithm, including the SPARE-PARTS implementation, inserts a failure arc at every state (except the start state), even if there is an out-transition on every alphabet symbol from a state. Such a failure arc is of course redundant. Inspection of the data showed that some of the randomly generated keyword sets lead to such “useless” failure transitions, but they are so rare that they do not materially affect the overall observations. The overall rankings of the output FDFAs of the various algorithms to acf could broadly be stated as mi > me > kum > mar. This ranking is with respect to closeness of transition placement to acf. Since the original focus of this study was to explore heuristics for the DHA algorithm, further comments about the kum algorithm are reserved for the next section.
The rationale for the mar heuristic is clear: it will cause the maximum savings
in transitions in a given iteration. It was in fact the initial criterion proposed
in [
When early trials in our data showed up mar’s relatively poor performance, the mi and me heuristics were introduced to prioritise concepts in the top or bottom regions of the lattice. These latter two heuristics will maximize the number of symbol transitions to be removed per state when replacing them with failure transitions, in so far as concepts with large intents tend to have small extents and vice-versa. Although such a relationship is, of course, data-dependent, random data tends in that direction, as was confirmed by inspection of our data. These two heuristics appear to be rather successful at attaining acf-like FDFAs. However, the ClosestToRoot heuristic has also played a part in this success. Note that the acf failure transitions are designed to record that a suffix of a state’s string is also a prefix of some other state’s string. Thus, f (q) = p means that a suffix of state q’s string is also a prefix of state p’s string. However, since there may be several suffixes of q’s string and several states whose prefixes meet this criterion, the definition of f requires that the longest possible suffix of q’s string should be used. This ensures that there is only one possible state, p, in the trie whose prefix corresponds to that suffix. Thus, on the one hand, acf directs a failure transition “backwards” towards a state whose depth is less than that of the current state. On the other hand, acf selects a failure transition’s target state to be as far as possible from the start state, because the suffix (and therefore also the prefix) used must be maximal in length.
The ClosestToRoot heuristic approximates the acf action in that it also directs failure transitions backwards towards the start state. However, by selecting a failure transition’s target state to be as close as possible from the start state, it seems to contradict acf actions. It is interesting to note in Subfigure 3b that both mi and me show a rapid and more or less linear decline in failure transition matchings with respect to acf when pattern set size reaches about 65. We conjecture that for smaller keyword sizes, theClosestToRoot heuristic does not conflict significantly with acf’s actions because there are few failure target states from which to choose. When keyword set sizes become greater, there is likely to be more failure target states from which to choose, and consequently less correspondence between the failure transitions chosen according to differing criteria.This is but one of several matters that has been left for further study. 5
Our ultimate purpose is to investigate heuristics for building FDFAs from generalised complete DFAs—a domain where optimal behaviour is known a priori to be computationally hard. The comparison against acf FDFAs outlined above is a firm but limited starting point. The next step is to construct complete DFAs from randomly generated FDFAs and examine the extent to which the heuristics tested out in this study can reconstruct the latter from the former. Because generalised DFAs can have cycles, the ClosestToRoot heuristic will be generalised by using Dijktra’s algorithm for calculating the shortest distance from the start state to each DFA state. It remains to be seen whether mar will perform any better in the generalised context.
The relatively small alphabet size of 10 was dictated by unavoidable growth in the size of the associated concept lattices. Even though suitable strategies for trimming the lattice (for example by not generating concepts with arc redundancy less than 2) are being investigated, it is recognised that use of DHA will always be constrained by the potential for the associated lattice to grow exponentially. Nevertheless, from a theoretical perspective a lattice-based DHA approach to FDFA generation is attractive because it encapsulates the solution space in which a minimal FDFA might be found—i.e. each ordering of its concepts maps to a possible language-equivalent FDFA that can be derived from DFA and at least one such ordering will be a minimal FDFA.
The kum FDFA generation approach is not as constrained by space limitations as the DHA approach and in the present experiments it has performed reasonably well. In the original publication, a somewhat more refined version is reported that attempts to avoid unnecessary chains of failure transitions. Future research should examine the minimising potential of this refined version using generalised DFAs as input and should explore more fully the relationship between these kumbased algorithms and the DHA algorithms.