Aho–Corasick string matching algorithm
||This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (February 2013)|
In computer science, the Aho–Corasick string matching algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all patterns simultaneously. The complexity of the algorithm is linear in the length of the patterns plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary =
aaaa and input string is
Informally, the algorithm constructs a finite state machine that resembles a trie with additional links between the various internal nodes. These extra internal links allow fast transitions between failed pattern matches (e.g. a search for
cat in a trie that does not contain
cat, but contains
cart, and thus would fail at the node prefixed by
ca), to other branches of the trie that share a common prefix (e.g., in the previous case, a branch for
attribute might be the best lateral transition). This allows the automaton to transition between pattern matches without the need for backtracking.
When the pattern dictionary is known in advance (e.g. a computer virus database), the construction of the automaton can be performed once off-line and the compiled automaton stored for later use. In this case, its run time is linear in the length of the input plus the number of matched entries.
The graph below is the Aho–Corasick data structure constructed from the specified dictionary, with each row in the table representing a node in the trie, with the column path indicating the (unique) sequence of characters from the root to the node.
The data structure has one node for every prefix of every string in the dictionary. So if (bca) is in the dictionary, then there will be nodes for (bca), (bc), (b), and (). If a node is in the dictionary then it is white node. Otherwise it is a grey node. There is a black directed "child" arc from each node to a node whose name is found by appending one character. So there is a black arc from (bc) to (bca). There is a blue directed "suffix" arc from each node to the node that is the longest possible strict suffix of it in the graph. For example, for node (caa), its strict suffixes are (aa) and (a) and (). The longest of these that exists in the graph is (a). So there is a blue arc from (caa) to (a). There is a green "dictionary suffix" arc from each node to the next node in the dictionary that can be reached by following blue arcs. For example, there is a green arc from (bca) to (a) because (a) is the first node in the dictionary (i.e. a white node) that is reached when following the blue arcs to (ca) and then on to (a).
|Path||In Dictionary||Suffix Link||Dict Suffix Link|
At each step, the current node is extended by finding its child, and if that doesn't exist, finding its suffix's child, and if that doesn't work, finding its suffix's suffix's child, and so on, finally ending in the root node if nothing's seen before.
When the algorithm reaches a node, it outputs all the dictionary entries that end at the current character position in the input text. This is done by printing every node reached by following the dictionary suffix links, starting from that node, and continuing until it reaches a node with no dictionary suffix link. In addition, the node itself is printed, if it is a dictionary entry.
Execution on input string
abccab yields the following steps:
|Node||Remaining String||Output:End Position||Transition||Output|
|()||abccab||start at root|
|(a)||bccab||a:1||() to child (a)||Current node|
|(ab)||ccab||ab:2||(a) to child (ab)||Current node|
|(bc)||cab||bc:3, c:3||(ab) to suffix (b) to child (bc)||Current Node, Dict suffix node|
|(c)||ab||c:4||(bc) to suffix (c) to suffix () to child (c)||Current node|
|(ca)||b||a:5||(c) to child (ca)||Dict suffix node|
|(ab)||ab:6||(ca) to suffix (a) to child (ab)||Current node|
- Set Matching and Aho–Corasick Algorithm, lecture slides by Pekka Kilpeläinen
- Aho–Corasick entry in NIST's Dictionary of Algorithms and Data Structures
- Aho–Corasick string matching in C#, a CodeProject tutorial by Tomáš Petříček
- Aho-Corasick C implementation, good for small pattern lengths.
- Aho-Corasick Python wrapper
- Aho-Corasick explained using Python
- Aho-Corasick Java implementation
- Aho-Corasick Java implementation II
- Animated Aho-Corasick, an animated implementation of Aho-Corasick for learning purposes
- Aho-Corasick C++ implementation, this C++ library also implements some other related algorithms