The rule that pays on a long enough text

Two shift rules, one matcher, one question: which is cheaper. The two previous essays answer it in halves — the exact rules skip a little further, the published rules are built far more cheaply — and neither half is a decision.

Add them. With two patterns of ten characters over four symbols, on five hundred characters of text: 389 steps for the published rules against 874 for the exact ones. On thirty-two thousand: 18,334 against 18,139.

The order has reversed, and the thing that reversed it is the amount of text.

Adding two counts, with the reason stated #

This collection does not sum unlike counts, so a plate that adds a preprocessing cost to a scan cost has to justify itself.

Both terms here are character comparisons. The exact construction compares symbols of the reversed patterns against each other; the scan compares text characters against trie edges. Neither is a rank, a cell or a cache miss, and both are the same act on the same kind of data.

That makes the sum meaningful in a way that adding cells to reads would not be. The plate says so on its axis, and the two terms are drawn separately in the table that walks every pair and in what the approximation gives up so that a reader can see which is which.

The published construction’s steps are node visits rather than character comparisons, which is the one place the sum is loose; the essay before this one takes that up, and the ratio being measured survives an exchange rate of two or three.

The crossing, and where it is #

At two patterns the totals run: 389 against 874 at five hundred characters, 697 against 1,167 at a thousand, 1,254 against 1,718 at two thousand, 2,393 against 2,811 at four thousand, 4,673 against 5,014 at eight thousand, 9,177 against 9,357 at sixteen thousand, and 18,334 against 18,139 at thirty-two thousand.

The lines cross between sixteen and thirty-two thousand characters. Below it the cheap tables win because their saving in construction exceeds their loss in scanning; above it the loss in scanning — 6.3 per cent of a growing number — exceeds a fixed saving of 488 steps.

The arithmetic is a division. The construction difference is 488 steps and the scan difference is about 6.3 per cent of the published scan, so the crossing is where 0.063 × scan = 488, which is a scan of about 7,700 characters examined — and the scan examines about 0.65 characters per character of text, so about twelve thousand characters. The measurement puts it between sixteen and thirty-two thousand, which is the same statement with the constants measured rather than rounded.

Both of those numbers are the definition-shaped construction’s. Where the exact rules pay now redoes the arithmetic with the exact tables built from the trie’s links, where the construction difference is 89 steps and the crossing falls to eight thousand characters.

At four patterns it is at the edge, and at thirty-two it does not exist #

The crossing is a property of the pattern set as much as of the text, and it disappears quickly.

At four patterns, the totals at thirty-two thousand characters are 25,237 against 25,621 — the cheap tables are still ahead, by one and a half per cent, at the top of the sweep. The crossing is somewhere past it.

At thirty-two patterns there is no crossing at any length. The scans are identical to the character, so the exact rules’ 65,037-step construction buys nothing at all, and the totals run 2,391 against 69,605 at five hundred characters and 48,379 against 115,593 at thirty-two thousand. The gap narrows in proportion and never closes.

So the honest summary is: the exact rules can pay for themselves on one, two or perhaps four patterns given enough text, and cannot on more.

Why this is in the practice field #

The field this sits in is about what actually ships, and the shipping decision here is not the one the two previous essays set up.

A real matcher does not choose between two shift rules on a fixed pattern set and a fixed text. It is a library, it is handed sets and texts it did not choose, and it has to pick a construction without knowing either. Given that, the published rules are the only defensible choice: they are within 6.3 per cent on the worst set in this sweep, identical on most of them, and buildable at set sizes where the alternative is not.

That is why they are the ones that shipped, in 1979 and since. The measurement here does not overturn it — it prices it, which is a different job, and one this collection’s the sort the library ships does for a sorting policy in the same spirit.

The other half of the practice argument is that a library’s cost model has a term nobody in the theory has: the set is used many times. A pattern set compiled once and matched against a stream amortises any construction to nothing, and then the 6.3 per cent is the whole decision.

What the one-pass matcher does to the decision #

There is a third algorithm in this comparison and leaving it out would make the essay a choice between two rules when it is a choice among three.

Aho–Corasick reads every character of the text exactly once, whatever the pattern set, and its construction is linear in the total pattern length — the same failure links the published shift rules are computed from. So its bill on twenty thousand characters at 128 patterns is a construction of the same order as the published rules’ and a scan of exactly twenty thousand.

The skipping matcher at that set size examines 41,580 characters and touches 17,405 distinct positions. In examined characters it is twice as expensive; in distinct positions it is thirteen per cent cheaper. Which of those a machine feels depends on whether the text is in cache, and this collection measured that pair when it first built the skipping matcher, and refused to declare a winner.

So the practical decision has three branches, not two, and the shift-rule question only arises after the skipping matcher has been chosen. On a large pattern set over a small alphabet it usually should not be.

The shape is a crossover, and this collection has a name for it #

A fixed cost paid once against a marginal cost paid per unit is the commonest shape in this whole collection, and it always resolves into a length.

Where insertion sort actually wins is the founding instance: a quadratic sort with a small constant beats a linearithmic one with a large one, below a size the measurement finds and no analysis names. The threshold somebody chose is the same crossing seen as a number in a real source file.

What makes this one worth its own essay is that the fixed cost is preprocessing — a term that asymptotic analysis of string matching routinely quotes as linear and moves past, because it is linear for the rules that ship and is not for the rules that are exact.

And the crossing sits at a text length a real application would pass in a moment. Thirty-two thousand characters is a small file. So the practical answer for one or two patterns is that the exact rules win, and the practical answer for a hundred patterns is — as this essay had it — that they cannot be built. The second half of that did not survive: they can, in linear time, and the reason not to build them turns out to be that they buy nothing rather than that they cost too much.

What a library would do with three numbers #

The decision can be made from quantities available before anything runs, which is what makes it a rule rather than a benchmark.

The pattern count. Above about eight, the exact rules skip identically on random sets and the decision is made — build the cheap tables.

The construction difference. For a small set it is a few hundred steps, computable from the set’s size and the shortest pattern’s length without building anything.

The expected text. If the set will be matched against more than a few tens of thousands of characters, the exact rules’ extra skipping outruns their construction; below that it does not.

None of those needs a timing run and all three are integers a caller either knows or can estimate. That is the same style of decision procedure three savings in three currencies arrives at for approximate matching in this same phase: compute what can be computed, measure the one thing that cannot, and choose.

What the plate cannot show #

The totals here are counts of primitive steps and a machine does not spend steps, so there are two things this plate would need to become a recommendation and does not have.

The first is a cost per step. A character comparison during preprocessing is a sequential read of two small arrays; a character comparison during a scan is a read of a text position that may be anywhere and a hash-map lookup on a trie node. On a real machine those differ by whatever the cache says, and this collection has a counter for that and has not pointed it here.

The second is the memory the tables occupy. The exact rules store one shift per node; the published rules store two per node plus a character table. Neither is large and neither is drawn.

So the crossing at thirty-two thousand characters is a crossing in acts. Where it sits in seconds is a different measurement, and the count is not the time is the essay that says why the two questions are not the same question.

The crossing moves with the alphabet #

One more parameter changes the answer and it changes it in the direction that makes the exact rules look better.

On a twenty-six-symbol alphabet every rule skips further, because the character table returns the maximum for most characters. The scan is a smaller number, so a fixed construction difference takes more text to amortise — and the exact rules’ construction is larger on a wide alphabet too, since the character table has more entries.

The measurement is at two alphabets and the shape holds at both. What it does not establish is a formula for the crossing in terms of $\sigma$, because two points and a mechanism are not a fit.

The check the plate carries #

The assertion behind the total plate is that the cheap tables win on the shortest text in the sweep. That is the half a bug would break: a construction cost accidentally left out of the total, or counted twice, would move the left-hand end.

The correctness precondition is the same one every plate in this strand carries — both rules must find exactly what exhaustive search finds, at every text length — and the plate refuses to draw if either misses an occurrence.

What is deliberately not asserted is the crossing’s position. It is a measurement that depends on the pattern set, the text and the alphabet, and asserting it would be pinning a number that this collection expects to move.

The set is compiled once and the text arrives forever #

The measurement above holds the pattern set and the text length fixed and varies one of them. A real deployment usually holds neither fixed and the asymmetry between them is the whole of what makes a construction cost tolerable.

A pattern set is compiled once — at startup, at deploy, when a signature list is updated — and then matched against everything that arrives. So the construction is a fixed cost per set change and the scan is a marginal cost per byte, and the ratio between how often each happens is a property of the deployment rather than of the algorithm.

At the extreme where a set is compiled once and never changed, only the scan matters, and the exact rules win on any set where they skip further at all — which the sweep says is sets of one, two, four and eight patterns. At the other extreme, a set built per query against one short document, only the construction matters, and the cheap tables win everywhere.

That is a second axis the plate does not have, and it is the one a practitioner is usually on. Sized for a rate that does not hold still is this collection’s standing note about parameters chosen for a workload that then changes; the same caution applies to a shift rule chosen for a text length.

The answer, in one paragraph #

For one or two patterns and a text over about thirty thousand characters, the exact shift rules are cheaper in total and the difference is a few per cent. For four patterns the crossing is past the top of this sweep. For eight or more, the two rules scan almost identically and the exact construction is a pure loss that grows by 3.3 for every doubling of the set.

A library handed an arbitrary set therefore builds the published tables, and a specialist matching two fixed patterns against a large corpus should consider the exact ones and will save a few per cent.

That is a smaller conclusion than “the published rules are a linear-time approximation” suggests, and it is the one the measurement supports.

The gap at thirty-two patterns is exactly constant #

The gap narrows in proportion and never closes is the right conclusion reached by the wrong description, and the arithmetic is worth doing because the exact version is a stronger statement.

At thirty-two patterns the totals are 2,391 against 69,605 at five hundred characters and 48,379 against 115,593 at thirty-two thousand. Subtract: 67,214 and 67,214. Not approximately — the same integer, across a sixty-four-fold increase in text.

The ratio narrows, from 29 to 2.4, and the gap does not move by a single step. That is the cleanest available demonstration of the claim the essay makes elsewhere: the two scans are identical to the character, so the difference between the totals is nothing but the construction difference, which was paid before the first window and is the same number forever.

The same two rows give a quantity nothing else on this page states. The published total rises by 45,988 over 31,500 more characters of text, so the scan examines 1.46 characters per character of text at this set size. That is above one, and it is the number that decides against the skipping matcher entirely at large sets — the one-pass matcher reads each character once, and the skipping matcher’s advantage in distinct positions is being bought at nearly half again as many examinations.

And once the gap is understood as a constant, the crossing stops being a range and becomes a division.

Crossing = construction difference ÷ scan saving per character of text.

At two patterns the gap runs from 485 at five hundred characters to $-195$ at thirty-two thousand, so the exact rules gain 680 over 31,500 characters — 0.0216 a character — and the gap reaches zero at about 23,000 characters. The sweep brackets it between sixteen and thirty-two thousand because those are the rows it has; the interpolation puts it near the middle of that bracket, and the number is available from two rows rather than from a finer sweep.

At thirty-two patterns the denominator is zero, so the crossing is at infinity. That is the same sentence as there is no crossing, and stating it as a division makes it a case of the rule rather than an exception to it.

The estimate offered above — 488 steps over 6.3% of a scan, giving twelve thousand characters — is therefore right in method and low by about a factor of two, for the reason where the exact rules pay now takes apart in detail: the 6.3% is measured on twenty thousand characters, the crossing is a statement about the short end, and the marginal saving near a crossing is smaller than the one a long run reports. The measured rate here, 0.0216 a character, is against the 0.041 that 6.3% of a 0.65 examination rate implies.

Which leaves the decision procedure shorter than the three numbers above. Take the construction difference and the scan difference from what the approximation gives up’s table, and divide. Where the second is zero there is nothing to decide; where it is not, the answer is one number and it needs no sweep at all.

The honest limit #

The sweep runs to thirty-two thousand characters because the exact construction at 128 patterns is already three quarters of a million steps and the plate needs both terms visible on one axis. A longer sweep would show the two-pattern lines diverging further and would not change the crossing.

The pattern sets are random with no member a substring of another. A set with shared suffixes gives the published rules smaller tables and the exact rules more work, which moves the crossing right — in the direction that favours the cheap tables further.

And the totals mix two kinds of primitive step on the published side, as the essay before this one records. The crossing at two patterns is between two numbers within two per cent of each other, so it is the measurement in this strand most sensitive to that looseness, and it is quoted as a range between sixteen and thirty-two thousand for that reason.