Aho-Corasick: many patterns at once

Aho-Corasick finds every occurrence of every pattern from a list in one left-to-right pass over a text. It builds a trie of the patterns and gives each node a failure link: the longest proper suffix of the node’s string that is also a path in the trie. While reading the text, the automaton follows a trie edge when the next character has one and failure links when it has none, so it never moves back in the text, and output links report every pattern that ends at the current character. Building takes time in proportion to the total length L of the patterns, and the scan takes O(n + z) for a text of n characters with z matches. Keyword filters, signature scanners and other searches for thousands of fixed strings at once are its typical uses.

Many patterns, one pass

Searching for each pattern on its own costs a pass over the text per pattern: 10⁴ patterns in a text of 10⁶ characters means 10¹⁰ character steps. Aho-Corasick makes at most 2n moves plus one report per match, whatever the number of patterns, because all the patterns share one automaton; NIST’s dictionary of algorithms notes that the machine’s transitions do not grow with the number of keywords. Alfred Aho and Margaret Corasick published the method in 1975, for searching bibliographic text. It generalises Knuth-Morris-Pratt: with a single pattern, the failure links are exactly KMP’s prefix function.

Trie, failure links and output links

The trie below stores the patterns tea, eat, ate and at. A node stands for the string its path spells from the root, and four nodes are marked as the places where a pattern ends.

A failure link answers one question. The text has just spelled this node’s string, and the next character has no edge: what is the longest piece at the end of the text read so far that can still grow into a pattern? It is the longest proper suffix of the node’s string that is a node too. The node tea fails to ea, because a text that spelled tea also spelled ea, and from ea the letter t continues into eat. A node with no such suffix fails to the root.

An output link points along the failure chain to the nearest node where a pattern ends. The node eat links to at, so reaching eat reports two matches: eat, and at, which ends at the same character. Without output links a scan reports only the deepest pattern at each position and misses the ones nested inside it.

Building the links breadth first

The children of the root fail to the root. For a node v reached from its parent u by the letter c, follow failure links from u until a node with an edge for c turns up, or the root does; v fails to that edge’s target, or to the root if there is none. A failure link always points to a shallower node, so taking nodes in breadth-first order guarantees that every link this step follows is already final. The output link of v is its failure target when a pattern ends there, and the failure target’s own output link otherwise. With dictionaries for the edges, the whole construction takes O(L) time for patterns of total length L. The links can also be compiled into a full transition table, one next node per node and letter, which spends memory to make the scan faster.

Scanning the text

The scan keeps one node: the longest suffix of the text read so far that is a trie path. For each character it follows failure links while the node has no edge for it, takes the edge if there is one, and reports the patterns at the node and along its output links. Its whole state is that one node, so the same scan works on a stream that arrives in pieces.

# Aho-Corasick for the patterns tea, eat, ate and at: the trie, the failure links built breadth first, the output
# links, then one pass over a short text that reports every occurrence of every pattern.
from collections import deque


def build(patterns):
    goto = [{}]  # goto[node][letter] = child node; node 0 is the root
    fail = [0]
    ends = [[]]  # patterns that end exactly at this node
    label = [""]  # the string the path to this node spells
    for p in patterns:
        node = 0
        for c in p:
            if c not in goto[node]:
                goto.append({})
                fail.append(0)
                ends.append([])
                label.append(label[node] + c)
                goto[node][c] = len(goto) - 1
            node = goto[node][c]
        ends[node].append(p)
    out = [0] * len(goto)  # output link: the nearest node on the failure chain where a pattern ends (0: none)
    order = []
    queue = deque(goto[0].values())  # depth 1: their failure link is the root
    while queue:
        u = queue.popleft()
        order.append(u)
        for c, v in goto[u].items():
            f = fail[u]
            while f and c not in goto[f]:
                f = fail[f]
            fail[v] = goto[f].get(c, 0)
            out[v] = fail[v] if ends[fail[v]] else out[fail[v]]
            queue.append(v)
    return goto, fail, ends, out, label, order


def search(text, machine):
    goto, fail, ends, out = machine[:4]
    node = 0
    for i, c in enumerate(text):
        while node and c not in goto[node]:
            node = fail[node]  # no edge for c: fall back to the longest suffix that is still a trie path
        node = goto[node].get(c, 0)
        m = node if ends[node] else out[node]
        while m:
            for p in ends[m]:
                yield i - len(p) + 1, p
            m = out[m]


patterns = ["tea", "eat", "ate", "at"]
machine = build(patterns)
goto, fail, ends, out, label, order = machine
print(f"{'node':<6} {'failure link':<13} {'output link':<12} ends here")
for v in order:
    shown = label[out[v]] if out[v] else "-"
    print(f"{label[v]:<6} {label[fail[v]] or 'root':<13} {shown:<12} {', '.join(ends[v]) or '-'}")

text = "seated at the teatray"
print()
print(text)
for start, p in search(text, machine):
    print(f"{' ' * start + p:<24}{p}, from position {start}")

node   failure link  output link  ends here
t      root          -            -
e      root          -            -
a      root          -            -
te     e             -            -
ea     a             -            -
at     t             -            at
tea    ea            -            tea
eat    at            at           eat
ate    te            -            ate

seated at the teatray
 eat                    eat, from position 1
  at                    at, from position 2
  ate                   ate, from position 2
       at               at, from position 7
              tea       tea, from position 14
               eat      eat, from position 15
                at      at, from position 16

The table lists the nodes in breadth-first order with both links, and the scan of “seated at the teatray” finds seven matches. At position 3 the automaton stands on eat and reports eat, then at through the output link. In “teatray” it moves from tea to eat through the failure link of tea, without reading any character twice.

The number of matches is the part of the cost that the automaton cannot shrink. With the patterns a, aa and aaa, every a after the second one in a run of a’s ends three matches, and with k nested patterns of this kind every character can end k of them, so z can exceed n many times over. A filter that only needs a count per pattern should not list the matches one by one.

Practise: count every pattern

Count each pattern’s occurrences in one pass; the sample tests check the counts against a brute-force search.

def count_occurrences(text, patterns):
    """Returns how many times each pattern occurs in text (overlaps count), in the order of patterns."""
    return [0 for _ in patterns]

import random

from occurrences import count_occurrences


def brute_force(text, patterns):
    return [sum(text.startswith(p, i) for i in range(len(text))) for p in patterns]


def test_lesson_example():
    """counts tea, eat, ate and at in the lesson's text"""
    assert count_occurrences("seated at the teatray", ["tea", "eat", "ate", "at"]) == [1, 2, 1, 3]


def test_overlapping_and_nested():
    """counts overlapping occurrences of nested patterns"""
    assert count_occurrences("aaaa", ["a", "aa", "aaa", "aaaaa"]) == [4, 3, 2, 0]


def test_repeated_pattern():
    """gives a pattern listed twice its count twice"""
    assert count_occurrences("abab", ["ab", "ba", "ab"]) == [2, 1, 2]


def test_suffix_patterns():
    """finds a pattern that ends inside a longer one"""
    text = "she sells sea shells"
    patterns = ["he", "she", "hell", "shell", "s", "sea"]
    assert count_occurrences(text, patterns) == brute_force(text, patterns)


def test_edges():
    """handles an empty text and patterns longer than the text"""
    assert count_occurrences("", ["a", "bc"]) == [0, 0]
    assert count_occurrences("ab", ["abc", "b"]) == [0, 1]


def test_random_inputs():
    """matches a brute-force count on 150 random inputs"""
    rng = random.Random(8)
    for _ in range(150):
        letters = "abc"[: rng.randint(2, 3)]
        text = "".join(rng.choice(letters) for _ in range(rng.randint(0, 300)))
        patterns = ["".join(rng.choice(letters) for _ in range(rng.randint(1, 6))) for _ in range(rng.randint(1, 15))]
        assert count_occurrences(text, patterns) == brute_force(text, patterns), (text, patterns)

/** Returns how many times each pattern occurs in text (overlaps count), in the order of patterns. */
export function countOccurrences(text, patterns) {
  return patterns.map(() => 0);
}

import { test, assert } from 'mysmartcopilot:test';
import { countOccurrences } from './occurrences.mjs';

const bruteForce = (text, patterns) =>
  patterns.map((p) => {
    let n = 0;
    for (let i = 0; i < text.length; i++) if (text.startsWith(p, i)) n++;
    return n;
  });

test("counts tea, eat, ate and at in the lesson's text", () => {
  assert.deepEqual(countOccurrences('seated at the teatray', ['tea', 'eat', 'ate', 'at']), [1, 2, 1, 3]);
});

test('counts overlapping occurrences of nested patterns', () => {
  assert.deepEqual(countOccurrences('aaaa', ['a', 'aa', 'aaa', 'aaaaa']), [4, 3, 2, 0]);
});

test('gives a pattern listed twice its count twice', () => {
  assert.deepEqual(countOccurrences('abab', ['ab', 'ba', 'ab']), [2, 1, 2]);
});

test('finds a pattern that ends inside a longer one', () => {
  const text = 'she sells sea shells';
  const patterns = ['he', 'she', 'hell', 'shell', 's', 'sea'];
  assert.deepEqual(countOccurrences(text, patterns), bruteForce(text, patterns));
});

test('handles an empty text and patterns longer than the text', () => {
  assert.deepEqual(countOccurrences('', ['a', 'bc']), [0, 0]);
  assert.deepEqual(countOccurrences('ab', ['abc', 'b']), [0, 1]);
});

test('matches a brute-force count on 150 random inputs', () => {
  let state = 8;
  const next = (m) => {
    state = (state * 48271) % 2147483647; // stays below 2 ** 53, so every engine computes the same values
    return state % m;
  };
  for (let t = 0; t < 150; t++) {
    const letters = 'abc'.slice(0, 2 + next(2));
    let text = '';
    for (let i = next(301); i > 0; i--) text += letters[next(letters.length)];
    const patterns = [];
    for (let k = 1 + next(15); k > 0; k--) {
      let p = '';
      for (let i = 1 + next(6); i > 0; i--) p += letters[next(letters.length)];
      patterns.push(p);
    }
    assert.deepEqual(countOccurrences(text, patterns), bruteForce(text, patterns), text);
  }
});

Why the scan is linear, and what the matches cost Pro: opens with a Pro, Premium or Ultimate pass

Tables or dictionaries, and a filter that holds up Pro: opens with a Pro, Premium or Ultimate pass

Five languages, the bugs small tests miss, and variants Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Aho-Corasick puts all patterns in one trie and adds failure links and output links, built breadth first.
• The scan follows edges and failure links, never moves back in the text, and makes at most 2n moves.
• The total cost is O(L) to build and O(n + z) to scan; z, the number of matches, can far exceed n.
• With one pattern the failure links are KMP’s prefix function.