The table that walks every pair

Both sets of shift tables are computed before the text is read, and both are computed from the same trie. One of them costs 5,604 primitive steps at 128 patterns and the other costs 769,724.

The scan those tables exist to make cheap reads 41,580 characters. So the exact construction is eighteen times the whole scan, and the published one is thirteen per cent of it.

The two constructions #

The exact rules are a definition. For a trie node and each candidate shift, walk every pattern at every offset and ask whether the segment already read lines up. That is $O(k \cdot w_{\min} \cdot \mathrm{depth})$ per node — the shape what O-notation does not say would have this collection measure rather than quote and there are $O(k \cdot m)$ nodes, so the whole thing grows faster than the pattern set does.

The published rules are two passes over the trie’s failure links. $d_1$ at a node is the least depth increase to a failure child; $d_2$ is the same restricted to nodes that end a pattern, computed deepest-first and then inherited shallowest-first. Every node is visited a constant number of times.

The measured counts follow: across sets of 1, 2, 4, 8, 16, 32, 64 and 128 patterns, the published construction costs 51, 106, 203, 407, 800, 1,547, 3,004 and 5,604 steps. Each is almost exactly twice the one before it, which is what a linear construction does when the set doubles.

The exact construction costs 207, 594, 1,828, 5,952, 19,467, 65,037, 229,881 and 769,724. Each is about 3.3 times the one before.

Per character of pattern, which is the fair denominator #

A set of 128 patterns of ten characters is 1,280 characters of pattern, and a construction whose cost is linear in that is the claim to test.

The published construction: 5.1 steps per character of pattern at four patterns, 4.4 at 128. Flat across a thirty-two-fold growth, which is what “linear in the total pattern length” means measured rather than asserted.

The exact construction: 45.7 steps per character at four patterns, 601 at 128. A factor of thirteen, still climbing at the top of the sweep.

The plate asserts both halves — that the published figure is within a factor of two of itself across the sweep, and that the exact one grows by at least four — because a plate showing one line flat proves nothing without the other line beside it.

The construction is compared against itself, too #

The published tables have a definition as well as an algorithm, and this collection computes both.

$d_1$ and $d_2$ are defined over the suffix set of a node — every node whose word has this one’s word as a proper suffix — and the definition can be evaluated directly by testing every pair of nodes. That is quadratic in the trie and it is what the linear construction has to agree with.

Measured on three sets: 226 steps against 289 at two patterns, 474 against 1,089 at four, 885 against 3,481 at eight. The linear route is already four times cheaper at eight patterns, and the two agree at every node of every one of the three tries.

That check is what makes the failure-link identity a claim rather than a citation. It is the same discipline a search that runs backwards applies to the transform’s own identity, and it is cheap because the quadratic version is only unaffordable at sizes the check does not need.

Eighteen times the scan #

The number that makes this an essay rather than a table is the comparison against the scan.

At 128 patterns the exact construction is 769,724 steps and the scan it enables reads 41,580 characters. The tables cost eighteen and a half times what they save, on a text of twenty thousand characters — and this collection measured the same shape at seven times on a smaller sweep, in the essay that built the exact rules.

That is not an argument against the exact rules; it is an argument about where the balance sits, and the balance moves with the text length. A pattern set used against a megabyte amortises the construction to nothing.

What it does say is that a benchmark quoting a skipping matcher’s cost as “characters examined” is quoting the smaller half of the bill at any realistic pattern-set size on a short text. The count somebody chose is this collection’s standing complaint about exactly that, and the construction cost is the term most often left out of a matcher’s account.

Why the exact construction grows faster than the set #

The shape is worth deriving because “quadratic” is not quite right and the plate’s slope says so.

For each of the trie’s nodes, the exact good-suffix computation tries each candidate shift from one up to the shortest pattern’s length, and for each shift it walks every reversed pattern comparing up to the matched length. So the cost per node is bounded by $w_{\min} \times k \times \mathrm{depth}$, and the node count is itself about $k \times m$ for a set with little sharing.

That gives something like $k^2 m^2$, and the measured growth from 64 to 128 patterns is 3.35 — between the 2 a linear construction gives and the 4 a quadratic one does, because the trie stops growing linearly once the patterns start sharing prefixes.

So the exponent is not clean, and this collection does not fit one to it. Eight points that grow by factors of 2.9, 3.1, 3.3, 3.3, 3.3, 3.5 and 3.3 are a measurement of a construction on one family of pattern sets, and reporting an exponent would be reporting the family.

The ratio is a function of the sweep #

One caution about the headline: 137 is not a property of the two constructions, it is the ratio at the right-hand end of one sweep.

At one pattern the exact construction costs 207 steps against 51 — a ratio of 4.1, and a reader stopping there would conclude the two are within a small factor. At four patterns it is 9.0, at sixteen 24.3, at sixty-four 76.5 and at 128 it is 137.4.

So what the plate establishes is a widening, and the assertion behind it demands exactly that rather than a threshold: the ratio at the top of the sweep must be at least twice the ratio at the bottom. A fixed threshold would have to be re-chosen every time a plate was drawn over a different range, which is how a gate acquires a tuned constant.

Extrapolating the widening is a different matter and this collection does not do it. What the eight points support is that the gap grows; where it reaches a hundred, or a thousand, is arithmetic on an exponent nobody has fitted.

The unit, and what it is not #

Both constructions are counted in primitive steps and the two kinds of step are not identical, which the plate’s axis label says and this section states plainly.

The exact construction’s step is a character comparison: two symbols tested for equality. The published construction’s step is a node visit: following a failure link, or reading a child’s depth.

Those are not the same act on a machine, and this collection’s rule is not to sum unlike counts. The plate puts them on one axis because both are the primitive operation of their own construction and the question being asked is how many of anything each performs — the same compromise one run, two counts allows when two counts are both operations on the same structure at the same level.

The factor between them on a real machine is small — both are a memory read and a comparison — and the ratio being measured is 137, so the conclusion survives an exchange rate of two or three either way. It would not survive an exchange rate of a hundred, and nothing here rules one out.

What a linear construction makes possible #

The practical consequence is not that the published rules are cheaper. It is that they can be built at all at sizes where the exact ones cannot.

At 128 patterns of ten characters the exact construction is three quarters of a million steps, which is fine. At 10,000 patterns — a virus signature set, a dictionary — the same growth gives something on the order of $10^{10}$, which is not. The published construction at that size is about a million and a half, which is a fraction of a second.

So the two rules are not competitors across the whole range. Past a set size, only one of them exists, and the essay that measures where the other consideration crosses — how much text makes the extra skipping worth the extra construction — only has a question to answer below that size.

That is the rule that pays on a long enough text, and its crossing turns out to exist only at two and four patterns.

Where the construction sits in a real run #

It is worth assembling the whole bill once, because the two halves are usually reported by different people.

For 128 patterns of ten characters against twenty thousand characters of four-symbol text: the published rules cost 5,604 steps to build and 41,580 characters to scan, for a total of 47,184. The exact rules cost 769,724 to build and 41,580 to scan — identical scans, as what the approximation gives up measures — for a total of 811,304.

Thirteen and a half times the total, for the same answer found by reading the same characters.

At two patterns the picture is the one the trade suggests: 300 and 13,084 against 594 and 12,306, so the exact rules are ahead on the total from about sixteen thousand characters of text onward.

Two regimes, and the boundary between them is a set size rather than a text length. Below about eight patterns the exact rules skip further and can pay for themselves; above it they skip identically and cannot.

A bound that is about the right thing #

It is worth noticing that this essay’s headline is a construction cost, which is the quantity asymptotic analysis of string matching usually treats as a footnote.

The classic statements are about the scan: Aho–Corasick reads the text once, Commentz-Walter reads a fraction of it, Boyer–Moore is sublinear on a wide alphabet. Preprocessing is quoted as “linear in the total pattern length” and moved past — which is true of the published rules and, as this essay measures it, false of the exact ones by a factor of 137 at a set size a real application would use. That last clause did not survive: the table the links already knew builds the same exact tables from the trie’s failure links in 3,824 steps, so the quadratic behaviour measured here is a property of this construction and not of the rule.

The model a bound was quoted in is this collection’s general form of that complaint. Here the model is not wrong; the accounting is incomplete, and the missing term is the larger one at every text length below about a million characters.

The check that must hold, and the one that must fail #

Two assertions carry this measurement.

The first is that the published construction’s cost per character of pattern stays within a factor of two across the sweep while the exact one’s grows by at least four. Both halves are needed: a construction that had stopped building anything would be perfectly flat.

The second is the agreement between the linear tables and the definition, at every node, which is what says the cheap construction is computing the right thing. A cheap construction computing something else would be cheaper still.

And the rejection test raises the good-suffix table to its ceiling everywhere — the change a plausible optimisation would make — and requires the exhaustive comparison to catch the resulting missed occurrences. Two occurrences reported where there are eight.

What this leaves undone #

Two things are named here and not measured, and both are the sort that turn into a strand.

The suffix-link construction of the exact rules. Nothing proves the exact good-suffix condition needs a walk over every pattern at every offset; the single-pattern version of it is computed in linear time by a classical construction, and whether the multi-pattern one has an equivalent is a question this collection has not asked. If it does, the whole comparison in this strand collapses to a constant factor.

The large pattern set. Every measurement stops at 128 patterns because the exact construction is three quarters of a million steps there and grows by 3.3 per doubling. The regime a real signature matcher works in — thousands of patterns — is exactly where the published rules’ linearity is the whole story, and it is a regime this collection can measure on one side only.

Naming them here is deliberate. The shift a set of patterns allows left the published rules unmeasured with a sentence, and that sentence is what this strand was built from.

What a linear exact construction does to every number here #

The deferral named at the end of this page — whether the exact rules have a construction that does not walk every pair — was taken, and the answer is yes. The table the links already knew computes the same exact tables from the trie’s failure links in 3,824 steps at 128 patterns. That is worth carrying through the whole page, because it does not soften a single number above; it inverts the conclusion they were assembled to support.

Take the comparisons in order.

The headline ratio of 137 becomes 0.68. The exact rules, built through the failure links, cost less than the published approximations do — 3,824 against 5,604 — because the published construction here walks failure children explicitly rather than building them in one pass, and both are now linear in the same structure.

“Eighteen times the scan” becomes nine per cent of it. The tables are no longer the larger half of the bill; they are a rounding error against 41,580 characters of scanning.

The whole-run accounting reverses. The published route totals 5,604 plus 41,580, or 47,184. The exact route now totals 3,824 plus 41,580, or 45,404 — cheaper overall, for tables that skip at least as far at every node. There is no longer a trade to be made.

And the two-regime conclusion goes with it. This page ends by saying that below about eight patterns the exact rules can pay for themselves and above it they cannot; with a linear construction they pay for themselves everywhere, and the rule that pays on a long enough text is answering a question that only existed while the construction was superlinear. Its crossing was real about the constructions measured and is not a fact about the rules.

What survives is worth being just as precise about, because it is not nothing.

Every measurement on this page is still exact about the construction it measured. 769,724 steps at 128 patterns, growing by 3.3 a doubling, is what a definition-shaped construction costs, and the definition-shaped construction is still the reference the fast one is checked against at every node. That is the arrangement the strand deliberately keeps.

And the general complaint stands. A matcher’s account that omits its preprocessing is incomplete, and the omitted term was the larger one here for as long as the only available construction was this one. The correction is that the term’s size is a property of an implementation rather than of a rule — which is a sharper version of the same warning, since an implementation is the thing a reader actually runs and is the thing nobody publishes a bound for.

The lesson to carry, then, is not the 137. It is that a superlinear cost measured on the only construction available is a measurement of that construction, and that the sentence this page closes with — if it does, the whole comparison in this strand collapses — was the right thing to write down, because it named the one measurement that would overturn the essay and somebody then took it.

The honest limit #

The two counts are in different primitives, as above, and no exchange rate between them is established. A reader who wants the comparison in one currency will have to supply one, and the ratio is large enough to survive small ones.

The pattern sets are drawn uniformly at random with no member a substring of another. A real set with heavy prefix sharing gives a smaller trie, which makes both constructions cheaper and the exact one relatively more so, since its cost is superlinear in the node count.

And the failure-link construction here walks failure children explicitly rather than building them with the standard queue in one pass, so the published side’s constant is larger than a careful implementation’s. That makes the measured 137 a lower bound on the ratio, which is the safe direction for the essay’s claim.