The thread: Repetition is not entropy
A floor under a run count
A structure whose size is a function of the number of runs in a transform must give a different bit string to every text with that many runs, so it needs at least the logarithm of how many such texts there are. That count is walked rather than estimated — all four thousand and ninety-six of them — and the representation everybody uses turns out to have five bits of slack.
The data that is not a numberThe entropy that cannot see a copy
Two copies of a text have exactly the same symbol statistics as one, so every entropy on this site doubles when the second copy arrives and the second copy carries no information at all. The number of runs in the Burrows-Wheeler transform is 224 at two copies and 224 at thirty-two.
The index that replaces the textThe index that stores the runs
A compressed self-index over thirty-two copies of a text is 30,557 bits, because its size follows an entropy that cannot see a copy. An index that stores the transform as its runs is 11,900 — and at a single copy it is the larger of the two, which is what makes the comparison a claim about repetition rather than about size.
The index that replaces the textThe sampling that follows the runs
A run-length index over thirty-two copies of one text spends 11,286 bits on its suffix-array sampling and 5,605 on the transform it was built to compress. Sample at the run boundaries instead and the sampling is 10,942 bits that stop moving — two values per run, and a function that fills in everything between them.
The data that is not a numberThe phrases a text copies from itself
Four thousand characters of English-like text hold 604 phrases in the greedy parse and 1,219 runs in the transform. Thirty-two copies of one text hold 156 phrases and 233 runs. Two measures of repetition, neither of them an entropy, and they do not agree about which text is the more repetitive.
The other axisWhat is still proportional to n
An index whose size is a function of the run count still has an n in it, and at thirty-two copies of a text the n is half of it. Everything that stores the transform grew by 45 per cent; the two arrays that answer "where" grew by eighteen times, and neither of them has anything to do with repetition.
The index that replaces the textAn index with z in its size
Over thirty-two copies of one text, an index built on the parse is 8,892 bits, the r-index is 17,047 and the entropy-bounded index is 34,615. Over eight thousand characters of four-symbol text the same three are 7,844, 25,177 and 20,413, and the smallest of the three has changed places twice.
The data that is not a numberThe occurrences that cross a boundary
One pattern, thirty-two copies of a text, thirty-two occurrences. The search finds one of them and produces the other thirty-one by arithmetic, and the count it finds is the same one at two copies, at eight and at thirty-two — the searching does not grow when the answer does.
The index that replaces the textThe collection decides which index is small
Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.
The other axisThe term that came back
A phrase index is worth building because 8,192 characters parse into 156 phrases. Cap the copy depth at one and the same text parses into 7,351 — ninety per cent of the characters — and the structure is proportional to the text again.
The data that is not a numberA corpus that was not generated
Every collection in five strands has been copies of a generated text with a fraction of its characters replaced — three numbers, one dial. Here is one that was not — twelve essays, eight source modules, ten revisions of one file — measured beside the model of it.
The data that is not a numberA million characters of the same thing
Every measurement this collection has published about real text was taken on twenty-four thousand characters, because the phrase count was quadratic. It is linear now, so here is the same corpus at forty times the size — and what forty times does to its own numbers.
What is taught wronglyThe half of a fall that is the logarithm
Phrases per character on a real collection of essays fall by a factor of 2.34 as it grows. A shuffle of the same characters falls by 1.70. Nearly three quarters of the movement is arithmetic, and no definition of the measure says so.
StructuresThe runs a permutation does not leave
A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.
What is taught wronglyA sampling that costs more than the array
On four-symbol text the transform has 0.75 runs a character, so a sampling of two suffix-array values per run is one and a half values per position — 271,565 bits against the 131,088 that keeping every value costs. The structure built to remove a term proportional to the text is twice the thing it replaced.
The data that is not a numberThe shape of a real history's depth
Four essays here are about capping how far an extraction follows a chain of copies, and every number in them came from a generated collection. Here is the depth histogram of a real version history, which is a bell, and of twelve unrelated essays, which is nearly the same bell.
What is taught wronglyThe measure that cannot see the alphabet
Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.
The data that is not a numberThe cell nobody filled
Every structure here was measured either on one long repetitive text or on prose cut into short documents. The collection that is both is a two-by-two with one empty corner, and what is in it is not the product of its margins.
What is taught wronglyThe deepest text is punctuation
Eight source files reach depth 78 in a parse, on a collection with no version history in it at all. The positions between depth 20 and depth 72 are the same 48 characters at every level, and every one of them is a dash in a comment separator.
The data that is not a numberWhat repetition is worth once the logarithm is gone
On prose, nearly three quarters of the fall in phrases per character with size is arithmetic that any text pays. On a collection built of copies it is a fifth, and what is left is a factor of three that is genuinely the arrangement.
The index that replaces the textThe index that does not notice
Three compressed indexes over the same characters. One is flat at six and a half bits a character however many copies the collection holds; the other two fall by factors of five and six. At one copy the two that fall are the largest of the three.
What is taught wronglyA boundary that costs nothing
A separator occurs nowhere else in the collection, so it must break a phrase that would have spanned it. Cutting a repetitive text into a hundred and twenty-eight documents raises its run count by two per cent, and cutting prose raises it by ten.
StructuresThe price of a boundary is what precedes it
A separator sorts before everything, so its rows sit at the top of the suffix array and hold the documents' last characters. What a document boundary costs the transform is the entropy of the character in front of it, and nothing else.