Aho–Corasick Failure Links and Multi-Pattern Scanning

A dictionary matcher takes a set of k patterns and reports every occurrence of every pattern in a text of length n. Running a single-pattern algorithm once per pattern costs Θ(k·n) scans even when the patterns share prefixes, and pattern sets such as a keyword filter or a tokenizer’s operator table always share prefixes. The alternative is to read the text once and keep a state that represents “which prefixes of dictionary words match the text ending here”. That state is a node in a trie of the patterns, and the automaton that moves between nodes is the Aho–Corasick machine.

The trie alone answers the wrong question. It follows edges only while the text matches a prefix of some pattern, and it stalls the moment the text takes an edge that does not exist. Since every text position must be processed and the trie cannot be restarted at every position without losing the linear bound, the machine needs a transition for every character at every state. Adding those transitions explicitly costs |Σ| per node; adding them as a fallback function costs one edge per node plus a bounded number of hops per text character.

The trie as the primary structure

Build a trie by inserting each pattern, creating nodes for characters and marking the node reached at the end of a pattern as terminal. Each node holds a map from character to child, and the terminal flag is either a boolean or a list when duplicate patterns exist. The root represents the empty prefix.

For a dictionary of k patterns of total length M, the trie has at most M+1 nodes and at most M edges; both counts reach their maximum only when no two patterns share a prefix. A node’s depth equals the length of the prefix it represents, so a match ending at depth d started d characters earlier in the text.

Reading the text one character at a time and following trie edges works only while the text continues along a path. After a failure the machine must find the longest suffix of the text read so far that is also a prefix of some pattern, and resume there. The failure link of a node encodes exactly that: a pointer to the node representing the longest proper suffix of the node’s string that is a prefix in the trie.

Deriving failure links from the parent’s link

The link of a node is computed from its parent’s link, which is why the construction is a breadth-first traversal. The root’s children fail to the root. For any other node u reached from parent p by character c, the candidate is the child-by-c of the failure target of p; if that child does not exist, the candidate’s own failure target is tried, and so on to the root. The result is the standard loop:

from collections import deque

def build(patterns):
    goto = [{}]          # node -> {char: node}
    fail = [0]
    out = [[]]           # node -> patterns ending here
    for pat in patterns:
        v = 0
        for ch in pat:
            if ch not in goto[v]:
                goto[v][ch] = len(goto)
                goto.append({})
                fail.append(0)
                out.append([])
            v = goto[v][ch]
        out[v].append(pat)

    q = deque()
    for ch, u in goto[0].items():
        fail[u] = 0
        q.append(u)
    while q:
        p = q.popleft()
        for ch, u in goto[p].items():
            f = fail[p]
            while f and ch not in goto[f]:
                f = fail[f]          # walk up the suffix chain
            fail[u] = goto[f].get(ch, 0)
            if fail[u] == u:         # p is the root: the only such edge is u itself
                fail[u] = 0
            q.append(u)
    return goto, fail, out

The guard on the last assignment is defensive. A node is the child of exactly one parent, so the edge that reaches u cannot be the same edge that reaches its failure target; if the guard ever fires, the trie has been built wrong. Its practical job is to keep the scan terminating when a malformed trie is handed to the scanner, since a node that fails to itself makes the fallback loop in scan spin forever. Structuring the code so the root’s children are enqueued before the loop is what makes the f = fail[p] start correct: without it, the root would have to be processed and its own links would need a special case.

The loop inside the breadth-first traversal walks the failure chain, so a single node’s link may cost more than one step. A node’s failure chain is strictly shorter than its own depth, so one link costs at most h steps, where h is the longest pattern, and the whole build costs at most M·h. The linear construction removes that factor by memoising the walk in a table of size nodes × |Σ|: the transition for (state, character) is computed once when the state is dequeued and reused by all of its children, so each table entry is filled with one step and the whole table costs O(nodes · |Σ|). The textbook loop is preferable when the alphabet is large and the table would be mostly empty; the table is preferable when the alphabet is small and the dictionary is long. Either way, the construction is independent of the text.

Scanning without re-reading

Once the links exist, the scan is a loop with two nested steps: follow the character edge if it exists, otherwise follow failure links until an edge exists or the state is the root.

def scan(text, goto, fail, out):
    state, hits = 0, []
    for i, ch in enumerate(text):
        while state and ch not in goto[state]:
            state = fail[state]
        state = goto[state].get(ch, 0)
        # every pattern ending at a node on the failure chain also ends here
        s = state
        while s:
            for pat in out[s]:
                hits.append((i - len(pat) + 1, pat))
            s = fail[s]
    return hits

The inner walk over the failure chain is what reports nested patterns. If the dictionary contains both he and she, the state after reading she is the node for she, and the node for he is reachable only through a failure link. Without the walk, he would be missed at that position. The walk costs the depth of the matched pattern, which puts the scan at O(n·h) for the textbook loop, since the state walk itself is amortised O(n). Precomputing the output lists is what removes h: with every node carrying its full list, the scan visits one node per text character and one report per match, so its cost is O(n + z) where z is the number of reported occurrences. When the dictionary is large and matches are frequent, z dominates, and no automaton can do better because the output itself is that large.

The alternative to the report walk is to precompute, for each node, the complete list of patterns that ends at that node or at any node on its failure chain. Each node’s list is its own output concatenated with its failure target’s list, which is computed before it in breadth-first order. That removes the walk from the scan, at the cost of memory proportional to the total size of all lists, which for nested patterns such as a, aa, aaa, … is quadratic in the dictionary size. The trade is between scan time and preprocessing space, and the memory bound is what decides it.

Making every transition explicit

The automaton formulation replaces the failure-following loop with a total transition function δ(state, c) that is defined for every state and character. δ is computed during the breadth-first traversal: for an existing child u of p by c, δ(p, c) = u; for a missing edge, δ(p, c) = δ(fail(p), c). Because the traversal is breadth-first, the failure target’s transition row is already complete when it is needed.

This turns the scan into one array lookup per character:

for (size_t i = 0; i < n; i++) {
    state = delta[state][(unsigned char)text[i]];
    for (size_t j = 0; j < out_count[state]; j++)
        report(i, out_pattern[state][j]);
}

The cost is |Σ| entries per node: for a byte alphabet and a dictionary of a million characters, a transition table of 256 million entries, at one or two bytes each, which is hundreds of megabytes. The explicit table is worth it when the dictionary is small and the text is huge, and it is unusable when the alphabet is Unicode code points, where |Σ| exceeds a million and the table becomes sparse beyond any useful density.

Between the two extremes sits the compressed representation: a sorted edge array per node with binary search, or a hash map per node. Both avoid the |Σ| factor and pay a lookup cost per character. On modern hardware the difference is dominated by cache behaviour rather than instruction count, because a dense table for a small alphabet keeps the hot states in cache while a hash map touches a different bucket per character.

Where the machine stops being the right tool

Three constraints bound the design.

Memory is proportional to the dictionary, not the text. The trie holds every pattern’s characters, so a dictionary of a hundred thousand words occupies megabytes regardless of how short the text is. Building it per query is wasteful; it is built once and reused.

The alphabet must be fixed at build time. Adding a character to the alphabet of an explicit transition table requires rebuilding. With byte transitions this is not an issue; with code points it is another argument for the sparse form.

Patterns with wildcards or classes do not fit. The trie branches on a literal character. A pattern containing a character class would need an edge that matches several characters, which turns the deterministic automaton into a nondeterministic one and reintroduces the subset construction. Regular expression engines handle that case by simulating the NFA, not by this construction.

Deletion is the fourth constraint, and the one that bites in long-running processes. Removing a pattern from the trie leaves nodes that may be shared with other patterns, so the nodes cannot be freed without reference counts. Marking the terminal node as no longer terminal is correct and cheap, but the nodes and failure links remain allocated. A dictionary that churns through patterns grows the trie monotonically unless it is rebuilt.

Relationship to the single-pattern machinery

Aho–Corasick is the multi-pattern generalisation of the KMP automaton: with one pattern, every node has at most one child, the failure links form the border chain of the prefix function, and the scan is KMP. Seen the other way, the prefix function is Aho–Corasick with a dictionary of one word, and the failure link of a node at depth d is the prefix function value for the pattern prefix of length d.

It does not generalise the right-to-left skip of Boyer–Moore. Aho–Corasick reads the text strictly left to right and never skips a character, so on natural-language text with a single pattern it is slower than a good Boyer–Moore implementation. Its advantage appears only when the dictionary has many patterns: the scan cost is independent of k, while any per-pattern method pays k times the scan.

For matching with a fixed number of mismatches, the automaton has no natural extension either. The state would need to record how many errors have been consumed, multiplying the state space by the error budget; the bit-parallel methods described in bit-parallel approximate matching handle small budgets more cheaply.

The failure links themselves are the same object as the suffix links of a suffix automaton, which is the structure behind suffix automata and distinct substrings. The difference is what the nodes represent: a trie of patterns in one case, all substrings of a single text in the other.