Aho-Corasick Multi-Pattern Search Visualization

The idea: many patterns, one pass

You have a list of patterns (words, virus signatures, banned phrases) and a text of length n. You want every place where any pattern occurs. Running KMP once per pattern reads the text once per pattern. Aho-Corasick (Alfred Aho and Margaret Corasick, 1975) reads it once for all of them.

It builds a small machine from the patterns in two phases, then runs the text through it:

1. Trie. Insert every pattern into one trie.
2. Failure links. Give every node a link to use when the next character has no edge.
3. Scan. Feed the text through, one character at a time, and report a match whenever the state is a pattern node or has an output link.

Phase 1: the trie

Each node stands for the string on the path from the root, so the canvas names nodes by that string (sh, she). Patterns with a common prefix share nodes: he and hers share h and he. A node where a pattern ends is an output node; on the canvas it has that pattern's colour. In the paper, following an edge is the goto function. Building the trie takes time proportional to the total length of the patterns.

Phase 2: failure links by BFS

Suppose the machine is in state she and the next character is r. There is no r edge. The last characters read were she, so the best state to continue from is the longest proper suffix of she that is also a node: he. That is the failure link fail(she) = he. From he the r edge exists, and the scan goes on to her.

The links are computed level by level with a queue (breadth-first), because a node's link is found from its parent's link, which is one level up:

• Depth-1 nodes fail to the root.
• For a node v = u + c, start at f = fail(u). While f has no c edge and is not the root, set f = fail(f). Then fail(v) is f's c child, or the root if there is none.

This is the same idea as the KMP failure table, run on a trie instead of a single pattern. The queue on the canvas shows the BFS order (Demo 1).

buildFailureLinks():
    for each child v of root:  fail(v) = root;  queue.push(v)
    while queue not empty:
        u = queue.pop()
        for each child v = u + c:
            f = fail(u)
            while f ≠ root and f has no c edge:  f = fail(f)
            fail(v) = f.c if it exists, else root
            out(v)  = fail(v) if fail(v) is a pattern node, else out(fail(v))
            queue.push(v)

Output links

When the scan reaches she, the pattern she ends there, but so does he, a suffix of it. The output link (also called the dictionary suffix link) of a node points to the nearest node on its failure chain where a pattern ends. Following output links from the current state lists every pattern that ends at this text position, without walking failure links that lead nowhere. In Demo 2 the state ca is not a pattern itself, but its output link reports a; in Demo 3 the state aaa reports aaa, aa and a through a chain of output links.

Phase 3: the scan

Start at the root. For each text character c: while the state has no c edge and is not the root, follow its failure link; then take the c edge if there is one. Report the state if it is a pattern node, and every node on its output-link chain. The text index never moves back. Scanning ushers with he, she, his, hers (Demo 1):

i	char	moves	state	reported
0	u	root has no u edge	root
1	s	root → s	s
2	h	s → sh	sh
3	e	sh → she	she	she at 1, he at 2 (output link)
4	r	she fails to he, he → her	her
5	s	her → hers	hers	hers at 2

Demo 4 shows a long fallback: after aaaa the character b follows three failure links (aaaa → aaa → aa → a) before the b edge of a leads to ab. Demo 5 passes through sh and hi, which are prefixes of patterns, but no pattern ends, so nothing is reported.

Running time

Let m be the total length of all patterns, n the text length and z the number of matches.

• Building the trie and the links: O(m) (times the alphabet size if each node keeps an array of children).
• Scanning: O(n + z). Each goto edge makes the state one character deeper, and each failure hop makes it at least one character shallower, so there are at most n hops in total. Output links cost one step per match reported.

The scan cost does not depend on the number of patterns. That is why Aho-Corasick is behind grep -F / fgrep with many fixed strings, intrusion-detection signatures (Snort), antivirus scanners (ClamAV) and ad-block filter lists. For one pattern, see KMP and the String Search Race.

What the page leaves out

Real implementations often precompute the full DFA: a goto entry for every node and every character, so the scan never follows a failure link at run time. They store children as arrays, hash maps or double arrays to trade memory against speed, work on bytes rather than letters, and keep the state between chunks to scan a stream. The page also leaves out case folding, wildcards, and adding patterns after the links are built.

References

Aho & Corasick, "Efficient string matching: an aid to bibliographic search" (CACM, 1975)

Aho-Corasick algorithm (Wikipedia)

Aho-Corasick algorithm (cp-algorithms)