The phrases a text copies from itself

Take a text and read it left to right. At each point, find the longest piece of what remains that has already appeared somewhere earlier, write down where it appeared and how long it is, and jump past it. Where nothing has appeared before, write down the character itself and step one position.

The number of pieces is $z$. On sixty-four characters of English-like text it is 46, and 21 of those are single characters that had never been seen.

Why this is a measure and not a compressor #

The construction above is Lempel and Ziv’s, and this collection has already built a compressor on it: the dictionary that builds itself measures the bits a sliding-window coder emits, with a bounded window, a minimum match length and a real encoding of the tokens.

None of those bounds are here. The window is the whole prefix, the minimum length is one, and the phrase count is reported as a number rather than as bits. That is deliberate: the quantity being measured is a property of the text, and a window size or a token encoding is a property of an implementation. A parse with a 4,096-character window measures how repetitive the text is within four thousand characters, which is a different question and a good one, and not this one.

The other difference is that the source of a phrase may overlap the phrase itself. A thousand identical characters is two phrases here — one literal and one reference of length 999 starting at position 0 — rather than the ten or so a bounded matcher would emit. That overlap is what makes $z$ small on periodic structure and it is why this parse is the measure and the coder is not.

The second measure, and the first thing they disagree about #

This collection already has a measure of repetition that is not an entropy. The entropy that cannot see a copy introduced $r$, the number of equal-letter runs in the Burrows-Wheeler transform, and measured its central property: two copies of a text have the transform of one, plus one run, and the count then does not move however many copies arrive.

$z$ has the same property for the same reason at a different level of the machinery. The second copy is one phrase — a reference of length 512 to position 0 — and every copy after it extends that phrase rather than adding one.

Measured on this collection’s own sweep: $z$ is 155 at one copy and 156 at every point from two copies to thirty-two, while $nH_3$ runs from 324 bits to 10,175. Both non-entropy measures are flat and the entropy is not, which is the finding the strand before this one established and this one inherits.

Where they disagree #

Being flat on copies is what the two measures have in common. What separates them shows up on texts that are not collections of copies, and the plate of five texts is the cleanest form of it.

At four thousand characters: English-like text has $z = 604$ against $r = 1{,}219$; four-symbol text $z = 816$ against $r = 3{,}063$; an internally repetitive text $z = 110$ against $r = 158$; a periodic text $z = 1{,}285$ against $r = 3{,}588$; a uniform random text $z = 1{,}286$ against $r = 3{,}596$.

$z$ is smaller than $r$ on all five, and the ratio is not constant — 2.0 on English, 3.8 on four-symbol text, 1.4 on the repetitive one, 2.8 on both random sources. A structure sized by one of them and a structure sized by the other are therefore not two implementations of one idea, and the fact that both are called “measures of repetitiveness” hides a factor of nearly four.

Why $z$ is smaller here, and where the inequality actually lies #

The observation that $z < r$ on every text in the plate invites a general claim, and the general claim is not available.

What is known about the pair is a pair of inequalities in opposite directions with logarithmic factors in them, and neither dominates: a text can have $r$ much larger than $z$ and a text can have $r$ smaller than $z$. What the plate measures is that on these five texts the parse is the smaller number, which is a fact about English, DNA-like strings and this collection’s random sources rather than a theorem.

The mechanism behind the direction is worth stating even so. A phrase can be long — the parse takes the longest match available, so one repeated block of five hundred characters is one phrase. A run is a stretch of the transform, and a repeated block contributes runs proportional to the number of distinct contexts it appears in rather than to its length. So the parse gets full credit for a long repeat and the transform gets credit proportional to how cleanly the repeat clusters rows.

This is the same distinction compression is prediction makes about coders, one level up: a measure counts what a particular machine can exploit, and two machines exploit different structure.

A third quantity that is neither #

There is a temptation, once two measures are on the table, to look for the one that is right. It is worth resisting with a third number that is neither of them and is the one every earlier essay in this field used.

$nH_k$ — the length times the empirical entropy of order $k$ — is what the compressed indexes in this field are measured against, and it is a function of how often each symbol follows each $k$-symbol context. Two copies of a text have exactly the distribution of one copy, so $nH_k$ doubles when the second arrives and carries no information at all. On the sweep above it runs 324 bits to 10,175 across a collection whose content never changed after the first copy.

Raising $k$ does not help and the reason is structural rather than a matter of degree: a repeat five hundred characters long is a correlation at distance five hundred, and no fixed-order context model has a context that long. Pushing $k$ up far enough to see it makes the contexts outnumber the characters, at which point the empirical entropy is measuring the sample rather than the source — the trap the model is the compressor is about, and the reason every $H_3$ quoted in this field is quoted at a length where the singleton share is under a tenth.

So there are three quantities, two of them blind to copying and one of them blind to everything else. That is not a ranking; it is why the choice of measure decides what a structure can be small on.

The literals are the part that is not repetition #

A parse has two kinds of phrase and only one of them is a copy. The literals — single characters appearing for the first time — are a lower bound on $z$ that has nothing to do with how repetitive the text is: a text over $\sigma$ symbols has at least $\sigma$ of them, one per symbol.

Measured: 21 literals on English, 4 on four-symbol text, 19 on the repetitive one, 8 on the periodic and uniform sources. In every case it is close to the alphabet size, because after each symbol has been seen once nothing else needs to be written down literally.

That matters for reading the numbers. On the collection of thirty-two copies, $z$ is 156 and 19 of those are literals; the remaining 137 phrases carry the whole of the structure’s knowledge of a sixteen-thousand-character text. A structure proportional to $z$ is therefore proportional to something that has an alphabet-sized floor under it, and on a very repetitive collection most of what it stores is that floor.

What the arcs show that a count does not #

The picture at the top of this essay is not decoration. Three properties of the parse are visible in it and are invisible in $z$.

Phrases are not uniform. A few of them are long and most are one or two characters, which is why the arithmetic mean phrase length is a poor summary and why $z$ rather than a mean is the quantity carried forward.

Sources are not local. The arcs reach backwards by arbitrary distances, and on a collection of copies the longest arc reaches back one whole copy. A bounded window would cut exactly those arcs, which is the difference between this measure and a coder’s output.

A phrase may copy from a region that is itself a copy. That is the property the character that costs a chain is about, and it is the price of everything else here: producing one character means following the arcs backwards until a literal is reached.

What the dial does to each measure #

“Repetitive” is a dial in this strand rather than an adjective, and the two measures respond to it differently enough to be worth one plate.

Substituting one character in a hundred, independently per copy, turns a collection of thirty-two identical copies into thirty-two near-copies. Every substitution breaks one long phrase into two and adds a literal-ish phrase in the middle, so $z$ grows roughly linearly in the number of substitutions. The run count grows too, for a related but not identical reason: each substitution disturbs the rows whose contexts it changes.

The important thing about the dial is what it does to the comparison. At divergence zero both measures are flat and the entropy is not, which is the headline. At divergence one — every copy independently drawn — both measures grow like the entropy does, and the three quantities become three ways of saying the same thing.

So a collection is not simply repetitive or not. The entropy that cannot see a copy established that reading the divergence off the plate matters; this strand carries the same convention, and every plate in it prints the number it was drawn at.

The parse is quadratic here, deliberately #

One implementation note belongs in the essay rather than in a docstring, because it decides what can be measured.

The parse used throughout this strand is computed by scanning every earlier position for the longest match, which is $O(n^2)$ character comparisons. It is a measurement taken once per text at sizes a plate can draw, not a compressor, and at four thousand characters it takes a few milliseconds.

A real implementation computes the same parse in linear time from a suffix automaton or a suffix tree, and the number it produces is the same number. So nothing in this strand depends on the quadratic loop except the sizes at which the sweeps run — which is why the collections here are thousands of characters rather than millions, and why every claim is stated as a shape rather than as an extrapolation.

That constraint is the same one every substring in fewer states works under from the other direction: the automaton is the structure that makes the parse cheap, and this strand uses the slow route because it needs the parse rather than the structure.

Neither measure is a bound on the other’s structure #

It is tempting to read the plate of five texts as ranking two structures, and it does not, for a reason worth separating from the measurement.

A structure sized by $z$ stores a source, a length and a literal per phrase, and it needs an ordering of the boundaries to search. A structure sized by $r$ stores a transform’s runs, a wavelet tree over their heads, and a sampling. The constants differ, the machinery differs, and a text where $z$ is half of $r$ does not necessarily give an index half the size.

An index with z in its size is where those constants are measured, and the answer on this collection is that the phrase index is smaller than the r-index at every point past one copy — by more than the measures’ ratio, because the r-index carries a sampling and a predecessor structure that the phrase index does not.

What the two measures give is the shape of each structure’s size as the collection grows. Both flatten; how far below the entropy-bounded structure each ends up is arithmetic on the constants.

What is being claimed, exactly #

Three statements, and the distinctions between them are the point of the essay.

$z$ is flat under copying. Checked: 155 at one copy, 156 from two to thirty-two, on a collection whose entropy grows by a factor of thirty-one. That is a property of the parse and not of the implementation.

$z$ is smaller than $r$ on the five texts here. Measured, and stated as a measurement rather than as an inequality, because the general relation between the two carries logarithmic factors in both directions.

Neither of them is an entropy. An entropy is a function of a distribution of symbols in contexts and cannot see a copy at any order; both of these count structure that a distribution does not contain. That is the finding repetition is not entropy exists to carry, and the second measure is what turns it from a claim about one number into a claim about a kind of number.

Why this needs a new anchor rather than a new rung #

This collection organises essays by the idea they argue about, and the parse is a new one rather than a deeper rung on an existing ladder. The reason is worth stating because the alternative was tempting.

The obvious home is the repeat ladder, which runs from the entropy that cannot see a copy through the index that stores the runs to a floor under a run count and is about repetition as a property that a run count can see. Every essay on it is about $r$.

The parse is a different object with a different invariance, a different structure built on it and a different failure mode. Its size is unaffected by the alphabet’s order, which the measure that cannot see the alphabet measures and which is false of $r$; its structure produces a character by following a chain rather than by walking a transform; and its search splits occurrences into two kinds that have no analogue in the other index at all.

Putting those on one ladder would have made “rung 5 of repeat” mean two different things depending on which essay it was, and this collection’s own note about anchors says not to: an anchor is the idea an essay makes an argument about, and the argument here is about phrases.

The honest limit #

The collections here are copies of a generated text, with an optional per-character substitution rate as the dial. Real repetitive corpora — versioned documents, genomes of one species, logs — are repetitive in ways that are neither identical copies nor uniform substitution, and both measures respond to the difference.

The second limit is length. Everything is measured between five hundred and sixteen thousand characters, where $\lceil\log_2 n\rceil$ moves by four and the alphabet-sized floor under $z$ is a visible fraction of it. A sweep long enough to separate $z$’s growth on non-repetitive text from $n/\log_\sigma n$ — the rate it is known to approach — is not run here.

What is missing is a collection with document boundaries. A parse crossing from the end of one document into the start of the next produces phrases that are artefacts of the concatenation, and every measurement in this strand pays that cost silently.

That last cost has a bound, and it is worth stating rather than leaving as an unknown. A phrase either lies inside one document or straddles a join, and a join can be straddled by at most one phrase — the one whose start falls before it and whose end falls after. So the artefact contribution to $z$ is at most $d - 1$, one per boundary.

That is the same shape as the spanning-window count the occurrences a join invents measures: a property of how many documents there are, not of how long they are. On the collections here, where the documents are copies and each parses as a single phrase, it is zero — a copy’s phrase begins exactly at the boundary rather than across it, which is why the flat lines above are not quietly inflated.

Where it would matter is the shape this strand has not measured: many short documents, where $d$ approaches $z$ and up to a fifth of the phrase count could be joins rather than text. A separator does not remove those phrases — it makes them unmatchable, which is a different fix for a different problem, and one separator, or one for each prices it.

So the silent cost is bounded, it is zero on everything drawn here, and it is worst exactly where the measure is most load-bearing.