A schedule nobody writes down

The previous essay measured a factor of 2.7 and attributed it to the order a pattern is consumed in. This one is about the object that decides that order, which is a small table of integers that nothing in any description of the method names, and about the three ways of writing one that produce answers a reader cannot tell from correct ones.

What a scheme is #

Three lists per search, all of the same length.

An order: which piece to visit first, second, third. It is constrained — a search holds the rows for a contiguous string, so a piece can only be visited when it touches what has already been visited. With three pieces there are four legal orders.

A ceiling: the most errors allowed so far after each piece is finished. A search whose first ceiling is zero demands its first piece be exact.

A floor: the fewest errors allowed so far, which exists so that a scheme’s searches can be made to partition the occurrences rather than overlap on them.

A scheme is a list of searches, and it is valid when between them they cover every way the errors can fall. The pieces themselves come from the pigeonhole the q-grams an error cannot destroy is built on, and the index they are searched in is the one the structure that was supposed to halve prices.

The covering condition, enumerated #

With two errors over three pieces there are ten distributions, counting the ones that use fewer than the whole budget: (0,0,0), (1,0,0), (0,1,0), (0,0,1), (2,0,0), (1,1,0), (1,0,1), (0,2,0), (0,1,1), (0,0,2).

A search covers a distribution when the running total of errors, in that search’s own order, stays between its floor and its ceiling at every step. A scheme is valid when every one of the ten is covered by at least one search.

That is a finite check over a small set — the number of distributions is (k + p − 1) choose k, which at k = 2 and p = 3 is ten and at k = 3 and p = 4 is thirty-five — so there is no reason to argue about it. It is enumerated, and the enumeration is in the checks rather than in a comment.

It is worth noticing what the condition does not say. It says nothing about how large the resulting trees are, so a valid scheme can be arbitrarily bad — the plain right-to-left search is a valid one-search scheme with ceilings of k everywhere, and it walks the largest tree in the strand. Validity is a correctness condition and nothing else.

The quality condition is separate and has no closed form: among covering schemes, the good ones have tight ceilings early and their first pieces exact. That is a search over a small space, and the space is small enough to enumerate at the budgets anybody uses.

The scheme here was found, not quoted #

The three searches on the plate are not from a paper. They were found by enumerating every order whose prefixes are contiguous against every non-decreasing pair of floor and ceiling vectors, taking every triple of them, and keeping a covering one whose searches all demand their first piece exact.

There were two reasons not to quote one. The first is that the published schemes are stated for exactly k errors, with their floors set so that each occurrence is found by exactly one search — which is the right design when the answer wanted is “the occurrences at distance exactly k” and the wrong one here, where every matcher in this collection reports everything within the budget. A scheme with its floors intact reports only the occurrences that use the whole budget, and the ones at distance one and zero vanish.

The second reason is better: the enumeration is three lines and it produces a scheme that is checkably valid, where a quoted one is valid on the authority of the quotation. The first triple written down here from memory was not covering — it missed the distribution (0,2,0), both errors in the middle piece — and the enumeration is what said so.

That is not an argument against reading the literature. It is an argument for the habit this collection keeps: a condition that can be checked in a line should be checked rather than cited, particularly when the failure it prevents is silent.

What an incomplete scheme does #

Remove one search from the covering triple. What is left is still three searches minus one, still finds occurrences, still reports them at their correct error counts, and still walks a smaller tree than the plain search does.

Measured on a text with eight planted occurrences: seven of the eight are found. The missing one is the occurrence whose errors fell the way the removed search covered.

Nothing about the output says so. The seven are real. Their error counts are right. The positions are in the text. A test that plants patterns and checks that the matcher finds them passes seven times in eight and fails once, and if the planting happens to distribute errors the way the surviving searches cover, it passes every time.

The distribution that goes missing #

It is worth saying which one, because the pattern is instructive. The triple written from memory covered every distribution with an error in the first or last piece, and missed (0,2,0) — both errors in the middle.

That is exactly the distribution a planted test is least likely to produce. Planting two errors at random positions in a fifteen-character pattern puts both in the middle five characters about a ninth of the time, so a test with eight planted occurrences misses the case about four times in ten. The defect is therefore not merely silent: it is silent in a way correlated with how tests are usually written.

The enumeration has no such correlation. It walks all ten cases in the order they are generated and reports the missing one by name.

Redundancy, which hides a different defect #

The covering triple covers several distributions twice, and that redundancy is not a flaw — a covering with no overlap requires the floors that make the scheme report only exactly-k occurrences.

It does mean the output cannot be used as a test of the structure. An interval that grows at both ends records the measurement: with the reverse interval’s start deliberately left where it was, so that every extension after a leftward one is wrong, the scheme finds all eight occurrences — because the search that uses both directions loses them and another search hands them back.

The in-step check on the intervals catches it on all thirty-nine substrings it examines. The answer catches it never.

So the strand carries two independent checks that look redundant and are not: one on the structure’s invariant, one on the scheme’s covering. Each is blind to the other’s failure.

The pieces cut for the wrong budget #

The third way to get this wrong is arithmetic rather than logic, and it is the one most likely to survive into a working implementation.

The pigeonhole needs k + 1 pieces. Cut the pattern into k instead — an off-by-one in a place where “the number of pieces” and “the budget” are both nearby integers — and the guarantee is gone: k errors can touch k pieces, so no piece is forced to be exact.

Measured: seven of eight occurrences found, again. Same symptom, different cause, and the schemes still run, still terminate, and still walk a plausible tree.

The reason this one is dangerous is that it is invisible at a fixed budget. A test suite that always runs at k = 2 with a hard-coded three-way cut never exercises the relationship between the two numbers, and the defect appears the first time somebody changes the budget.

Three defects, one shape #

All three produce false negatives that look like results: real occurrences, correct error counts, a smaller tree, and no exception anywhere.

That is the shape the pruning that loses an occurrence records for a bound rather than a schedule, and it is the shape the filter that proposes everything records for a filter. It recurs because approximate matching’s output is a set, and a set that is missing something looks exactly like a set.

The general defence this collection uses is the same in all three places: check against a computation that does not share the mistake. Here that is comparing the pattern against every position of the text, which is quadratic, is trivially correct, and is run at every budget on every schedule.

The floors, and the thing they were for #

It is worth returning to the floors, because dropping them has a cost that this strand pays and does not otherwise mention.

A floor’s purpose is to make the searches disjoint: with floors set so that search i handles only distributions whose running total has reached a certain value by a certain step, each occurrence is found exactly once. Without them, occurrences covered twice are explored twice, and the scheme walks a larger tree than the published version would.

So the trees measured here are upper bounds on what a scheme with intact floors would explore, and the factor of 2.7 is a conservative one — the same direction of conservatism three savings in three currencies insists on stating whenever a comparison is not exact. The reason the floors were dropped is stated above and is not negotiable: this collection reports occurrences within the budget, and a scheme with floors reports occurrences at the budget.

A scheme covering “at most k” with floors as tight as that condition permits is a real object, and the enumeration here does keep whatever floors survive the wider condition — the third search’s floor is (0, 1, 1) rather than zero. Squeezing more out of that is a deferral, and it is worth perhaps a further ten per cent.

Why there are three searches, and why four at three errors #

The plate shows three searches at two errors and four at three, and the enumeration is described as finding nothing better than one per piece. That is not a coincidence of the space searched. Once every search is required to start on an exact piece, one search per piece is forced, and the argument is short enough to give.

The pigeonhole says that $k$ errors over $k+1$ pieces leave at least one piece untouched, which is what makes an exact anchor available at all. It does not say which piece, and a search that demands its first piece exact can only cover distributions in which that particular piece is the untouched one. So the question is whether some proper subset of the pieces suffices as starting points, and the distributions with exactly one zero answer it: at two errors those are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$, and each is coverable only by the search anchored on its single zero piece. All three searches are necessary, and by the same argument all four are at three errors, where $(1,1,1,0)$ and its rotations do the forcing.

So the scheme size is $k+1$ exactly — a lower bound from the distributions and an upper bound from the construction — and the enumeration is confirming a count rather than discovering one. That is worth knowing before running it, because it says what a covering scheme with fewer searches would have to give up: the exact first piece, on at least one of them.

Which is the trade the validity condition deliberately does not express. A scheme is free to allow errors in its first piece; it then covers more distributions per search and needs fewer searches, and it starts each of them from an interval that has not been narrowed by an exact match. The plain right-to-left search is that idea taken to its limit — one search, covering everything, walking the largest tree in the strand. Fewer searches and bigger trees are the same axis, and the covering condition is orthogonal to it, which is why validity and quality have to be checked separately.

The forcing also explains why the budget hurts twice over. Raising $k$ by one adds a piece, so the scheme gains a search, and it shortens every piece from $m/(k+1)$ to $m/(k+2)$, so every anchor is a weaker filter. At fifteen characters and two errors the anchor is five characters; at three errors it is under four, and a four-character exact anchor over a four-symbol alphabet matches a text of four thousand characters in about fifteen places before any error is allowed at all. Both effects push the same way, which is the mechanism behind the ceiling the shortest pattern sets arriving in a different field: a filter’s selectivity is set by the shortest exact thing it can insist on, and dividing a pattern into more pieces is a decision to insist on less.

The pieces themselves come from the q-grams an error cannot destroy, and this is where that pigeonhole’s cost becomes visible as a schedule rather than as a bound.

What a reader should ask of a scheme #

Three questions, in order, and the first two have finite answers.

Is it covering? Enumerate. At the budgets anyone runs there are at most a few dozen distributions and the check is a loop.

Are its pieces cut for this budget? k + 1 pieces for k errors, and the relationship should be computed rather than typed. A cut written as a literal is a cut that stops matching the budget the first time either changes.

And what does it cost? That is the open question, because the answer depends on the alphabet, the pattern length, the budget and where the pieces are cut — and this strand measures it at one setting of each. The factor of 2.7 is a measurement about fifteen characters of four-symbol text at two errors, and the plates that vary each of those are the reason it is not offered as a constant.

Why the object is a table rather than a rule #

There is one more thing worth extracting, and it is about the form of the answer rather than its content.

A good schedule is not derived from a principle. It is a triple of integer vectors, found by search over a space of triples, and the reason it is good is that no better triple exists in that space. There is no sentence of the form “always start in the middle” that is correct — at three errors the enumeration finds nothing better than one search per piece, and at one error it finds nothing better than two.

That puts a schedule in the same category as a merge policy’s rules or a sort’s cutoff: an object with a value rather than a formula, whose value has to be established by measurement and then written down. The threshold somebody chose is this collection’s essay about that category, and it applies here with one addition — a threshold is at least visible as a number in the code, and a schedule is usually not present at all.

What this makes visible about the method #

An index walk with an error budget is usually written down as a recursion: at each character, match or branch, stop when the budget runs out. That description is complete, correct, and omits the object that decides a factor of five.

The schedule is not a parameter of that recursion. It is a choice about which characters the recursion sees first, and on a unidirectional index there is nothing to choose — which is precisely why the description does not mention it. The choice appears with the second index, and it appears as a table of integers that nothing derives.

That is the same shape as the queue decides the class, and the pseudocode does not name it, which found the same thing about a shortest-path algorithm, and as the model a bound was quoted in, which found it about a bound. A description that is complete about the operations can be silent about the thing that decides the cost, and the silence is not carelessness — it is what happens when the deciding object has only one possible value in the setting the description was written for.

What is checked, and what must fail #

Every named scheme covers every distribution, at three budgets, by enumeration.

Every schedule finds exactly what exhaustive comparison finds, positions and error counts, at two budgets.

And three things must fail. A scheme with a search removed must lose an occurrence — it loses one of eight. Pieces cut for the wrong budget must lose one — they lose one of eight. And an unsynchronised interval must be caught by the in-step check even though the answers do not change — it is, thirty-nine times out of thirty-nine.