Aho–Corasick

many needles, one pass over the haystack

ALG 13.3 · ADS2

The problem

  • Needles ι1, …, ιn with lengths Ji, haystack σ of length S.
  • Output: all pairs (k, i) such that σ[k : k + Ji] = ιi.
  • Run KMP n times? Θ(∑Ji + n·S). With 10 000 virus signatures and a 1 GB file, not great.
  • The output itself can be big: needles a, aa, aaa, …
Goal: Θ(∑i Ji + S + V), where V = number of occurrences. You cannot do better.
1975: Alfred Aho and Margaret Corasick (Bell Labs), Efficient string matching: an aid to bibliographic search. The algorithm became the original Unix fgrep. (Aho is also the “A” in AWK.)

States = prefixes of needles; forward edges = a trie

  • Same idea as KMP: a state α means “the last few characters read were α”.
  • Terminal states (double border, with the needle's number) are where needles end. Some are inner nodes (ara is a prefix of arab).

Failure edges: exactly as in KMP

failure edge failure edge to ε

Back(α) = the longest proper suffix of α that is a state. Chop characters off the left of α until you get a state.

Quiz: Back(arab) = ?  → b

Quiz: Back(barbara) = ?

arbara and rbara are not states, but bara is (on the way to baraba). The failure edge jumps to another branch.

Searching: KMP, with a tree instead of a path

AcStep(s, x):
  while Forward(s, x) = ∅ and s ≠ r: s := Back(s)  ▷ fall back
  if Forward(s, x) ≠ ∅: s := Forward(s, x)  ▷ else we are in the root and ignore x
  • Invariant: s is the longest suffix of the text read so far that is a prefix of some needle.
  • Same picture as last week: the failure chain s, Back(s), Back(Back(s)), …, r is the list of all “live alignments”, now of all the needles together.
  • Same amortization: each forward edge goes one level down, each failure edge at least one level up ⇒ Θ(S) steps in total.
When do we report a needle? “When we enter a terminal state.” Right?

Reporting is the new difficulty

After reading bara we are in state bara, which is not terminal, but ara just ended!
  • The needles ending here are exactly the terminal states on the failure chain of s.
  • Walk the whole chain each time? It can be long with nothing to report (needles a…ab with m as and b, haystack aaaa…: about m wasted steps per character).
  • Precompute the set M(β) of needles to report in each state? The total size can be superlinear.

Shortcut edges

Shortcut(α) = ζ(α) = the nearest terminal state reachable from α by failure edges (other than α), i.e. the longest proper suffix of α that is a needle.
shortcut edge   It skips stretches of the failure chain that have nothing to report.

AcSearch

AcSearch(σ):
  s := r
  for x ∈ σ:
    s := AcStep(s, x)
    j := s
    while j ≠ ∅:
      if Word(j) ≠ ∅: report Word(j)
      j := Shortcut(j)
  • Every step along a shortcut edge reports something, except possibly the first one (s itself may not be terminal).
  • Time: Θ(S) for the steps + Θ(V) for the reporting.

Demo: ara, bar, arab, baraba, barbara in σ = barbarabarab

red: failure edges taken · green: forward edge · purple: shortcut edges walked while reporting

Building the automaton

  • The trie is easy. Word(s) is marked when inserting.
  • KMP trick: Back(β) = the state we reach by searching in β[1:], i.e. β with its first character bitten off.
  • KMP: one run over ι[1:], the reader stays behind the writer.
  • AC: run over all ιi[1:] one after another? No! Failure edges cross branches, so we might need Back of a node in a branch we have not processed yet.
Fix: go level by level (BFS with a queue F). A failure edge always leads to a strictly shallower state, so every edge we follow is already built. It is like running all the searches on the ιi[1:] in parallel, one character at a time.
Shortcut(s) comes for free: if z = Back(s) is terminal, Shortcut(s) = z; otherwise Shortcut(s) = Shortcut(z).

AcBuild

AcBuild(ι1, …, ιn):
  create the trie, set Word; Back(r) := ∅, Shortcut(r) := ∅
  for every child s of r: Back(s) := r, Shortcut(s) := ∅, put s into F
  while F ≠ ∅:
    take i from F
    for every child s of i, with x the character on the edge is:
      z := AcStep(Back(i), x); Back(s) := z
      if Word(z) ≠ ∅: Shortcut(s) := z else Shortcut(s) := Shortcut(z)
      put s into F
  • Time: it is just the searches in all the ιi[1:], with their steps interleaved ⇒ Θ(∑Ji).
Theorem: Aho–Corasick finds all occurrences in Θ(∑i Ji + S + V).

Demo: AcBuild for ara, bar, arab, baraba, barbara

yellow: node i taken from F · orange: failure edge being created · red/green: the AcStep that finds it · light blue: in the queue

Bonus: the Scunthorpe problem

A naive profanity filter finds the needles inside innocent words, which is why in 1996 people from the town of Scunthorpe could not create AOL accounts. Aho–Corasick finds every occurrence quickly. Deciding which ones matter is a different problem. Playground: try your own needles · game: Where Do I Fail? · ADS2 Arcade