Proportional to the answer, not the alphabet

The claim is that an interval enumeration costs what the answer costs rather than what the alphabet costs. Testing it needs an experiment where the answer moves and the alphabet does not, and the sweep a reader reaches for first moves both.

Sweeping the interval’s width changes how many symbols it holds — a four-position interval holds at most four and a four-thousand-position interval on twenty-six letters holds all of them. That is a real measurement and it confounds two things: as the interval widens, both the symbol count and the interval’s own size grow, and a cost following either would look the same.

The experiment that separates them holds the alphabet at thirty-two symbols throughout and draws the measured stretch from a restricted sub-alphabet. The background uses all thirty-two, so the tree’s shape and depth are fixed; the stretch uses d of them, so the interval holds d distinct symbols at a fixed width.

The two lines #

The loop is flat at three hundred and twenty ranks. Thirty-two symbols, ten ranks each — the depth of a balanced tree over thirty-two symbols is five, and each rank walk costs two per level in this accounting. It asks about every symbol whether or not the symbol is there, so the number cannot depend on what is there.

The descent goes ten, ten, sixteen, twenty-two, thirty-eight, sixty-two as the symbol count goes one, two, four, eight, sixteen, thirty-two.

The factors are 32, 32, 20, 14.5, 8.4 and 5.2.

The flat line is worth a sentence on its own because it is the thing being replaced and it has no defence. A loop over the alphabet cannot do better than σ rank walks, and a rank walk on a balanced tree over σ symbols is log₂ σ levels, so σ log σ is not a bad implementation of the loop — it is the loop. There is no version of “ask about each symbol” that costs less.

That is why the comparison is between an operation and an approach rather than between two implementations. Asking about symbols that are not there is where the approach is described; this is where its cost is shown to be independent of the answer, which is the property that makes it replaceable.

The discount #

The descent’s cost does not rise linearly with the symbol count, and the gap is the whole shape of the result.

Doubling the symbols from one to two costs nothing — both cost ten ranks. Doubling from sixteen to thirty-two costs twenty-four more. The marginal cost of a symbol rises as more of them are present.

The reason is that a descent enters the ancestors of the present leaves, and the ancestors of d leaves in a tree of σ number about d(1 + log₂(σ/d)). At d = 1 that is 1 + 5 = 6 nodes; at d = 2 the two paths share their top, so it is 2(1 + 4) = 10 — but only if the two leaves are far apart, and if they are siblings it is 7.

At d = 32 it is 32(1 + 0) = 32 leaves plus 31 internal nodes, which is the whole tree.

So the per-symbol cost falls: ten ranks a symbol at d = 1, five at d = 2, four at d = 4, 2.75 at d = 8, 2.4 at d = 16 and 1.94 at d = 32.

What a falling per-unit cost does to a quotation #

A method costing c·d has a constant c that can be quoted once. This one does not.

Its effective constant is ten at one end and two at the other, on the same tree and the same alphabet. A summary saying “about four ranks a symbol” would be an average over a range where the true value spans a factor of five, and the average would be wrong at both ends.

The honest summary is the formula — two ranks per node, and the nodes are the ancestors of the present leaves — which is short enough to carry and is what every number here follows from.

This collection has met the shape before on a different structure. Work that falls as the answer grows is the document listing’s version, where the same counting bound produces the same falling per-unit cost, and where the same difficulty arises in quoting a crossing.

Halving the alphabet halves the loop’s flat line — sixteen symbols at eight ranks each is a hundred and twenty-eight — and barely moves the descent’s left-hand end, because one root-to-leaf path on sixteen symbols is eight ranks against thirty-two’s ten. So the factor at d = 1 falls from thirty-two to sixteen, which is σ/2 in both cases.

That the factor at one symbol is exactly σ/2 is worth checking rather than assuming, and it comes out of the arithmetic directly: the loop costs σ · 2 log₂ σ and the descent costs 2 log₂ σ, so the ratio is σ. The measured thirty-two at σ = 32 is that, and the halving is the two ranks a node.

Where the floor is #

There is a lower bound on any method that reports which symbols are present, and it is worth writing because the descent is close to it.

Reporting d symbols out of σ requires distinguishing them, and there are C(σ, d) subsets of size d, so an answer carries log₂ C(σ, d) bits of information — which is about d log₂(σ/d) + d log₂ e for d well below σ.

That is the same shape as the descent’s node count. The descent reads 2d(1 + log₂(σ/d)) numbers rather than bits, so the comparison is not immediate, and the shape is the bound’s.

That is unusual. Most costs in this collection have a shape that is an artefact of a structure — a tree’s depth, a table’s width, a probe sequence’s length. This one has the shape of the problem, which means the descent is within a constant of the best possible for the reporting part.

What it does not bound is the finding part. The bound above is about naming a known set; the descent also has to determine which set, which is where the ranks go. So the correspondence is suggestive rather than a proof of optimality, and it is offered as the former.

A node costs two ranks is where the constant in front of the node count is pinned down, and it is worth restating here because every number above depends on it: the descent visits k nodes and spends 2k ranks, exactly, and the check is an equality rather than a bound. Without the arithmetic identity the descent would cost 4k and every factor on this page would halve.

The confounded sweep, and what it still shows #

The width sweep is worth drawing even though it cannot separate the two effects, because it shows something the controlled sweep cannot.

As the interval widens from four positions to four thousand on a twenty-six letter alphabet, the symbol count goes four, nine, twenty-three, twenty-six, twenty-six, twenty-six. The descent’s cost goes fourteen, thirty-six, fifty-four, fifty-four, fifty-four, fifty-four.

It flattens. Once every symbol is present there is nothing left to enter, so the descent’s cost is capped at the whole tree and does not rise however wide the interval gets.

That cap is what gives the operation a bounded worst case: 2(2σ − 1) ranks against the loop’s σ⌈log₂ σ⌉, a ratio of ⌈log σ⌉/2, which at twenty-six symbols is 2.4 and at a thousand is 5.

So the operation is never much worse than the loop and is often much better. The controlled sweep says how the “often” behaves and the width sweep says where the ceiling is.

Two at binary, five at twenty-six is where the alphabet axis is measured properly, and it is the axis that decides whether this operation is worth anything on the workloads it is meant for. The controlled sweep says the operation’s cost follows d; the alphabet sweep says how large σ has to be for that to matter.

Why the restricted sub-alphabet is the right control #

The construction deserves a paragraph because it has a subtle failure mode that this collection walked into once.

The background text uses all thirty-two symbols so that the tree’s shape is fixed — a balanced code over thirty-two symbols, depth five, at every point of the sweep. If the background used only the d symbols the stretch uses, the tree would be over d symbols and its depth would be log₂ d, so the descent’s cost would fall for two reasons at once and the alphabet would not be held after all.

The stretch is placed in the middle of the text rather than at an end, and the interval is taken over the stretch exactly. Placing it at the start would make the interval’s rows unrepresentative of the tree’s structure at the top levels.

And the whole thing is generated by a seeded stream that has to be a real one. An earlier version used a multiply-and-mask generator that lost its high bits in a double, so a request for twenty-six letters produced two — and every factor on every plate was the factor at σ = 2. The tell was that DNA and binary reported the same alphabet size. A corpus that was not generated is where this collection stopped trusting its own generated inputs without checking them, and a generator producing two symbols when asked for twenty-six is the cheapest possible instance of the same failure.

What this means for a search #

The controlled numbers translate to a search through one further fact: the intervals a search works in are narrow.

At the root the interval is the whole text and every symbol is present, so the descent costs the whole tree and the loop’s advantage is at its smallest. One character in, the interval is still wide. Six characters into an eight-character pattern on a text of eight thousand, the interval holds a handful of rows and therefore a handful of symbols — which is the left-hand end of the controlled sweep, where the factor is twenty or thirty.

So the search spends most of its time in the regime where the descent is worth most, and the plate above is a plate about where that time goes.

The measurement that would have been wrong #

It is worth stating what the naive version of this measurement reports, because it is a plausible plate and it says something false.

Sweeping the interval width and plotting the factor gives 18.6, 7.2, 4.8, 4.8, 4.8, 4.8. A reader would conclude that the saving is about five and is large only on very narrow intervals.

The controlled sweep gives 32, 32, 20, 14.5, 8.4, 5.2 against the number of symbols present, which says the saving is a function of d/σ and reaches thirty-two when one symbol is present.

Both are true of what they measured. The first is a measurement of intervals and the second is a measurement of the operation, and only the second transfers to a search whose interval widths are different from the sweep’s.

That distinction is the reason the confounded sweep is drawn as a companion rather than as the result. A plate showing a factor against a width is a plate about that text at those widths.

The distribution the leaves are drawn from #

The bound d(1 + log₂(σ/d)) is tight for evenly spread leaves and the measured points sit twenty per cent under it, which means the leaves in this sweep are not evenly spread. That gap is worth understanding because it is the difference between a bound and a measurement, and the direction is the useful one.

Leaves that clump — a set of symbols whose codes share prefixes — have more shared ancestors and therefore fewer distinct ones, so a clumped set is cheaper than the bound. The restricted sub-alphabet used here takes the first d symbols of a fixed ordering, which on a balanced code means the first d code words, which means a clumped set: the whole left subtree first.

So the measured numbers are the best case for a given d, and a set of d symbols scattered across the alphabet would cost more — up to the bound.

That matters for reading the search numbers. The symbols present in a search’s interval are not the first d of anything; they are whichever characters happen to precede the interval’s rows, which is a scattered set. So a search sees costs nearer the bound than this sweep does, and the factors it gets are correspondingly a little smaller.

Measuring the scattered case would need a different construction and this sweep does not attempt it. What it establishes is the shape — cost following d with a logarithmic discount — and the constant in front of it is a property of how the symbols are distributed rather than of the operation.

What a fixed alphabet buys the measurement #

Holding σ fixed does one more thing that is easy to take for granted: it holds the tree’s shape fixed, which holds the code lengths fixed, which holds the cost of a single rank walk fixed.

That matters because the loop’s cost is σ walks and a walk’s cost is the code length. On a balanced tree every code is ⌈log₂ σ⌉ bits so the walks are uniform; on a frequency-shaped tree they are not, and the loop’s cost would then depend on which symbols the text made frequent. Sweeping d on a Huffman tree would therefore move the loop’s line as well, and the flat comparison line would be gone.

This sweep uses a balanced tree for that reason. It is the wrong shape for compressing anything — the array is the length distribution is where the frequency-shaped tree earns its place — and it is the right shape for a measurement whose subject is the descent rather than the code.

That is a general habit worth naming: hold the structure fixed and vary the query, or hold the query fixed and vary the structure, and never both. Every plate in this strand does one or the other, and the two that look like exceptions — the alphabet sweep and the width sweep — are drawn as companions to a controlled sweep rather than as results.

Why this is a bound essay rather than a cost essay #

The strand’s other cost measurements are about how much a change saves. This one is about what the cost is a function of, which is a different kind of claim and needs a different kind of evidence.

A saving is demonstrated by two numbers. A functional form is demonstrated by a sweep whose axis is the argument and whose other variables are held — which is why most of this essay is about the experiment rather than about the result.

The result itself is two lines: the loop is flat in d, and the descent is 2d(1 + log₂(σ/d)). Everything else is the case for believing that the second line is about d and not about something that moved with it.

There is a floor is this collection’s habit for the other side of the same question — what a cost cannot go below — and the two habits are complementary. A floor says no method can do better; a functional form says what this method’s cost follows. Neither implies the other, and this operation happens to have both, with the floor and the form having the same shape.

What is bounded and what is not #

Collecting the three bounds this essay has produced.

The descent’s cost is at most 2(2σ − 1) ranks, which is the whole tree, and it reaches that when every symbol is present.

It is at least 2 log₂ σ, which is one root-to-leaf path, and it reaches that when one symbol is present.

Between the two it is 2d(1 + log₂(σ/d)) to within the leaves’ arrangement, and the measured points sit twenty per cent under that bound because the bound is tight only for evenly spread leaves.

None of those is the interesting number for a caller, which is the factor against the loop: σ⌈log σ⌉ over the above, which is σ/2 at one symbol and ⌈log σ⌉/2 at all of them.

Both ends of that are worth carrying. Half the alphabet in the best case, half its logarithm in the worst, and everything real between.

There is a last thing the cost analysis leaves out entirely, and it is worth flagging because a reader who has followed the arithmetic this far might take the operation as settled. The descent returns its symbols in the tree’s leaf order. On a balanced tree that is the alphabet’s order and everything above holds unchanged. On a frequency-shaped tree it is not, and a caller accumulating a running count as it reads the output computes a plausible wrong number — which one set, three orders measures, and which no operation count can see.

So the cost is proportional to the answer and the correctness of one use of the answer is proportional to nothing measured here. Two independent properties of one operation, and the strand needs both.