Where the exact rules pay now

The rule that pays on a long enough text asks the question a library actually faces: given a pattern set and a text, which shift rule should be built? The answer is a crossing — precomputation is paid once and the scan is paid per character, so the rule that skips further wins on a long enough text and loses on a short one.

That essay computed the crossing with the exact rules built from their definition. The table the links already knew makes them 86 times cheaper to build, and the ratio that was an implementation fixes the accounting on the other side. This essay is the arithmetic redone.

The crossings #

Two patterns of ten characters over four symbols, both rules built and then run on texts of increasing length. The total is precomputation plus characters read.

The crossing is at eight thousand characters. Built from the definition it is at thirty-two thousand; the construction moves it by a factor of four.

Both sides of that table are running the same scan — the same windows, the same shifts, the same characters read — so the whole movement is in the constant added before the first window. A plate of this shape always looks like two nearly-parallel lines, and everything interesting about it is where they touch.

At four patterns the crossing is at four thousand characters with the construction and sixty-four thousand with the definition — a factor of sixteen. At eight patterns and above there is no crossing at any length in the sweep, with either construction, and the reason has nothing to do with construction cost.

Why thirty-two patterns never crosses #

Because the two rules make identical decisions there.

What the approximation gives up measures the published rule against the exact one at every decision in its domain, and finds them identical from thirty-two patterns up: 3,736 (node, character) pairs, zero differences. At sixteen patterns two of 552 differ; at two patterns five of 84.

So the scans are the same, the exact rule reads exactly what the published rule reads, and its extra construction is never earned back. There is no length of text at which a difference of zero amortises anything. A crossing exists only where there is a scan difference to amortise, and the scan difference exists only on small sets.

Which is the shape of the whole result. The exact rules skip further exactly where both rules are cheap to build, and cost more to build exactly where they skip identically. The two effects cancel almost perfectly, and the residue is a crossing at a few thousand characters on very small sets.

What the construction actually changed #

Not the answer to “which rule should a library build”. That is still the published one, for the reasons the earlier essay gives and which are unchanged: the exact rules are within 6.3% on the worst set in the sweep, identical on most of them, and a library handed an arbitrary set cannot know which it has.

What changed is the reason. The old answer was “the published rules, because the exact ones are unbuildable at any realistic set size”. The new answer is “the published rules, because the exact ones buy nothing at any realistic set size”. Those are different arguments and only the second one survives.

The difference matters for anybody extending the work. If exactness were unbuildable, the research direction would be a cheaper construction. It is not: the construction is linear and it exists. The direction that would matter is a rule that skips further than exact — which is impossible, since exact is the largest safe shift — or a different matcher altogether.

Before the crossing can be argued about it is worth knowing which half of the construction the saving came out of, because the two tables are not the same problem and only one of them was ever expensive.

Why eight patterns is where it stops #

The pattern count at which the crossing disappears is worth one paragraph of mechanism, because it is not a threshold anybody chose.

The two rules differ at a decision when case two of the exact condition — the known segment hanging off the end of a shorter pattern — permits a shift the published rule’s guard does not. That requires a pattern short enough and a segment long enough to overhang it, and both become rarer as the set grows: more patterns means a deeper trie, more failure children per node, and therefore a smaller $d_1$ that already sits below whatever case two would have offered.

So the exact rule’s advantage is a property of sparse pattern sets, and a set of eight random ten-character patterns over four symbols is already dense enough that case one dominates almost everywhere. Add patterns and the two rules converge; the convergence is measured at 3,736 identical decisions from thirty-two patterns up.

That is a satisfying reason for a threshold rather than a fitted one, and it makes a prediction: a set of long patterns over a wide alphabet stays sparse for longer, so the crossing should survive to larger set sizes there.

It does. On sixteen-character patterns over a twenty-six symbol alphabet the crossing has vanished at two, four and eight patterns — and reappears at sixteen, at 128,000 characters of text. The direction is the predicted one and the mechanism is visible in the same numbers: on that alphabet a sixteen-character pattern’s trie is wide and shallow, case one has few candidates, and case two keeps mattering for longer.

That last measurement is also a correction to this ladder’s headline. The 1.6 multiple is on four-symbol text with ten-character patterns; on twenty-six symbols with sixteen-character patterns it is 5.5 to 6.9, flat across the sweep. The construction is linear in the total pattern length on both, at 7.0 steps per character on one and 30 to 34 on the other, and the difference is the bad-character table, whose sweep costs one pass per alphabet symbol.

The case where the exact rules do win #

Two patterns, a long text, and a set the library was told about in advance.

That is a real case: a virus scanner with two signatures against a disk image, a log filter with a handful of fixed strings against a terabyte of logs. The saving is 6.3% of characters read at two patterns, and 6.3% of a terabyte is real work — sixty gigabytes of characters not examined, for eighty-nine extra steps of preprocessing.

The construction matters there in a small way and a large one. Small: the crossing moves from 32,000 characters to 8,000, which for a terabyte is irrelevant. Large: the exact rules can now be built for a set of a thousand patterns, which the definition could not — 601 steps per character of pattern at 128 patterns and still climbing means a thousand ten-character patterns would cost tens of millions of steps, and at 7.0 per character it costs seventy thousand.

So the construction converts “exact is available on tiny sets” into “exact is available on any set”, and the measurement then says the large sets do not want it. That is a satisfying place to end up: the option is now real, and the reason not to take it is a property of the rules rather than of an implementation.

What a specialist should do, which is different #

A library and a specialist face different problems and the same measurement answers both differently.

A library is handed a set it did not choose and a text it cannot see. It has to pick a construction from the set alone, and the numbers above say: build the published tables, because on eight or more patterns the exact ones are identical and on fewer than eight the crossing may or may not be reached.

A specialist knows the set and the text. Two fixed patterns against a corpus of a gigabyte is a case where the exact rules read 6.3% fewer characters, the construction difference is eighty-nine steps, and the crossing was passed at the eight thousandth character. Building the exact tables there is free money.

The interesting middle case is a specialist with a large set and a long text, and the measurement says there is nothing there: at thirty-two patterns the two rules make the same decisions, so the exact tables read exactly what the published ones read and cost 812 more steps to build. Not a loss worth avoiding, and not a gain.

So the decision procedure is one line longer than the earlier essay’s: if the set has fewer than eight patterns and the text is longer than a few thousand characters, build the exact tables; otherwise build the published ones and stop thinking about it.

The decision, as a library would make it #

Three numbers, all computable before any text is read.

The pattern count. At eight and above, the two rules skip near-identically on random sets and there is no crossing at any text length — build the cheap tables, and the exact ones would be a pure loss of construction time.

The construction difference. For a small set it is a few hundred steps: 195 against 106 at two patterns, 339 against 206 at four. Computable from the set’s size and the shortest pattern’s length without building anything.

And the expected text length. The crossing is the construction difference divided by the fractional scan saving, which is about 6% at two patterns. Eighty-nine steps over 0.06 of a character saved per character examined gives roughly fifteen hundred characters examined, and the matcher examines about 0.65 characters per character of text — so about two thousand three hundred. The measurement puts it at eight thousand, which is the same statement with the constants measured rather than rounded.

That the estimate is off by a factor of three is worth noting rather than hiding. The scan saving is not constant across text lengths — a short text has proportionally more window starts near its beginning, where the shift rules have less to work with — so the fraction saved on five hundred characters is not the fraction saved on sixty-four thousand.

The factor of three, taken apart #

That discrepancy is worth a paragraph of arithmetic rather than a hypothesis, because the table above contains enough to resolve most of it and the resolution changes what a reader should do with the estimate.

Part of it is the sampling. The crossing is not at eight thousand characters; eight thousand is the first row where the exact total is lower. At four thousand the exact rules are 17 steps behind and at eight thousand they are 60 ahead, so they gain 77 over that interval and the crossing sits at about 4,900. The estimate of 2,300 is therefore off by 2.1, not by 3, and a third of the gap was a plate’s grid rather than anything about the algorithm.

The rest is the saving rate, and it is exactly a factor of two. Between those two rows the exact rules gain 77 steps over 4,000 characters of text — 0.0192 a character. The estimate used 6.3% of characters examined at 0.65 examined per character of text, which is 0.0389 a character. Divide 89 steps by the measured rate instead and the crossing lands at 4,600, against the 4,900 the interpolation gives. The estimate’s method was right and the number it was fed was double the truth.

So the explanation offered — that a short text has proportionally more window starts near its beginning, where the rules have less to work with — is the right shape and is not sufficient. It predicts a rate that climbs with text length and converges on 0.0389, and the rate does climb: between sixteen thousand and sixty-four thousand characters the exact rules gain 1,182 steps over 48,000, which is 0.0246. But that is still 63% of the asymptotic figure at the far end of a sweep spanning two orders of magnitude, so whatever is suppressing the saving is larger and slower than a boundary effect on the first few windows.

The practical consequence is a correction to the decision procedure above, and it generalises past this ladder. A crossing estimated from a saving measured far past the crossing is optimistic, and here by a factor of two. The scan advantage a rule shows on twenty thousand characters is not the advantage it has at five thousand, and the crossing is by construction a statement about the short end. The rate to divide by is the marginal one near the crossing, which means the estimate needs the very measurement it was trying to avoid.

What rescues the estimate is that being wrong by two in the crossing rarely changes a decision. The specialist case is a gigabyte and the crossing is five thousand characters or ten; the library case is eight patterns or more, where there is no crossing at all. The band where a factor of two matters is a text of a few thousand characters with two patterns, and that is a text a naive scan would finish in the time spent deciding.

Which is the honest reading of what the approximation gives up’s 6.3% arriving here as a crossing: the percentage is a property of the rules on a long run, the crossing is a property of the rules on a short one, and converting between them takes a rate that is itself a function of the length. The rule that pays on a long enough text drew the curve rather than quoting a ratio, and this is why.

The shape of the arithmetic, and where else it appears #

A cost paid once against a cost paid per unit, with a crossing between them, is the most common shape in applied algorithm choice and this collection has met it four times.

The rule that pays on a long enough text is this one’s parent: two shift rules, a construction against a scan, a crossing in characters of text.

What a second pass buys is the streaming version: a second pass over the data against the space a one-pass structure needs, and a crossing in how much state can be held.

A bound that has to be paid for, one ladder over, is the awkward version: the fixed cost is space rather than time, so the crossing is in the number of queries and there is no rate between the two that a measurement can supply.

And choosing a growth factor is the version where the fixed cost is a reallocation and the variable one is wasted memory.

What distinguishes them is what the crossing is in: characters of text, bits of state, number of queries, number of appends. In every case the answer is a curve and the recommendation is a default, and in every case the default is defensible only because somebody measured where the curve crosses.

What did not change #

Every number about the scan is unmoved, and it is worth repeating because this ladder has moved so much else.

The exact rules read 12,306 characters per twenty thousand at two patterns; the published rules read 13,084. Identical at thirty-two patterns and above. The mean shift, the coverage, the number of windows — all unchanged, because nothing on this ladder alters a single shift decision.

What moved is entirely in the column that is paid once. That is the cleanest possible form of a correction: one term of a two-term sum was wrong, and the other term is what the algorithm is actually about.

The honest limits of the crossing measurement #

Three, and the first is the one that would move the numbers most.

The pattern sets are random and distinct. patternSet draws patterns uniformly and requires them to be distinct and non-nesting, which is the case where the two shift rules agree soonest — a set of patterns sharing long suffixes has a deeper trie and different behaviour. Real pattern sets are not random: a virus scanner’s signatures share structure, and a set of English words shares suffixes heavily.

The text is uniform over its alphabet. A text with structure has different shift behaviour, and the scan difference between the two rules — the thing being amortised — is measured on the uniform case.

And the crossing is in primitive steps of two different kinds. A character comparison during precomputation and a character read during a scan are both counted as one, which the earlier essay flagged and which stands: the ratio being measured is small enough that an exchange rate of two or three either way would move the crossing by that factor and not change the conclusion. It would not survive an exchange rate of forty, and nothing here rules one out.

What is being claimed #

With the link construction the exact rules pay for themselves past 8,000 characters at two patterns, against 32,000 with the definition — a crossing moved by a factor of four.

At four patterns the crossing is 4,000 characters against the definition’s 64,000; at eight and above there is none with either construction, because the two rules make near-identical decisions there.

The recommendation is unchanged and its reason is not. A library builds the published tables because the exact ones buy nothing on the sets it will be handed, not because they cannot be built. That is a better answer than the old one for a reason worth stating: an argument from impossibility is overturned by anybody who builds the thing, and an argument from measurement is not.

And the exact rules are now available at any set size. Seventy thousand steps for a thousand patterns, where the definition would have cost tens of millions — which is what makes “they buy nothing” a measurement rather than a hypothesis.

The multiple over the published rule is 1.6 on one alphabet and 6 on another, both flat across their sweeps, so even the corrected ratio is a two-parameter quantity and not a constant.