The entropy that cannot see a copy

Take five hundred and twelve characters of English-like text and write it out thirty-two times.

The collection is now 16,384 characters and contains 512 characters of information. Every measure of compressibility this collection has built says otherwise.

$n \cdot H_3$ grows 15.8× across a collection that grew 16×. The second copy is charged full price, and so is the thirty-second.

Why the entropy has to behave that way #

$H_k$ is a function of the distribution of symbols in $k$-symbol contexts. Concatenate a text with itself and every context occurs twice, every symbol following it occurs twice, and the distribution is identical to two decimal places at the join and exactly identical away from it.

$$H_k(T \cdot T) = H_k(T) \quad\Longrightarrow\quad 2n \cdot H_k(T\cdot T) = 2 \cdot n H_k(T)$$

So an index bounded by $n H_k + o(n)$ must double. Not because the analysis is loose — the bound is true and the structures this collection built reach it — but because the quantity is the wrong one. Everything above the third order does the same thing, and going to $H_8$ or $H_{16}$ does not help: the repeat here is 512 characters long, and no fixed-order context model can see a correlation at that distance.

This is not a defect in the analysis. It is a defect in what is being counted, and it is the reason the indexes built for genome collections, document version histories and web crawls are not built on entropy at all.

Two measures that are not entropies #

$r$, the number of equal-letter runs in the Burrows-Wheeler transform. The transform sorts every rotation of the text and reads off the last column, so characters that precede similar contexts end up adjacent. Repeat a text and every context occurs twice, so every character that would have been alone in the last column is now beside its twin — and the run count barely moves.

$z$, the number of phrases in the greedy self-referential parse. Each phrase is the longest prefix of what remains that has occurred starting earlier in the text; the occurrence may overlap the phrase itself, which is what makes a thousand identical characters two phrases rather than five hundred. The second copy of a text is one phrase.

Both are flat and both move by one between the first copy and the second — the join, and the sentinel’s neighbourhood.

Neither is an entropy and neither is a function of a symbol distribution. Both are properties of the sequence, and the difference between “the distribution of symbols in this text” and “this text” is the whole subject.

What r counts is the differences #

Repetition in the real world is not exact. Version histories, genomes and web crawls hold copies that have drifted, so the useful question is what happens between the two ends.

Hold the collection at eight copies and 4,096 characters and substitute a fraction of each copy after the first. The length never changes.

$r$ rises 12.3× across the sweep and $n H_3$ rises 1.72×. And the entropy’s rise is mostly not about repetition at all: substituting characters at random flattens the context distribution, which raises $H_3$ for reasons that would apply to a single copy.

So $r$ is counting the differences between the copies. Seven edits take it from 224 to 264 — about six runs per edit, which is roughly what breaking a run in the transform costs — and the relationship holds across two orders of magnitude of edit count.

That is the property the whole family of repetition-aware indexes is built on, and it is a measurement here rather than a citation.

Six runs an edit, and why that number #

The rate at which $r$ rises with the edit count is worth deriving rather than fitting, because the derivation says what the measure is actually counting.

Substitute one character in one copy. That character occupied a position in the transform’s last column, inside a run of characters that all preceded the same context; changing it splits that run into three — the part before, the changed character alone, the part after. That is two extra runs.

But the substitution also changes the context of the characters around it, so a handful of neighbouring positions move elsewhere in the sorted order and each of them splits a run where it lands. How many depends on how deep the contexts have to go before the two copies diverge, which on English-like text is a small number.

Measured across the sweep:

Flat at 5.7 across a fivefold change in the edit count, and then falling by half.

The falling half is the measure saturating and it is worth reading. Once the edits are dense enough to land in runs that other edits have already broken, an edit splits a run that was already short and buys fewer new runs. At 25% divergence the copies are barely related and $r$ is approaching what eight unrelated texts would give — 2,746 against 3,663 — so the rate has nowhere left to go.

That gives the practical form of the claim, with its condition attached: for a collection whose copies are close, $r$ is of order $\ell + d$ rather than of order $c\ell$ — $c$ documents of length $\ell$ differing in $d$ places — and it is the $c$ dropping out that makes the whole family of repetition-aware indexes possible. For a collection whose copies are not close, $r$ is of order $c\ell$ and there is nothing to exploit, which is the same statement read from the other end.

Where the empirical entropy stops being a measurement #

Push the divergence to the end — substitute every position of every copy after the first, so the eight documents are unrelated — and something happens that is worth an entire section, because it is a trap rather than a result.

The collection got sixteen times less repetitive by the run count, and the measured $H_3$ fell by a quarter.

The reason is that an empirical $H_k$ is a measurement of the sample. A text of 4,096 characters over twenty-one symbols has 9,261 possible three-symbol contexts; the unrelated collection contains 3,012 of them and 77% occur exactly once. A context seen once has zero conditional entropy by definition — whatever followed it, followed it every time — so the estimate is reading its own sparsity and reporting it as compressibility.

The condition is computable before any text is looked at: the estimate is a measurement while $n \gg \sigma^k$ and an artefact when it is not. On the texts this collection has been measuring, $H_3$ over twenty-one symbols wants far more than four thousand characters:

$H_3$ rises with the length of the text, which is the wrong direction for a property of a source and the right direction for an estimate escaping its own sparsity. Every earlier essay in this field that quotes an $H_3$ is quoting a number measured on eight or sixteen thousand characters, where the singleton share is under a tenth — and the assertion carried with this machinery now requires that ratio rather than assuming it.

Three measures, three orderings #

Five texts, 2,048 characters each, measured every way.

Ordered by $r$: repetitive, English, DNA, periodic, uniform. Ordered by $z$: repetitive, English, DNA, uniform, periodic. Ordered by $H_3$: repetitive, English, periodic, uniform, DNA.

The DNA-like text is the interesting row. It has the highest third-order entropy of the five — over four symbols drawn independently there is nothing for a context model to learn, so $H_3$ is nearly $\log_2 4 = 2$ — and it sits in the middle by both repetition measures, because four symbols in two thousand characters produce plenty of accidental repeats.

Periodic and uniform swap places between $r$ and $z$, which is the sharpest available statement that the two repetition measures are not the same quantity: one of them counts places where the transform changes character and the other counts phrases in a parse, and no argument makes them agree.

So “this text is more compressible than that one” is not a statement until a measure is named. This collection has been careful about that for entropy orders since the text field opened; the same care has to extend to a second axis now that there is one.

Why the transform is where the runs are #

It is worth being precise about why the transform is the place to count runs, because the text itself has runs too and they are useless.

The transform sorts every rotation of the text and takes the last column. Two positions land next to each other in that column exactly when the text that follows them is similar — the sort key is the suffix, and the character reported is the one before it. So a run in the last column is a set of positions all preceded by the same character and all followed by similar text, which is precisely the pattern a repeated passage creates.

The text’s own runs measure nothing of the kind. On the same collection the transform has a fifth as many runs as the text does in the stretch drawn, and the text’s count would be identical if the copies were shuffled into a different order — which would destroy nothing about the repetition and everything about the transform’s runs.

And the transform’s symbol distribution is the text’s, exactly. This field measured that two essays ago and treated it as a curiosity: the transform is a permutation, so $H_0$ of one equals $H_0$ of the other to fifteen decimal places, and a structure charging one bit per bit cannot see the transform at all. Put the two facts together and the transform’s role is precise — it converts a property invisible to a symbol distribution into one that is a symbol distribution, of runs. That is the entire mechanism, and it is why the next essay’s structure stores runs rather than symbols.

What this changes about the earlier essays #

Three results in this field stand and one of them acquires a footnote.

The transform is a permutation, so $H_0$ of the transform equals $H_0$ of the text. That was measured to fifteen decimal places and is unaffected — and it is the reason $r$ is the right thing to count about the transform, because the run structure is exactly what the permutation creates and the symbol distribution is exactly what it does not touch.

A compressed self-index’s size orders texts as $H_3$ does. Measured across five texts and still true — of texts. Of collections it is a statement about the wrong quantity, and the next essay measures the structure that follows $r$ instead.

And the entropies quoted in this field are quoted at lengths where they are measurements. That was true and was not checked. It is checked now.

How much of a collection is left, as a number #

The divergence sweep has two anchors in it that are worth using together, and the essay has been reading it one column at a time.

Eight identical copies give $r = 224$. Eight unrelated texts of the same length give $r = 3{,}663$. Those are the two ends of the scale — perfect repetition and none — and every measurement in the sweep sits between them. Normalising against both says what fraction of the exploitable repetition survives a given amount of drift:

Read down that last column and the shape of the whole family becomes visible in a way no single row shows. The relationship is not linear and it is not close to linear: changing one character in four removes three quarters of what a repetition-aware structure had to work with, while changing one in a hundred removes six per cent of it. The regime where these indexes are extraordinary is narrow and it is exactly the regime real version histories and genome collections live in — successive commits differ in a fraction of a per cent, and human genomes differ in about a tenth of one.

Two things are worth saying about that normalisation before it is used for anything.

It is a measurement of this collection at this length, not a universal curve. The unrelated anchor depends on the alphabet and the length — eight unrelated DNA-like texts have a different $r$ than eight unrelated English-like ones — so the denominator has to be measured alongside the numerator rather than assumed. What is portable is the procedure, not the percentages.

And it says nothing about what a structure costs, only about what a measure reports. An index proportional to $r\log(n/r)$ does not halve when $r$ halves, because the second factor moves the other way. A measure of repetition is not a size, and the step from one to the other is the next essay’s subject rather than this one’s — which is why the column above is labelled as repetition retained rather than as space saved.

The parse depends on the order of the documents and the runs do not #

One more difference between $r$ and $z$, and it is the one with a practical consequence attached.

The greedy parse reads the collection left to right and each phrase may only refer to text that has already been seen. So the first document is parsed against nothing and pays its full phrase count, and every later document is parsed against everything before it. Reorder the collection and the parse changes: put the most representative document first and every other document is a short chain of references to it, put an outlier first and the second document pays nearly full price before the rest can begin referring to either.

The transform has no such preference. It sorts every rotation of the whole collection at once, so which document a matching context came from is not a question the sort asks, and two orderings of the same documents produce the same runs apart from what happens at the joins. $z$ is a property of the collection as a sequence and $r$ is a property of the collection as a set, near enough, and the two measures disagree about what the object even is.

That decides something a practitioner would otherwise discover by benchmark. A version history arriving in chronological order is close to the best order for a parse, because each revision resembles the one before it; a collection of genomes arriving in whatever order the files were listed in is not, and sorting it by similarity is a real and cheap improvement to an LZ-based index and no improvement at all to a run-based one. The same rearrangement that pays for one structure is invisible to the other.

It also explains the swap in the five-text table above without appealing to anything else. Periodic and uniform change places between $r$ and $z$ because a periodic text is a sequence with a strong left-to-right structure that a parse captures directly, while its rotations sort into an order the transform finds no more compressible than noise. Two measures, two definitions of what a text is, and no argument that makes them agree — which is the section heading three above, arrived at from a different direction.

What is not measured here #

Other repetition measures. $r$ and $z$ are two of several. The smallest straight-line grammar, the smallest bidirectional macro scheme and the attractor size all measure repetition and all order texts differently again; none is built here, and $\gamma \le z$ and $\gamma \le r$ are known relations that nothing above tests.

Which measure a structure can be built on. $z$ is measured here and no index in this collection is proportional to it. That is a real gap: the Lempel-Ziv index family exists and is a different construction from anything built here.

Real corpora. Every collection above is synthetic and its repetition is a parameter. That is deliberate — the dial is the instrument — and it means nothing here says what $r/n$ is for a genome collection or a source repository.