The measure that cannot see the alphabet

Nothing about a text changes when its symbols are renamed. The same characters occur in the same places; every repeat is still a repeat; a compressor’s job is identically hard.

The number of runs in its Burrows-Wheeler transform changes anyway, because the transform sorts rotations and sorting needs an order.

The construction #

A Fibonacci word is built by repeatedly appending the previous word to the current one, starting from b and ab. The sixteenth is 4,181 characters over two symbols, and it is about as structured as a binary string gets without being periodic.

Transform it with a sorting before b: the transform has six runs. Swap the two symbols — rename every a to b and every b to a, which changes nothing about the string’s structure — and the transform has nineteen.

Six is not a small version of nineteen. Across the family the better order holds the count at five or six at every length, while the worse one grows by one for every word in the sequence: 9, 11, 13, 15, 17, 19 at lengths 34, 89, 233, 610, 1,597 and 4,181.

The ratio therefore grows without bound. It is 1.5 at the sixth word and 3.17 at the sixteenth, and there is nothing in the construction that stops it.

Which order is the bad one alternates #

The detail that makes this more than a curiosity is that neither order is reliably the good one.

At the sixth, eighth, tenth, twelfth, fourteenth and sixteenth words, a before b gives six runs and b before a gives nine, eleven, thirteen, fifteen, seventeen and nineteen. At the seventh, ninth, eleventh, thirteenth and fifteenth, the two swap: a before b gives 8, 10, 12, 14 and 16, and b before a gives five.

So the penalty for ordering the alphabet wrongly cannot be avoided by a rule about the alphabet. It depends on the text — here on the parity of the word’s index — and a program choosing an order without looking at the data is choosing a coin flip whose stake grows with the length.

Why the parse cannot see it #

The parse is defined by one relation between characters: equality. A phrase is the longest piece of what remains that has already occurred earlier, and “has occurred” is a statement about characters being the same.

Renaming symbols is a bijection, so it preserves equality exactly. Two positions that held the same character before hold the same character after; two substrings that matched still match; the longest match at every point is the same length and starts in the same place. The parse is literally identical, phrase for phrase.

That is not an approximate invariance and it does not need a measurement — but it is measured anyway, because a claim that cheap is exactly the kind that gets implemented wrongly. Across every relabelling of every text in this essay, $z$ took one value. Across 24 orderings of a four-symbol alphabet it is 450 every time; across 60 relabellings of a nineteen-symbol alphabet it is 94 every time.

Why the transform can #

The transform sorts the rotations of the text and reads off their last characters. Sorting is the only place an order enters, and it enters decisively: which rotations end up adjacent is exactly what decides whether the last column has long runs.

Renaming the symbols permutes the sort keys, which reorders the rows, which changes which characters are neighbours in the last column. Nothing about the text changed and the entire structure the run count measures did.

That is why $r$ is a property of a text and an order rather than of a text. It is easy to lose track of, because the order is almost never stated: an implementation sorts by byte value and nobody writes down that the byte values were the choice. That is the same omission the model a bound was quoted in is about, moved from a cost model to a comparison operator.

How big is it on ordinary text #

The Fibonacci family is a construction and constructions can be unrepresentative, so the same measurement runs on this collection’s four ordinary texts.

Exhaustively where the alphabet allows: all 24 orderings of a four-symbol text give run counts from 1,527 to 1,562, a spread of 1.023. Sampled where it does not: sixty relabellings of English-like text give 646 to 687, a spread of 1.063; of a periodic text 1,762 to 1,817, a spread of 1.031; of an internally repetitive text 121 to 140, a spread of 1.157.

So on random-ish texts the effect is two to six per cent, and on the repetitive one — the kind of text the index that stores the runs exists for — it is sixteen. The direction is the interesting part: the more a text repeats, the more its run count depends on an arbitrary choice, because a small count is a fragile one.

The same fragility, seen in the structure #

The run count is not an abstract quantity here — three essays of this strand build a structure whose every part is a function of it — so it is worth asking what a sixteen per cent spread in $r$ does to a size.

Everything. The r-index’s parts are $r$ sparse-vector entries, $r$ wavelet-tree symbols, $2r$ suffix-array values and $r$ predecessor anchors, so a size proportional to $r$ moves with it exactly. A relabelling that raises the run count by sixteen per cent raises the sampling that follows the runs by sixteen per cent, and it raises the number of pieces in a function with r pieces by the same amount.

It also moves the query cost, though less. A predecessor query is a binary search over $r$ anchors, so a sixteen per cent larger $r$ is a fraction of a comparison; the toehold’s lookups are over $r$ run heads and move similarly. The structure gets bigger and barely slower, which is the least damaging direction for a spread to run in.

What it does not move at all is correctness. Every ordering gives a correct index, and the occurrence sets agree across all of them — which is worth saying because the invariance being violated here is one of size and not of behaviour.

What this does to a size claim #

An r-index’s size is $O(r\log(n/r))$ bits, and the sizes measured throughout this strand are quoted at whatever order this collection’s texts happen to sort in.

On English that means the sizes are within about six per cent of what a different ordering would give, and on the repetitive text within sixteen. Neither changes any conclusion in an index with z in its size or a sampling that costs more than the array, whose gaps are factors of two to fifty.

What it does change is what kind of number an $r$-based size is. It is not reproducible from the text alone. Two implementations indexing the same corpus, one sorting by byte value and one by frequency, report different sizes for the same structure over the same data, and neither is wrong.

A $z$-based size does not have that property. Two implementations of the parse report the same phrase count on the same text whatever their symbols are called, which is the sort of guarantee a guarantee names its model asks every claim here to be explicit about.

The order is a parameter nobody offers #

The natural next question is whether an implementation should choose the order deliberately, and the honest answer is that nothing here does and the search space says why.

There are $\sigma!$ orderings. For a four-symbol alphabet that is 24 and exhaustive search is what the plate above does; for a twenty-six-symbol one it is more than $10^{26}$, and each evaluation costs a transform. So “sort the alphabet to minimise $r$” is not an optimisation an index can perform as a matter of course, and this collection has not measured any heuristic for it.

What can be said from the measurements is the size of the prize. On the texts here the best order beats the worst by two to sixteen per cent and on the constructed family by a factor that grows with the length, so a heuristic would be worth having on repetitive corpora and close to worthless on random ones.

What is being claimed, and what is not #

Three separate statements, and only two of them are measurements.

The phrase count is invariant under relabelling. This is a proof rather than a measurement — equality is preserved by a bijection — and it is checked at every relabelling of every text here because a proof about a program is a claim about the program.

$r$ is not, and the difference is unbounded. The Fibonacci family exhibits a ratio growing with the length, which establishes that no constant bounds the penalty. It does not establish the growth rate; six points on a family is a demonstration and not a fit, and the plate says so.

The effect on ordinary text is a few per cent. Measured on four texts, exhaustively on one of them, and it is a statement about these texts rather than about texts.

The three together are what a reader needs: a structural invariance, a construction showing the other measure has none, and a measurement of how much it matters where nobody constructed anything.

The check that must fail #

A claim of exact invariance needs a test that would notice if it stopped holding, and “compare $z$ before and after” is not enough on its own — a broken relabelling that did nothing would pass it.

So the check is two-sided. Across the relabellings, $z$ must take exactly one value and $r$ must take more than one. If the relabelling stopped relabelling, the second half fails; if the parse started depending on the symbols, the first half fails.

On the Fibonacci family the same pair is checked in the sharper form: $z$ must agree between the two orders at every word, and the spread at the top of the range must exceed the spread at the bottom, so that the claim is about growth rather than about a gap.

The entropy is invariant too, and for a third reason #

One quantity in this field is unaffected by relabelling for a reason unlike either of the two above, and putting it beside them completes the picture.

An empirical entropy $H_k$ is computed from the frequencies of symbols in contexts. Renaming symbols permutes the table’s labels and leaves every count where it was, so the entropy is unchanged — not because it ignores order like the parse does, but because it never consults an order in the first place.

So the three measures split two against one in a different way from every other comparison in this strand: $z$ and $H_k$ are invariant and $r$ is not, where on repetition $z$ and $r$ are flat and $H_k$ is not. Which two measures agree depends entirely on which property is being asked about, which is the strongest possible argument against treating them as three estimates of one thing.

Why this belongs in the wrong-answers field #

The field this sits in collects things that are widely stated and mislead, and the statement here is “$r$ measures how repetitive a text is”.

It does, up to an arbitrary choice nobody mentions. Every paper quoting $r$ for a corpus quotes it at one ordering; every implementation sorts by byte value; every comparison between two corpora’s run counts is a comparison at whatever order both happened to use. The claims are all true and the quantity is not quite the one the sentence names.

This collection has the same shape elsewhere. The block that is not a block is about a parameter that a model treats as given and a machine does not supply; the model a bound was quoted in is the general form. A measure with an unstated parameter is a measure whose value cannot be reproduced, and that is a stronger complaint than a large error bar.

What a reader should do with this #

Two practical consequences, and neither of them is “stop using the run count”.

State the order. A run count quoted for a corpus is a run count at an ordering, and the ordering costs one line to record. This collection’s own texts sort by their characters’ natural order and every plate here is drawn at that order; this sentence is the record.

Do not compare run counts across implementations. Two indexes over the same corpus reporting 2,391 and 2,530 runs may differ in nothing but how they mapped symbols to integers, and a paper reporting a sixteen per cent improvement in a structure sized by $r$ has to rule that out before the improvement is real.

Neither of these applies to the phrase count, which is why this essay sits where it does. A quantity that cannot be reproduced from the data alone is a weaker instrument than one that can, and the difference is invisible until somebody renames the symbols.

The growth rate is readable without fitting anything #

This essay declines to fit a class to six points, and it is right to decline — but the six points here are stronger evidence than six points usually are, and the rate falls out without a fit.

The run counts in the bad order are 9, 11, 13, 15, 17, 19 at the sixth, eighth, tenth, twelfth, fourteenth and sixteenth words. That is exactly one more run per index of the family, an arithmetic progression with no residual. The lengths at those indices are 34, 89, 233, 610, 1,597 and 4,181, which is a geometric progression with ratio $\varphi \approx 1.618$, exactly, by construction.

An arithmetic sequence against a geometric one is a logarithm, and the base is the geometric ratio. So over the measured range

$$r \;=\; \log_\varphi n + c \;=\; \frac{\ln n}{\ln\varphi} + c \;\approx\; 2.08\log_2 n + c,$$

and putting the numbers in gives $\log_\varphi 34 + 2 = 9.3$ against a measured 9, and $\log_\varphi 610 + 2 = 15.3$ against 15. Both to within the rounding a run count forces.

That is a different kind of evidence from a straight-looking line. Nothing was fitted: the increments are integers and they are all the same integer, and the lengths are a defined recurrence rather than a swept parameter. What the six points establish is that the relationship holds exactly at every one of them, and the only open question is whether the family continues to behave as it has — which is a question about Fibonacci words rather than about extrapolating a curve. A limit is not a prediction’s caution is about the second kind of question and applies here weakly.

So the penalty for the wrong order on this family is $\Theta(\log n)$, against a constant for the right one, and the ratio grows without bound at a stated rate rather than merely without bound.

Two things follow, and the second is the one that keeps the finding honest.

The size claim inherits the logarithm. An r-index is $O(r\log(n/r))$ bits, so on this family the good order gives $O(\log n)$ and the bad one $O(\log^2 n)$. Both are absurdly small — the whole index for four thousand characters is a few hundred bits either way — and the class has changed, which is a stronger statement than a constant-factor spread and is the one the family exists to demonstrate.

And the stakes on this family are nil, precisely because both orders are so good. Nineteen runs over 4,181 characters is a text at the extreme of compressibility, where any ordering gives an index smaller than the alphabet’s description. The construction proves that no constant bounds the penalty; it says nothing about how large the penalty gets where the penalty could matter. That is what the two-to-sixteen per cent on ordinary text is for, and it is why the two measurements are both in this essay rather than either being sufficient.

Which is the same division of labour an index with z in its size uses between a constructed family and a corpus: the construction settles what is possible and the corpus settles what happens.

The honest limit #

The Fibonacci family is two symbols, so there are exactly two orderings and “the best” and “the worst” are the only options. Whether the same unbounded separation exists over larger alphabets, and whether the growth is the $\log n$ the shape suggests, is not established here — six lengths and a straight-looking line are a demonstration and this collection does not fit a class to six points.

The ordinary texts are relabelled exhaustively only for the four-symbol one; the others are sixty random permutations out of $\sigma!$, so their reported spreads are lower bounds on the true spread. A search for the extreme orderings would give larger numbers and is not run.

And nothing here measures what a good ordering would be. The prize is bounded by the spreads above; the heuristic that claims it is not built, not measured, and named only to say that it is not here.