One pass for every pattern at once

This site’s essay on Knuth–Morris–Pratt ends by naming the generalisation and not taking it. This is that generalisation.

The failure function KMP builds says, for each prefix of the pattern, the longest proper suffix of that prefix which is also a prefix of the pattern — so that a mismatch never has to move the read head backwards. Put many patterns in a trie and ask the same question of each node, and the answer is a failure link to the deepest node whose path is a proper suffix of this one. That is the whole construction.

What one pass costs, and what many passes cost #

The measurement is stark and it is the reason the structure exists.

A text of twenty thousand characters, searched for patterns of six characters each drawn from that text. The automaton reads the text once per run — 20,000 character reads — whatever the number of patterns. Running this site’s own Knuth–Morris–Pratt once per pattern reads it once per pattern.

The left-hand column is constant and the right-hand one is linear in the number of patterns, so the ratio is the pattern count. At sixty-four it is a factor of eighty.

The two matchers are asserted to agree on every occurrence, at every pattern count, before either count is reported. That check is not a formality: the failure mode of this structure loses occurrences rather than inventing them, and a matcher that loses occurrences reads exactly as much text and reports a better number of everything else.

The link that is easy to leave out #

There is a second kind of link, it is not the failure link, and the structure is silently wrong without it.

A node can be the end of one pattern while a suffix of the path to it is another pattern. In the automaton above, the node spelling she is the end of “she”, and the path he — reachable from it by one failure link — is the end of “he”. Arriving at she should report both.

The fix is a chain of output links: from each node, to the nearest node along its failure chain that is the end of some pattern. Arriving at a node, report its own patterns and then walk that chain.

Leaving it out produces this:

The he inside she is gone. And the broken version reads the same six characters, holds the same ten states, follows the same failure links, and reports fewer results — so every count it produces is at least as good as the correct one’s.

This site’s gate carries that as a rejection rather than as a measurement: it runs both matchers on the constructed text and requires them to disagree. Written the other way round — asserting that the correct matcher finds three — it would pass whether or not the broken one was ever built, which is the shape measured, not asserted exists to prevent and the fifth consecutive phase on this site to need it said.

Three functions, and only one of them is the algorithm #

Aho and Corasick’s original paper describes the machine as three functions, and keeping them separate is what makes the structure easy to reason about and easy to get wrong.

Goto is the trie: from a state and a character, the child if there is one. It knows nothing about failure and is built by inserting the patterns.

Failure is the link followed when goto has nothing, and it is the only part that requires thought. It is computed breadth-first, because a node’s failure target is found by following its parent’s failure link — which must already be correct, so the order of construction is forced. That is the third time in this phase that a construction is correct only in one order.

Output is what to report on arriving at a state: the patterns ending there, plus everything reachable along the output chain.

The failure function is the algorithm; the other two are bookkeeping. And the defect described above is a defect of output, which is why it survives every test that exercises the matching and none that exercises the reporting. An implementation can have a perfectly correct failure function and lose a third of its occurrences.

The failure link and the suffix link are the same object #

The previous essay’s suffix automaton has links that go from a state to the state of the next shorter class, and they form a tree. Aho–Corasick’s failure links go from a node to the deepest node whose path is a proper suffix, and they form a tree.

They are the same idea and they even coincide in a precise case: the failure links of a trie built from all suffixes of one text are exactly the suffix links of that text’s suffix tree. The two structures in this phase are two applications of one observation — that the set of suffixes of what has been read so far is the state a matcher needs, and that it can be represented by a single node plus a chain.

What the failure hops actually cost #

A single character can follow a long chain of failure links before it finds a transition or reaches the root, so the per-character cost is not constant. The total is, by the same potential argument as everywhere else in this phase: the depth in the trie rises by at most one per character and each hop strictly reduces it, so the hops over the whole text are bounded by its length.

Measured on twenty thousand characters: 4,989 hops with one pattern, 14,526 with four, 16,936 with sixteen, 16,636 with sixty-four. All under the length of the text, as the argument requires, and — worth noticing — no larger at sixty-four patterns than at sixteen.

That flattening is not an error. A larger trie has more transitions out of each node, so a character is more likely to find one without hopping at all — the structure gets denser about as fast as it gets deeper, and past a handful of patterns the two effects cancel. The amortised bound is loosest in exactly the regime the structure is used in.

The hops can be removed entirely, and it costs transitions #

There is a second form of the automaton in which no character ever follows a failure link, and the trade it makes is the cleanest one in this essay.

Give every state an explicit transition for every symbol of the alphabet, computing the missing ones during the same breadth-first pass that builds the failure links: state $v$’s edge for a character it does not have is whatever $v$’s failure target has for that character. The result is an ordinary deterministic automaton — one table lookup a character, no chains, no amortised argument needed.

Both forms find identical occurrences, which the gate requires before either column is reported. The dense form holds exactly $\sigma$ times as many transitions and takes zero hops.

On a four-symbol alphabet that is obviously the right trade: a factor of four on a structure holding a few hundred entries, against sixteen thousand pointer chases. On a Unicode alphabet it is obviously the wrong one, and the interesting implementations sit between — a dense table for the shallow, hot states near the root and sparse maps for the deep ones, which is a decision about where the traffic is rather than about the algorithm.

That is a threshold with a number behind it, which is the shape the threshold is the algorithm collects. The crossing point is set by the alphabet and by how many states are visited often, and neither is in the bound.

Where the cost really is #

Nothing here is free and the price is in three places, none of which is the text scan.

States, proportional to the total pattern length. Two hundred and forty-three for sixty-four patterns of six characters. That is small in this experiment and is not small when the pattern set is a virus signature database with hundreds of thousands of entries — where the structure becomes a serious memory consumer and the engineering is all about representing the transitions compactly.

A transition lookup per character, over an alphabet-sized branch. A map lookup here, an array of 256 slots per node in a fast implementation, a compressed representation in a careful one. The three differ by a large constant and by an even larger space factor, and choosing between them is where implementations actually differ.

Construction, once. Linear in the total pattern length, with the same amortised argument as the search.

Against those, the thing that does not grow is the only quantity a streaming deployment cares about: characters of input touched. An intrusion detector watching a network link cannot afford to read the traffic once per signature, and it does not have to.

The construction order is forced, again #

Worth one paragraph because it is the third time in this phase that a structure is correct only when it is built in one particular order.

A node’s failure target is found by following its parent’s failure link and looking for a transition on the node’s own character. So the parent’s link must already be right, which means the nodes have to be processed in order of increasing depth — breadth-first, and no other order works. Build the failure links depth-first and the structure is still a trie, still accepts every pattern, and has links pointing at nodes whose own links were not yet computed.

That failure is quiet in the same way the others are. The matcher still finds every pattern that occurs at a position no failure link is needed for, which on ordinary text is most of them, and the occurrences it loses are the ones that begin inside another partial match. The test that catches it is the one used throughout this phase: compare against a computation that does not share the mistake — here, a single-pattern matcher run once per pattern, which has no links at all.

The term the flat line does not include #

Characters read is flat at twenty thousand however many patterns are searched for, and that is the headline of the whole structure. It is a count of reading, and there is a second count that the plates do not draw.

Every arrival at a state walks the output chain, and each hop on that chain lands on a node that ends some pattern and therefore emits an occurrence. So the chain does no wasted work — the hops and the reported occurrences are the same number — and the automaton’s total cost is

$$O(\text{total pattern length}) + O(n) + O(\text{occ})$$

with the three terms being construction, reading and reporting. The first two are what the tables above measure and the third is invisible in them, because on the pattern sets used here the occurrences are few.

They are not always few, and the case where they are not is easy to construct. Take the patterns $a$, $aa$, $aaa$ and so on up to $a^k$ — a set whose total length is $k(k+1)/2$ and whose trie is a path of $k+1$ states — and run it over a text of $n$ copies of $a$. Every position ends an occurrence of every pattern no longer than the prefix so far, so the automaton reports about $nk$ occurrences while reading $n$ characters. The read count is flat, the state count is tiny, and the machine is doing work proportional to the product.

Nothing there is a defect. The occurrences are real, any correct matcher must produce them, and a bound with an $\mathrm{occ}$ term in it is the honest form. What the example shows is that the flat line is a claim about one of three costs, and that a pattern set with heavy nesting moves the work into the term the plates do not show.

Two practical readings follow. A deployment that only needs to know whether any pattern occurred, or which patterns occurred at least once, never has to walk the chain at all — mark the pattern as seen and continue — so the third term can often be dropped by asking a weaker question. And a benchmark of this structure that reports characters read is reporting the term that cannot vary, which makes it an excellent measure of the algorithm and a poor measure of a run.

The alphabet that matters is the patterns’, not the text’s #

The dense form is described above as obviously right on four symbols and obviously wrong on Unicode, and that second half is not true. The table’s width is not the text’s alphabet; it is the alphabet the patterns use, plus one.

Consider a symbol occurring nowhere in any pattern. From any state, a transition on it follows failure links until it reaches the root, and the root has no transition on it either, so the machine lands back at the root. That is the outcome from every state without exception, so all such symbols behave identically and one column of the table serves all of them.

So a dense automaton over a pattern set drawn from twenty-six letters is twenty-seven columns wide whatever the encoding of the text, and the mapping from a text character to a column is one lookup in a table indexed by the raw symbol — which for a byte-oriented text is 256 entries and for a wider encoding is a hash or a range check.

That changes the trade the essay records rather than removing it. The factor of $\sigma$ in the transition count is real and is a factor of the pattern alphabet, which for a signature database over bytes is genuinely 256 and for a dictionary of English words is 26. The states are what the pattern set decides, and multiplying a few hundred thousand states by 256 is a real memory cost — which is precisely why the interesting implementations are the hybrids the essay names, dense near the root and sparse below it.

The general form of the observation is worth extracting, because it applies well beyond this structure. An automaton’s alphabet is the set of symbols it distinguishes, not the set of symbols it might see, and any symbol that behaves identically to another under every state can share its column. Collapsing the alphabet by that equivalence is free, it is computable from the pattern set alone, and it is the difference between a table indexed by a character and a table indexed by a character class.

The worst set a trie can be given #

The state count is what everything above is a function of, and it is bounded by the total length of the patterns rather than by their number — so the cheapest set is the one whose patterns share the most, and the extreme of sharing is a set in which every pattern is a prefix of the next.

The two extremes bracket the same claim. Nesting makes the structure small and the output large; disjoint patterns make the structure large and the output sparse; and in both cases the scan reads each position exactly once, which is the only quantity the essay is about.

What it cannot do #

The automaton finds a fixed set of literal strings. It does not do wildcards, it does not do character classes, and it does not do approximate matching — a pattern one character off is simply absent.

The last of those connects this phase’s two halves. Finding a set of strings exactly costs one pass over the text; finding one string approximately costs the product of the two lengths, as a distance that is a path through a grid measured. The gap between the two is not an implementation detail — the automaton’s state is where in the patterns the text currently is, a single node plus a chain, and no such summary exists once the match is allowed to be imperfect. That is why the approximate half of this phase is built out of tables and the exact half out of automata.

There is a bridge, and it is named rather than taken: a regular expression is compiled to an automaton by exactly this machinery, and a bounded number of errors can be expressed as a regular language over an alphabet of edit operations — which turns approximate matching into automaton matching at the cost of an automaton whose size grows with the error bound. That is where this subject goes next, and it is not measured here.

The habit worth carrying out of this essay is narrower than the algorithm. When a problem becomes plural — many patterns, many queries, many keys — the first question is whether the per-item work can be shared rather than repeated, and the second is what has to be held in order to share it. Here the answer is a trie of the patterns and the answer is small. Where it is not small, the repetition is the right answer, and knowing which case one is in requires both numbers rather than a preference.