Obsidian + 🪴 Quartz 4.0

Aho-Corasick algorithm

7 min read

Aho-Corasick algorithm

It’s a string-searching algorithm. 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 strings simultaneously.

The complexity is linear in the length of string plus the length of the searched text plus the number of output matches: . Multiple matches will be returned for one string location if multiple strings from the dictionary match at that location.

In the Wikipedia’s page about this algorithm, it is written that “when the string 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.”. Making this algorithm perfect for Deep Packet Inspection systems.

Informally, the algorithm creates a trie using the strings in the dictionary and then constructs a finite-state machine from the trie by adding additional links between the nodes:

trie-aho-corasick

trie

Formally, a trie is a rooted tree, where each edge of the tree is labeled with some letter and outgoing edges of a vertex have distinct labels. Each vertex in the trie is identified with the string formed by the labels on the path from the root to that vertex.

Each vertex will also have a flag    which will be set if the vertex corresponds to a pattern in the dictionary. Accordingly a trie for a set of string is a trie such that each vertex corresponds to one string from the set, and conversely, each string of the set corresponds to one vertex.

A trie can be interpreted as a finite deterministic automaton. In such structure from any state we can transition, using some input letter, to other states like another position of strings.

  • Example: if there is only abc in the dictionary and we are standing at vertex ab, then using the letter c we can go to vertex abc.

A suffix link for a vertex    is an edge that points to the longest proper suffix of the string corresponding to the vertex   . The only special case is the root of the trie, whose suffix link will point to itself. Now we can reformulate the statement about the transitions in the automaton like this: while there is no transition from the current vertex of the trie using the current letter (or until we reach the root), we follow the suffix link.

Thus we reduced the problem of constructing an automaton to the problem of finding suffix links for all vertices of the trie. However, we will build these suffix links, oddly enough, using the transitions constructed in the automaton.

The suffix links of the root vertex and all its immediate children point to the root vertex. For any vertex    deeper in the tree, we can calculate the suffix link as follows: if    is the ancestor of    with    being the letter labeling the edge from     to   , go to   , then follow its suffix link, and perform the transition with the letter   from there.

Thus, the problem of finding the transitions has been reduced to the problem of finding suffix links, and the problem of finding suffix links has been reduced to the problem of finding a suffix link and a transition, except for vertices closer to the root. We can solve this recursive dependence in linear time.

It is easy to see that thanks to memoization of the suffix links and transitions, the total time for finding all suffix links and transitions will be linear.

BFS based construction

Instead of computing transitions and suffix links with recursive calls to functions, it is possible to compute them bottom-up starting from the root.

This approach will have some advantages over the one described above as, instead of the total length   , its running time depends only on the number of vertices     in the trie:

  • it is possible to adapt it for large alphabets using a persistent array data structure, thus making the construction time instead of .
  • We can reason inductively using the fact that BFS from the root traverses vertices in order of increasing length.

To construct it, do a breadth-first search of the trie, performing the following operation:

  • If the node is a root, it has no suffix link
  • If the node is one hop away from the root, its suffix link must point to root
  • Otherwise, the node corresponds to some string .

Let x be the node pointed at by w’s suffix link. Then, do the following:

  • If the node xa exists, wa’s suffix link points to xa.
  • Otherwise, if x is the root node, wa’s suffix link points to the root
  • Otherwise, set x to the node pointed at by x’s suffix link and repeat.

The output link at a node corresponding to a string w points to:

  • the node corresponding to the longest proper suffix of w that is a pattern, or
  • null if no such suffix exists

By always pointing to the node corresponding to the longest such word, we ensure that we chain together all the patterns using output links.

Initially, set every node’s output link to be a null pointer. While doing the BFS to fill in suffix links, set the output link of the current node v as follows:

  • Let u be the node pointed at by v’s suffix link.
  • if u corresponds to a pattern, set v’s output link to u itself.
  • Otherwise, set v’s output link to u’s output link.

The time complexity of building all output link is .

Complexity

  • to build the trie
  • work to fill in suffix links
  • work to fill in output links

Total preprocessing time:

After you build the trie, the algorithm for string matching run in

Applications

In competitive programming, this algorithm can be used to:

  • Find all strings from a given set in a text in
  • Finding the lexicographically smallest string of a given length that doesn’t match any given strings
  • Finding the shortest string containing all given strings
  • Finding the lexicographically smallest string of length   containing    strings

Graph View