The table the links already knew

The table that walks every pair measures the exact Commentz-Walter shift rule costing 769,724 primitive steps to build for 128 patterns, against the published rule’s tables, and concludes that preprocessing quoted as “linear in the total pattern length” is true of one and false of the other.

That conclusion is wrong, and the work that reached it said what would settle the question, in the list of what it had not built: a suffix-link construction of the exact shift rules, which would collapse this strand’s largest ratio to a constant factor if it exists.

It exists.

The condition, restated #

A Commentz-Walter matcher reads a window backwards through a trie of the reversed patterns. It has matched $j$ characters, spelling the word of a trie node $v$, and mismatched on a character $c$. The question is how far the window may move.

The good-suffix condition alone: the window may move by $d$ only if some reversed pattern $r$ agrees with the known segment at that offset — $r[t] = \text{word}(v)[t-d]$ for every $t$ in $[d, \min(d+j-1, |r|-1)]$.

Written as an algorithm that is a loop over $d$, a loop over the patterns and a loop over the offsets, which is what the site built and what costs 757,058 steps at 128 patterns.

The condition splits into two cases #

Look at what the range of $t$ means and the loop disappears.

Case one: the whole segment fits inside the pattern. When $d + j - 1 \le |r| - 1$, the condition says $r[d..d+j-1] = \text{word}(v)$ — the node’s word occurs inside $r$, starting at offset $d$.

Case two: the segment runs off the end. When $d + j - 1 > |r| - 1$, the condition says $r[d..|r|-1]$ equals a prefix of $\text{word}(v)$ — the suffix of $r$ starting at $d$ is a prefix of the node’s word.

And a third, degenerate: when $d \ge |r|$ the range is empty and the condition holds vacuously, which is why no shift ever exceeds the shortest pattern’s length.

The exact shift is the smallest $d$ satisfying any of them.

Case one is the failure links, exactly #

This is the observation the whole essay turns on, and it is one line.

$\text{word}(v)$ occurs inside a reversed pattern $r$ at offset $d$ if and only if there is a trie node $u$ at depth $d + j$ whose word ends with $\text{word}(v)$ — because the trie’s nodes are exactly the prefixes of the reversed patterns, and $r[0..d+j-1]$ is one of them.

“Whose word ends with $\text{word}(v)$” is the failure relation. $u$’s failure link points to the longest proper suffix of $\text{word}(u)$ that is a node, and following the chain reaches every node that is a proper suffix of it. So the set of $u$ satisfying case one for $v$ is exactly the failure subtree of $v$, and the smallest $d$ is $\min_u \text{depth}(u) - \text{depth}(v)$ over that subtree.

The minimum over a failure subtree is attained at a failure child, because depths increase along any path down the failure tree. So one pass over the failure children of every node gives case one for every node.

That number is $d_1$, and the published rule already computes it. The shift somebody published builds it, describes it as “the least depth increase to a node whose word has $\text{word}(v)$ as a proper suffix”, and observes that it is the failure relation read the other way. The shift a set of patterns allows is where this collection first built the exact rule and stated the condition; everything here is a reading of that condition rather than a new one.

So the published rule and the exact rule share their first case exactly. The exact rule is not an expensive quantity that the published one approximates; it is the same quantity with a second case added and without the guard that makes the published one safe.

Case two, which is the new work #

The suffix of some pattern starting at $d$ is a prefix of $\text{word}(v)$. Prefixes of $\text{word}(v)$ are the ancestors of $v$ in the trie, so the condition is: some ancestor $a$ of $v$ has $\text{word}(a)$ as a suffix of some pattern $r$, and then $d = |r| - \text{depth}(a)$.

Two steps compute that for every node.

Which nodes are suffixes of which patterns. The suffixes of a pattern that are trie nodes are exactly the nodes on that pattern’s own failure chain — walk from the pattern’s terminal node down the links to the root, and every node passed is a suffix of it. So one walk per pattern fills $S[a]$, the length of the shortest pattern having $\text{word}(a)$ as a suffix.

The best ancestor. $\min_a (S[a] - \text{depth}(a))$ over the proper ancestors of $v$ is a running minimum down the trie: one pass in breadth-first order, each node taking its parent’s value and its parent’s own candidate.

The exact good-suffix shift is then $\max(1, \min(d_1[v], \text{ancestorBest}[v], w_{\min}))$, and every part of it is a linear pass over a structure the matcher already builds.

The measurement #

Pattern sets of one to 128 patterns of ten characters over four symbols. The good-suffix table alone, with the bad-character table taken out:

The tables are identical at every node and every character, checked at all 2,180 decisions across six set sizes. Not close — identical.

Why the minimum over a failure subtree is attained at a child #

The one step above that is an argument rather than a definition, and it is short enough to give.

The failure tree’s edges go from a node to its longest proper suffix that is also a node, so following a failure link strictly decreases depth. Reading it the other way: every node in $v$’s failure subtree is reached from $v$ by a path of increasing depths.

So if $u$ is in the subtree at distance two or more, the node before it on the path is a failure child of $v$ at a strictly smaller depth. The minimum of $\text{depth}(u) - \text{depth}(v)$ is therefore always attained at distance one, and enumerating the failure children of every node — which is one pass over the links, reversed — enumerates every candidate.

That is why case one is a single loop rather than a traversal, and it is the same argument the published construction uses without stating it. Writing it down matters because the corresponding claim for case two is false: the best ancestor is not always the parent, which is why case two needs a running minimum down the trie rather than a single look upwards.

The other table, which was already nearly linear #

The exact rule needs a bad-character table too — $\text{bad}[c][j]$, the smallest $d \ge 1$ such that some reversed pattern holds $c$ at offset $d + j$ — and it collapses much less: 12,666 steps to 5,168, a factor of 2.45.

The reason is that its definition was already close to an algorithm. Written out it is a scan over each pattern for each character and each depth, which is $\sigma \cdot w_{\max}$ scans; written as a sweep it is one marking pass over the patterns per character and then a single backward walk over the depths carrying the nearest mark. Same asymptotics in the pattern length, a constant factor apart.

That contrast is the useful part. Two tables, one definition each, and one of them was a definition that happened to be an algorithm. Nothing about the way they are stated says which, and the factor between the two collapses is eighty.

The vacuous case, and the ceiling it produces #

The third case is worth two paragraphs because it is where the shift’s ceiling comes from and because it is the one place the arithmetic is not a data-structure argument.

When $d \ge |r|$ for some pattern $r$, the range of $t$ is empty and the condition is satisfied by nothing having to match. Since $|r| \ge w_{\min}$ for every pattern, $d = w_{\min}$ always works — so the exact shift is never more than the shortest pattern’s length, whatever the alphabet, whatever the text, however many patterns there are.

The ceiling the shortest pattern sets is the essay about what that costs in practice: one short pattern added to a set of long ones collapses every shift in the run to its length. The construction here inherits the ceiling unchanged — it is the third argument to the min — and it is worth noticing that the ceiling is the only part of the exact rule that never needed computing.

What is now linear and what that means #

Steps per character of the total pattern set, across a 128-fold growth:

• the published rule: 5.1, 5.3, 5.1, 5.1, 5.0, 4.8, 4.7, 4.4
• the exact rule from the links: 12.0, 9.7, 8.5, 7.9, 7.6, 7.4, 7.3, 7.0
• the exact rule from the definition: 20.7, 29.7, 45.7, 74.4, 121.7, 203.2, 359.2, 601.3

Two flat rows and one that climbs by a factor of twenty-nine. “Linear in the total pattern length” is now true of the exact rule as well, measured the same way the published rule’s linearity was measured — which is what makes the third row a fact about an implementation.

The automaton that makes the skipping matcher cheap #

There is a dependency worth naming here that is pleasing and is not usually stated.

Every part of this construction runs on the failure links of the trie of reversed patterns — which is the Aho-Corasick automaton, the structure one pass for every pattern at once builds for a matcher that never skips. The matcher that reads every character of the text once is what makes the matcher that skips affordable.

The published rules already depended on that, and this construction depends on it twice over: the failure children give case one, and the failure chains from the terminal nodes give the suffix relation for case two. Both are one breadth-first pass and a few walks.

So a Commentz-Walter matcher is an Aho-Corasick automaton with a shift function bolted on, and the shift function — exact or published — is computed from the automaton’s own links. That is a stronger statement than “they are related structures”: the expensive-looking rule is a two-line derivation from a table the cheap structure already has.

What it does not make cheap #

The construction is linear in the total pattern length; the scan it enables is unchanged, and that is the point of the whole ladder rather than a caveat.

What the approximation gives up measures the two rules’ scans: identical from thirty-two patterns up, and at most 6.3% apart below it. Nothing here changes a single shift decision — the exact rule skips exactly as far as it always did, and the published rule falls exactly as far short.

What changes is which of the two a reader should build, and that is decided by precomputation plus scan against the length of the text. The fourth essay on this ladder is that arithmetic, redone.

Why nobody built it #

Worth guessing at, because the guess is instructive.

The published rules are safe approximations whose whole selling point is that they can be built in linear time. Once a paper has established that, the exact rule becomes the thing being approximated — a definition, quoted to show what the approximation gives up, and never something anybody proposes computing.

So the exact rule got a definition and no construction, not because a construction is hard but because there was no reason to want one. The definition is short and correct and it is what everybody writes down; the fact that evaluating it is quadratic in the pattern set is a property of the writing rather than of the rule, and nothing in the literature had cause to notice.

This collection had cause, because it measured the definition and reported the measurement as a property of the rule. That is the error, and the definition is not the algorithm is the thread it produced.

The check that makes any of this usable #

Two constructions of one table are two chances to be wrong, and the only thing that makes the cheap one usable is that the expensive one is still there.

commentzWalter takes a construction option, defaulting to the definition. The link construction is selected explicitly, and the gate requires the two to agree at every node and every character across six pattern-set sizes — 2,180 decisions — before any number from either is reported.

That is deliberately the same arrangement the published rules already had: the shift somebody published computes $d_1$ and $d_2$ from the links and checks them against a quadratic enumeration of the same definition, on the grounds that “an identity nobody checks is a comment”. This ladder adds a second identity of the same kind.

The cost of keeping the reference is that the definition remains the default, so every number this collection published earlier about the exact rule’s precomputation is still the number this file produces. A construction that replaced the reference would have silently rewritten a measurement, which is a worse outcome than a slow default.

Where else this collection has measured a definition #

The thread this produced has three members already and they were all found the same way — by building a second implementation of something that had only ever had one.

The table that walks every pair is this one’s parent and its subject is the quadratic construction itself, which is real and is still 769,724 steps.

The candidates a filter cannot avoid is the same shape one ladder over: an intersection implemented as the definition of an intersection — walk one set, test membership in the other — measured at 4,355 candidates for 32 occurrences, against a range query that answers it in 33.

And the cost is the number of subproblems is the version this collection has had since its table field opened: the cost of a dynamic program is the number of cells its definition names, and a method that visits fewer is not a faster version of the same algorithm.

In each case the definition was the honest first implementation, the measurement of it was correct, and the sentence attached to the measurement said something about the problem that was true only of the code.

The 198 is not a constant #

The deferral this page answers asked for a construction that would collapse this strand’s largest ratio to a constant factor, and it is worth separating which ratio collapsed, because two are in play and only one of them did.

The ratio between the two rules’ constructions does collapse: the exact tables now cost about 1.6 times the published ones on four-symbol text, flat across the sweep. That is the deferral’s question and the answer is yes.

The ratio between the two exact constructions does not. It is 198 at 128 patterns, and 198 is a value at a point rather than a factor.

The reason is that the two are in different classes. The link construction is two linear passes — a failure-chain walk per pattern and a running minimum down the trie — so its cost per character of pattern is flat, at seven steps. The definition is a loop over offsets inside a loop over patterns inside a loop over nodes, so its cost per character grows with the set: 601 steps a character at 128 patterns, and still climbing at the right-hand edge of the sweep.

That makes the definition roughly quadratic in the total pattern length where the links are linear, so the gap between them widens without bound. A thousand ten-character patterns puts the definition in the tens of millions of steps and the links at about seventy thousand — a ratio in the hundreds, arrived at by the set growing rather than by anything changing.

So the honest headline is not a factor of 198. It is that the definition was never linear and the algorithm is, which is a stronger claim and the one the table that walks every pair was reaching for when it concluded that preprocessing quoted as linear is true of one rule and false of the other. It was false of one construction of one rule, and the rule itself is linear — which is the whole of what the definition is not the algorithm means, and the reason the shift somebody published’s approximation turns out not to have been buying what it appeared to buy.

What is being claimed #

The exact good-suffix condition has exactly two non-vacuous cases, one where the known segment lies inside a pattern and one where it runs off the end.

The first case is the published rule’s $d_1$, which is the failure-link relation, so the two rules share it exactly — the exact rule is not an expensive quantity the published one estimates, it is the same quantity with one more case and without the guard.

The second is computed in two linear passes — one failure-chain walk per pattern, and one running minimum down the trie.

The construction agrees with the definition at every decision, checked at 2,180 of them across six set sizes.

And it costs 3,824 steps against 757,058 at 128 patterns, which is 7.0 steps per character of pattern against 601.

What it does not change is a single shift. The tables are identical, so the rule skips as far as it did, reads what it read, and finds what it found — which is what makes the whole result about construction rather than about matching.