The branches an error opens

An index walk with a budget of $k$ has a branching factor of $\sigma + 1$ and a depth of about $m + k$, so the obvious bound on its size is something like $(\sigma m)^k$ — a bound everybody writing about the method quotes, and one nobody would use to size a machine.

Measured on a sixteen-character pattern over four symbols in four thousand characters, the tree is 16, 314, 3,875, 39,957 and 351,830 interval extensions at budgets zero through four.

The factor is not constant, and it falls #

The ratios between consecutive budgets are 19.6, 12.3, 10.3 and 8.8.

A bound of the form $(\sigma m)^k$ predicts a constant factor of $\sigma m = 64$. The first measured factor is under a third of that and the fourth is under a seventh, and — more interestingly — they are decreasing.

That is not what a branching argument predicts. Each additional error should open the same number of new branches at each state, so the factor should hold. Instead it falls by more than a half across four budgets, which means the tree is being pruned harder the deeper it gets.

Why it falls: an empty interval has no descendants #

The pruning is the one described in the search that spends a budget, and this is where it earns its place.

A state whose interval is empty is finished: no row’s suffix begins with the string being built, so nothing extends it. Early in the walk, with two or three characters matched, most extensions produce a non-empty interval — a two-character string occurs somewhere in three thousand characters whatever it is. Deep in the walk, with twelve characters matched, most do not.

So the effective branching factor is not $\sigma$; it is the number of characters $c$ for which the extended string still occurs, and that number falls towards one as the matched string gets longer. The tree’s growth is therefore a product of falling factors rather than a power.

This is the shape what O-notation does not say opened this collection with. The bound is correct: the tree is $O((\sigma m)^k)$. The bound is also 64 times per error where the measurement is nine, and the difference is a property of the text rather than of the algorithm.

What a bound of this shape is for #

It would be easy to read the previous section as a complaint about the $(\sigma m)^k$ bound, and it is not one. The bound is doing a job and the job is not sizing a machine.

What it says is that the method is exponential in the budget and polynomial in everything else — so a budget of one or two is a different kind of query from a budget of ten, and no implementation detail will change that. That is worth knowing before writing any code, and it is exactly the sort of statement an asymptotic bound is good at.

What it cannot say is how much. The measured factors run 19.6 down to 8.8 where the bound’s constant is 64, so a capacity estimate from the bound is out by between three and seven times per error — which compounds: at four errors the bound over-predicts by a factor of about six hundred.

The constant the notation drops is this collection’s founding statement of that gap, made for three sorts in the same class. Here the gap is not a constant at all: it grows with the budget, because the pruning gets stronger as the tree gets deeper.

The crossing #

The table’s cost does not move with the budget. Sixteen rows by four thousand columns is 64,000 cells whether $k$ is zero or four; the budget only decides which of the filled cells count as answers.

So there is a budget past which walking the index costs more acts than filling the rectangle it was meant to avoid, and on this text it is $k = 4$: 351,830 extensions against 64,000 cells, with $k = 3$ still under at 39,957.

That crossing is not a fixed property of the method. It moves with the text length — a longer text makes the table dearer and the tree only slightly so — and with the pattern length and the alphabet. At six thousand characters the table is 96,000 cells and the tree at three errors is 48,305, so the margin at the last budget below the crossing has widened from 1.6 times to twice.

What the crossing is not is a collapse in the sense the filters have. The walk at $k = 4$ is expensive and it is still exact, still reads no text, and still costs nothing in cells. It has become the wrong choice rather than a useless one.

The alphabet is the branching factor, and a wider one is not simply dearer #

The branching factor is $\sigma + 1$, so a wider alphabet should cost more. The measurement is not monotone: over two, four and twenty-six symbols with a fourteen-character pattern and a budget of two, the walk takes 5,396, 3,742 and 10,348 extensions.

Four symbols cost less than two. The reason is in the answer size rather than in the branching: over two symbols there are 89 places within two errors of the pattern, over four there are 4 and over twenty-six there are 3.

A binary alphabet makes every extension likely to be non-empty — half the characters, all of them common — so intervals stay alive far longer and there are far more strings within two errors of anything. The branching factor is smaller and the tree is larger, because the pruning is weaker and the answer is bigger.

Between four symbols and twenty-six the other effect wins: intervals empty almost immediately, the answer is three positions, and the cost is the alphabet loop at every state.

The budget is in the question, not in the implementation #

One property separates this parameter from most of the ones this collection sweeps, and it changes what the growth means.

A sampling rate, a block size, a threshold — these are choices an implementation makes, and a plate showing a cost rising with one of them is a plate about a decision. The error budget is not a choice: a caller who needs matches within three errors needs three, and running with two returns the wrong answer set.

So the growth measured here is not a trade-off curve. It is a statement about which questions this method can afford to answer, and the only way to move along it is to change what is being asked.

That is the same distinction a guarantee names its model draws between a parameter of a structure and a parameter of a problem, and it decides how the plates should be read. The crossing at $k = 4$ is not a place to avoid by tuning; it is where a caller with four errors has to use a different method.

Two effects, opposite directions, and no formula #

The two mechanisms are worth naming because they are the reason a branching-factor argument cannot answer this question.

More symbols, more branches. At each state the walk tries every character, so the loop is $\sigma$ long and the per-state cost rises linearly.

More symbols, deader branches. A random string of length $\ell$ over $\sigma$ symbols occurs in a text of $n$ characters about $n/\sigma^\ell$ times, so intervals empty after about $\log_\sigma n$ characters. On two symbols that is eleven characters and on twenty-six it is two and a half.

The product of a linear rise and an exponential fall has a minimum somewhere, and where it is depends on the text length, the pattern length and the budget. The measurement puts it between two and twenty-six symbols on this instance and does not locate it, because three alphabets are three points.

This collection has met the shape before: where insertion sort actually wins is a crossover between two effects with no closed form, measured rather than derived, and the answer there was a number rather than a rule.

What the answer size does to the comparison #

The alphabet plate contains a trap that is worth defusing, because it applies to every cost comparison in this strand.

Over two symbols the walk finds 89 occurrences and over four it finds 4. Those are not the same question. A method that returns 89 answers has done more work by any reasonable accounting, and comparing its cost against one returning four is comparing two problems.

The honest reading is the one the plate’s caption gives: the cost is not monotone in the alphabet and the answer size is not either, and the two move together. Dividing one by the other gives 61 extensions per answer over two symbols, 936 over four and 3,449 over twenty-six — monotone, and a different statement.

Both are true and they answer different questions. “How expensive is a search over this alphabet” is the first; “how expensive is an answer” is the second; and a plate reporting one without the other chooses which question the reader asks.

What would bound it properly #

The measurement here is of a walk with two prunings, and a bound that matched it would have to model both.

The first is the interval emptying, which depends on the text: a state’s survival probability is roughly $1 - (1 - \sigma^{-\ell})^n$ for a matched string of length $\ell$, and integrating that over the tree gives something like the measured product of falling factors. That is a model of a random text and this collection’s texts are generated, so it would be checkable here and not on a real corpus — the same limitation the probe formula nobody checks works under for a hash table.

The second is the budget running out, which is deterministic: below a certain depth the walk is doing exact backward searches and contributes one extension per remaining character.

Neither is in the $(\sigma m)^k$ bound, which is why it is 64 where the measurement is nine. A bound that ignores the input is a bound about the algorithm and not about the run, and this collection’s whole method is to measure the difference rather than to complain about it.

The growth is checked, not fitted #

Four points and an obvious curve invite a fit, and this collection does not fit one.

The check the plate carries is that each consecutive factor exceeds two — that the tree genuinely multiplies rather than merely rising — and that the table’s cell count is identical at every budget, so that the comparison is against a fixed cost. Both are properties the plate would be lying without.

What is deliberately not asserted is an exponent. A quantity multiplying by 19.6, then 12.3, then 10.3, then 8.8 has no exponent: it is not a power of $k$, and reporting a fitted one would be exactly the kind of claim fitting a class to measurements exists to refuse. The site’s fit machinery would return something, and what it returned would be an average of four different behaviours.

Where this leaves the method #

The budget is the parameter and it is not a dial in the usual sense: it is part of the question rather than a choice about how to answer it.

That makes the growth measured here a statement about which questions the method can answer rather than about how to tune it. Budgets of one and two are cheap; three is comparable to the table; four is worse. A caller who needs four errors on a twenty-character pattern should use something else, and the two filters in this phase have their own limits at nearly the same place — the seed filter by chance hits and the counting filter by arithmetic.

The three limits arriving together is not a coincidence — an error rate of a fifth is where a pattern’s structure stops constraining anything, whichever machinery is exploiting it — and three savings in three currencies is where the three are put on one page.

Where the growth would stop #

There is a ceiling on all of this that the sweep does not reach, and it is worth naming because it is the one thing that would make the tree stop multiplying.

At a budget large enough, every string of length $m \pm k$ is within $k$ errors of the pattern, the answer is every position in the text, and the walk enumerates the whole suffix array. The tree cannot grow past that, so the growth curve must flatten somewhere — and where it flattens is where the answer has become the whole text, which is the same degeneration the counting filter reaches at a threshold of zero.

On four symbols with a sixteen-character pattern that point is far above the budgets measured here; the answer at $k = 4$ is still ten positions out of four thousand. So the sweeps are entirely in the regime where the method is answering a selective question expensively, and the flattening is a fact about the shape rather than something this collection has measured.

Two of the three methods in this phase therefore have the same asymptote for the same reason. The threshold that reaches zero reaches it by arithmetic at a computable budget; the walk approaches it gradually and from below. Neither is useful there, and the useful ranges of both end well before it.

The factors fall by a constant, and where that lands #

This page refuses to fit an exponent and it is right to — a quantity multiplying by 19.6, 12.3, 10.3 and 8.8 has none. But the factors have a shape, and reading it costs one subtraction and says something the essay’s closing section reaches for qualitatively.

Take logarithms of the tree sizes: 2.77, 5.75, 8.26, 10.60, 12.77. The differences are 2.98, 2.51, 2.34, 2.17 — and the differences of those are −0.47, −0.17, −0.17. After the first step, each error’s multiplier is a constant 0.17 smaller in the log than the last, which is about sixteen per cent per error.

So over the measured range the tree’s logarithm is not linear in the budget; it is quadratic, and the quadratic’s sign is negative. That is exactly what a product of linearly-falling factors gives, and it is a much better description of four points than any exponent would be.

The useful part is where the arithmetic points. A multiplier falling by 0.17 in the log reaches zero — a factor of one, the tree no longer growing — at

$$k \;\approx\; 4 + \frac{2.17}{0.17} \;\approx\; 17,$$

and the pattern is sixteen characters long. The extrapolation lands on the ceiling this essay names for entirely independent reasons: at a budget of about $m$, every string of the right length is within $k$ errors of the pattern, the answer is the whole text, and the walk has enumerated the suffix array with nowhere left to grow.

Two things about that are worth separating, because only one of them is a claim.

The description is a measurement. Over budgets one to four the log-differences fall by a constant, and that is a statement about four points which any reader can check by subtracting.

The extrapolation is not. Nothing here establishes that the factors keep falling linearly out to seventeen, and this collection’s standing position is that a fit over a range says nothing past it — a limit is not a prediction in its usual form. What makes the coincidence worth printing is that the destination was known before the arithmetic was done: the ceiling is a counting argument about how many strings are within $k$ errors, and the extrapolation of a curve measured at $k \le 4$ arriving at the same place is a consistency check on both.

It also sharpens what the $(\sigma m)^k$ bound is wrong about. The bound is an exponential — a straight line in the log — and the measurement is a downward parabola. So the bound is not merely too large by a constant; it has the wrong shape, and the discrepancy compounds: three times per error at the first step and seven times by the fourth, which is the factor of six hundred this page quotes at $k = 4$ and would be far larger at eight.

Which is why the refusal to fit is the right call and the subtraction is still worth doing. Fitting a class to measurements would grant nothing here and should not; reporting that the log-differences are linear over the measured range grants nothing either, and it is a description of the plate rather than a class.

The honest limit #

The walk has no lower-bound pruning, so a published implementation’s tree is smaller than the one measured here — how much smaller is not established, and the factors quoted are upper bounds on what a careful implementation would show.

The texts are three to six thousand characters with occurrences planted by substitution, which means the answer sets are small and known. On a corpus where a pattern occurs approximately in many places, the leaves-to-answers gap and the tree size would both be larger for reasons that have nothing to do with the branching.

And the alphabet comparison is three points on one instance. It establishes that the cost is not monotone in $\sigma$, which needs only two points in the right relation, and it does not locate the minimum or say whether it moves with $m$ or $k$.