A paragraph rewritten, not a letter changed

The collection decides which index is small set three compressed self-indexes against each other and reduced the contest to three constants. On collections of copies of one English-like text, the phrase index built on the Lempel–Ziv parse cost about 57 bits a phrase, the r-index built on the runs of the Burrows–Wheeler transform about 73 bits a run, and the entropy-bounded FM-index about 2.11 bits a character. So the phrase index is smaller than the entropy-bounded one when the parse has fewer than 0.037 phrases a character, the r-index when the transform has fewer than 0.029 runs a character, and the phrase index is smaller than the r-index whenever phrases over runs is under 1.28.

Its honest limit named what those collections were not. Every collection in the strand that started with the entropy that cannot see a copy was a set of copies that had drifted apart by scattered substitutions: each character of each copy flipped to a random symbol with some small probability. A real repetitive collection does not drift that way. A version history changes a paragraph and leaves the rest alone; a set of near-duplicate pages differs in a block of navigation or a date. Both measures, the essay said, respond to the difference — and it did not say how much.

Two ways to change two per cent #

The collection is the strand’s own: thirty-two copies of a 512-character English-like text, sixteen thousand characters in all. With every copy identical the transform has 224 runs and the parse 161 phrases, 0.014 and 0.010 a character, which is far under both thresholds; the phrase index is the smallest of the three.

Then each copy after the first has a share of its characters changed, in one of two shapes. Scattered: every character independently, as before. In blocks: a stretch of $L$ consecutive characters, at a random place in a random copy, rewritten with fresh text drawn from the same source, for $L$ of 4, 16, 64 and 256 — as many blocks as the share requires. The share changed is the same in both shapes, up to the rounding of a few long blocks, and every plate plots against the share that actually changed. Four collections are drawn at every setting.

The two shapes separate at once. With 2% of the copies’ characters changed, scattered substitutions put the transform at 0.100 runs a character — more than seven times identical copies’ 0.014, and more than three times the 0.029 under which the r-index is the smaller structure. The same 2% rewritten in blocks of 16 leaves it at 0.026, still under the line. Scattered changes cross the r-index’s line between 0.2% and 0.5% changed. Blocks of 16 cross it between 2% and 5%, and blocks of 64 between 2% and 5% too, but only just: 0.031 at 5%.

So the strand’s whole account of when the r-index is the right structure was drawn on the shape of change least favourable to it. A collection that has drifted by a twentieth of its characters in paragraphs is still in the regime the r-index was built for; one that has drifted by a two-hundredth of its characters at random is not.

Phrases follow the same rule #

The parse responds the same way, less steeply. Scattered substitutions push it over the phrase index’s threshold of 0.037 phrases a character between 1% and 2% changed; blocks of 4 between 5% and 10%; blocks of 16 not by 10%, where they sit at 0.033. The phrase index stays smaller than the entropy-bounded one up to five times as much change when the change comes in paragraphs.

What one edit costs #

The reason is in the unit each measure counts. A run of the transform ends wherever two adjacent rows of the sorted rotations are preceded by different characters, and a phrase of the parse ends wherever the text stops repeating something earlier. A change breaks both at the place it happens, and the characters inside a changed block mostly do not break anything new.

A scattered substitution adds 4.6 runs and 1.9 phrases. A rewritten block of 4 adds 6.4 and 2.2; of 16, 10.1 and 4.3; of 64, 24 and 12; of 256, 72 and 36. The phrases follow a simple rule closely: two plus the block’s length over 7.5. The two are the phrases that break at the block’s edges — the copy’s text stops matching where the block starts and resumes matching where it ends — and the rest is the block’s own fresh text, which the parse covers in phrases of about 7.5 characters by finding pieces of it elsewhere in the collection. That is the same mechanism an index with z in its size built on: a phrase is a pointer to an earlier occurrence, and fresh English-like text has short earlier occurrences everywhere.

The runs grow more slowly than the block’s length, roughly with its three-quarter power: four times the block costs between two and a half and three times the runs. A changed character inside a block changes the rotations that start near it, but rotations starting inside fresh text are sorted among the collection’s other rotations by their own first characters, and many of them land beside rotations with the same preceding character. A run is broken only where the preceding characters differ, and inside a block of fresh text they often do not.

Edges and contents #

The two measures can be split into what a block costs at its edges and what it costs inside, and the split says where the remaining runs come from.

For phrases the split is clean, because the fitted rule is already in that form: two phrases for the edges, one for every 7.5 rewritten characters. For runs it is rougher. Between blocks of 64 and 256 the runs added grow by 48 for 192 more characters, a quarter of a run a character, and extending that line back to a block of nothing leaves about eight runs for the edges — more than the four or five a single scattered substitution costs, because a block’s two edges each join fresh text to old text in a context none of the copies has had, where a substitution makes one such junction on each side of one character. For short blocks the line overstates: blocks of 4 and 16 cost 6.4 and 10.1 runs, under the line’s 9 and 12, because their edges and their contents overlap.

A quarter of a run for every rewritten character is a measurable fraction of what the same source costs when it is not repeated at all. The original 512-character text, on its own, has 0.43 runs and 0.31 phrases a character. A rewritten block costs less than that inside — 0.25 runs and 0.13 phrases a character — because its fresh text is fresh to its copy but not to the collection: the other thirty-one copies, and the other blocks, are full of the same three- and four-character pieces, and the parse points at them while the transform sorts its rotations beside theirs.

So a long block costs about what that much new text would, and a scattered change costs about eighteen times what one character inside a long block does. Everything in the comparison follows from those two facts: scattered changes are all edges, and blocks are mostly contents.

A changed character, priced #

Divided by the characters changed rather than the places, the difference is the size of the effect. A scattered change costs 4.6 runs and 1.9 phrases a character. In blocks of 4 it is 1.6 and 0.55; of 16, 0.63 and 0.27; of 64, 0.38 and 0.18 — twelve times fewer runs and ten times fewer phrases than the same characters changed one at a time; of 256, 0.28 and 0.14.

That is why “divergence”, the dial the earlier essays used, is not a property of a collection anyone could quote without saying what kind. Two collections each 2% different from their original can differ by a factor of four in run count and the r-index built on them by the same factor, and the number that predicts which is not how much changed but how many places it changed in. The index that stores the runs was right that the run-length index’s size follows the runs and not the characters; this is the same statement one level down, about what the runs follow.

Which index is smallest #

Priced by the three constants, the phrase index is the smallest structure on every collection whose changes come in blocks of 16 or 64, up to 10% changed. Blocks of 4 hand the place to the entropy-bounded index at 10%. Scattered substitutions hand it over from 2% changed, which is where the earlier essays’ collections spent most of their time.

The r-index is never the smallest, which the earlier essay’s third threshold already said: it is never smaller than the phrase index unless phrases over runs exceeds 1.28. That essay’s reason for recommending it anyway was not size but its costs — every occurrence at the same price is the argument — and nothing here touches that. What changes is the size it pays for those costs: on a collection that changes in paragraphs it stays within about twice the phrase index’s size and far under the entropy-bounded index’s, up to a twentieth of the text changed.

The ratio that would reverse the order #

Phrases over runs is 0.72 for identical copies, and every kind of change lowers it, because every change breaks more runs than phrases. Scattered substitutions bring it to 0.41 at 10% changed; blocks of 64 only to 0.52; blocks of 256 to 0.57. Across every collection it stays between 0.36 and 0.70. The earlier essay found it between 0.26 and 0.71 on the texts it measured and called the third threshold “not close”; clustered changes keep it nearer the identical-copy end of that range, and still far from 1.28.

The earlier essay named the one condition that could reach it: an adversarial order of the alphabet, which moves the run count and not the parse, as the measure that cannot see the alphabet constructed. The shape of a collection’s edits is not that condition. Nothing about rewriting paragraphs instead of letters makes runs cheaper than phrases.

What the third measure does #

The entropy-bounded index is drawn on every plate as a fixed 2.11 bits a character, and that is the earlier essay’s constant, not a measurement of these collections. The entropy that cannot see a copy is the reason it does not move with the number of copies; it does move with the changes. The order-three entropy of thirty-two identical copies is 0.59 bits a character; with 2% scattered substitutions it is 0.71, and with 10% it is 1.14, because every substituted character creates contexts the original never had. The earlier essay measured the FM-index at 3.4 times its order-three entropy; if it tracked the entropy in that proportion, the entropy-bounded index on the scattered collections would have grown by a fifth at 2% and nearly doubled at 10%. It was not rebuilt to check.

Holding it at 2.11 is therefore generous to it on scattered changes, and the boundary on the smallest-index plate would sit at somewhat larger shares if it were rebuilt. Rewritten blocks of fresh text from the same source barely move the entropy, since their contexts are the source’s own, so on the clustered collections the fixed constant is close to right. The comparison between shapes survives the correction and becomes a little sharper.

The r-index’s constant has the opposite problem. What is still proportional to n found that at thirty-two copies about half the run-length index is its suffix-array sampling, which follows the text’s length rather than its runs; the 73 bits a run of the earlier essay already contains that, spread over the runs. On a collection with more runs the sampling is a smaller share of the whole and the constant falls a little. None of the thresholds moves by enough to change which shape crosses where.

What to ask of a collection before choosing #

The practical reading is short. The earlier essay’s decision asked two numbers of a collection, its runs and its phrases a character, and both cost one pass to measure. This essay adds a reason to measure them rather than estimate them from how different the documents are said to be: the same stated difference spans a factor of three to five in both — at 2% changed, 1,639 runs scattered against 348 in blocks of 64, and 738 phrases against 225 — and which side of a threshold a collection falls on depends on the shape of its differences, which nobody quotes.

A collection that grows by appending revised versions — a wiki’s history, a sequence of releases, a set of near-duplicate pages — changes in blocks, and on it the repetition indexes keep their advantage far longer than the strand’s own collections suggested. A collection whose copies differ by noise — sequencing errors, typing errors, a lossy channel — changes in scattered characters, and on it they lose it early. The two kinds look alike if the only number quoted is the share that differs.

What the rewritten blocks are not #

Fresh text from the same source. A rewritten block is drawn from the same English-like generator as the original, so its pieces occur elsewhere in the collection and the parse covers it in phrases of 7.5 characters. A block of text from a different language, or of random characters, would parse into shorter phrases and cost more of both measures; a block that moves a paragraph rather than rewriting it — the commonest edit in a real history — would cost almost nothing, two phrases and a few runs at its edges. Neither was measured, and they bracket the case measured here from both sides.

One collection shape. Thirty-two copies of 512 characters, the strand’s standard. More copies of a longer text lower identical copies’ runs and phrases a character further, and give every shape of change more room before a threshold; the order of the shapes should not change.

Constants, not indexes. The three index sizes are the earlier essay’s constants multiplied by the measured runs, phrases and length; none of the three structures was rebuilt for these collections. The constants were measured on collections of exactly this shape and the thresholds follow from them, so the comparison is between collections rather than between implementations.

A corpus that was not generated froze a real version history so that measurements about one would be about a fixed object, and that history is the natural place to read what shapes of change real collections actually have.

Still open: a paragraph that moves #

The rewritten block is the middle case of three. A collection’s edits can also move text — a paragraph cut from one place and pasted in another, the same characters in a different order — and a moved block changes no character’s content at all. The parse should see it as two broken phrases and one long pointer to the block’s old place; the transform should see it as a few rotations at the block’s edges sorting into new neighbours.

The measurement that follows changes the copies by moving blocks of 16 to 256 characters to random places within the same copy, at the same shares of characters moved, and puts the three shapes on one plate. The prediction is that a moved block costs about four phrases and eight runs whatever its length, so that a collection with a tenth of its text moved in blocks of 64 stays at about identical copies’ sizes, and that the run-length structure’s advantage over the entropy-bounded index survives up to a much larger share moved than rewritten. It could fail at the block’s edges: a moved block creates two new junctions per move, and each junction is a pair of contexts no copy has had, which the transform may punish more than the parse. The question is whether the measures count what changed or only where, and a move is the edit that separates the two.