A paragraph moved costs its seams

A repetitive collection — a version history, a set of near-identical pages, many genomes of one species — is small to index only if the index can see the repetition, and two measures decide whether it can. The runs of the Burrows–Wheeler transform, $r$, set the size of the r-index that the index that stores the runs built; the phrases of the Lempel–Ziv parse, $z$, set the size of the phrase index that the phrases a text copies from itself described. The collection decides which index is small priced both against the entropy-bounded FM-index, and three measured constants — about 57 bits a phrase, 73 bits a run and 2.11 bits a character — turned the contest into thresholds: the phrase index is smaller than the entropy-bounded one under 0.037 phrases a character, the r-index under 0.029 runs a character.

A paragraph rewritten, not a letter changed then asked how the shape of a collection’s edits moves those measures, at the same share of characters changed. A scattered substitution adds 4.6 runs and 1.9 phrases; a block of 64 characters rewritten with fresh text adds 24 runs and 12 phrases — far less a changed character, because a block’s interior is one stretch of new text rather than sixty-four separate breaks. Its phrases followed two plus the block’s length over 7.5, the mean phrase of fresh text: two for the block’s edges, the rest for its contents.

That essay ended on the third shape. A collection’s edits also move text: a paragraph cut from one place and pasted at another, the same characters in a different order. A move has edges and no new contents. If the two measures count what changed, a move should cost almost nothing; if they count where, it should cost its edges. The prediction was about four phrases and eight runs a move, whatever its length.

Three shapes at the same share #

The collection is the strand’s own: thirty-two copies of a 512-character English-like text, 16,384 characters, which with every copy identical has 224 runs, 161 phrases and an order-3 entropy of 0.59 bits a character. Each copy after the first is then changed in one of three shapes, and the three are compared at the same share of characters touched.

Scattered substitutions are the strand’s original dial: every character independently changed with a small probability. Rewritten blocks are the last essay’s: $L$ consecutive characters at a random place in a random copy replaced with fresh text from the same source. Moved blocks are new: $L$ consecutive characters cut from a random place in a random copy and pasted at a random other place in the same copy. A moved copy keeps its length and its multiset of characters exactly, which the measurement checks on every copy; only the order changes.

The share touched runs from 0.5% to 20%, the two block shapes use blocks of 64 unless a plate says otherwise, and six collections are drawn at every setting. At 10% that is about 25 blocks across the 31 changed copies, against about 1,500 scattered substitutions.

The moved line rises the slowest of the three. At a tenth of the text touched, moved blocks put the transform at 0.030 runs a character, rewritten blocks at 0.050, scattered substitutions at 0.370 — twelve times the moved figure. The r-index’s threshold of 0.029 is crossed at 9.2% moved, against 4.4% rewritten; scattered substitutions are already past it at half a per cent.

So the prediction’s direction holds: the r-index stays smaller than the entropy-bounded index about twice as far into a collection of moves as into one of rewrites. Its magnitude does not. A tenth of the text moved does not leave the collection near identical copies’ size: the runs more than double, from 224 to about 500. A move is cheap against the other two shapes, and it is not free.

The parse barely notices #

The parse sees a move even less than the transform does. A fifth of the text moved in blocks of 64 parses into 0.019 phrases a character, half the phrase index’s threshold of 0.037 and not yet twice the identical copies’ 0.010. Rewritten, the same blocks reach the threshold at 19% of the text; scattered, at one and a half per cent.

The reason is visible in how the parse works. The Lempel–Ziv parse reads each copy left to right and covers it with the longest stretches that occurred earlier in the collection. In a copy where a block of 64 has moved, the text before the cut is a stretch of the original; the moved block itself is a stretch of the original too, just read from a different place; and the text after the paste resumes another stretch of the original. Each of those copies from earlier text. What the parse cannot copy is the few characters at each junction, where text that was never adjacent in any earlier copy now meets — and there the parse spends a short phrase and starts the next long one.

What one block costs #

The two plates so far fix the block length at 64. The question the move was meant to answer is whether its cost depends on its length at all, so the next plate runs blocks of 4, 16, 64 and 256 and measures the cost of one block directly: the excess of runs and phrases over identical copies, against the number of blocks, fitted through the origin over the shares up to 5%, where blocks rarely overlap.

A moved block costs 2.9 to 3.3 phrases and 9.5 to 11.2 runs at every length from 4 to 256. A rewritten block’s cost climbs with its length, as the last essay found — to 40 phrases and 76 runs at 256 — because a rewritten block’s interior is new text and new text has to be paid for character by character. A moved block’s interior is old text, and the measures pay nothing for it whether it is four characters long or two hundred and fifty-six.

What a move pays for is its seams. A move makes three places where two characters that were never neighbours become neighbours: where the block was cut out, the gap closes and joins the text before the cut to the text after it; where the block lands, its first character meets the character before the paste, and its last meets the character after. Three seams, and about one phrase each: the parse can copy everything between seams and cannot copy across one. The prediction of four phrases counted the two edges of the block and the two of the hole it left, but the hole’s two edges are one seam, since the gap closes.

A scattered substitution has two seams of its own — the changed character’s left neighbour and its right — and on these collections costs 1.8 phrases and 4.5 runs, a little under one phrase and a little over two runs a seam. A move’s seams cost more runs each, about three and three-quarters, and that is the transform’s way of seeing them. The transform sorts every position by the text that follows it and records the character before; a position just before a seam is now followed by text it was never followed by, so it sorts into a place among strangers, and each of the positions before the seam whose sorting depends on reading across it may break a run. Across a substitution’s seam the context changes by one character; across a move’s it changes to a different part of the text entirely, so more of the preceding positions are displaced. The run count is the measure that charges a seam by how different the two sides are.

The entropy is the third witness #

The strand’s third measure is the empirical entropy, which the entropy that cannot see a copy introduced as the measure that does not see repetition at all: it counts how predictable each character is from the three before it, and a collection of identical copies is exactly as predictable as one copy. Moves leave it almost where it was — 0.62 bits a character at a tenth of the text moved, 0.65 at a fifth, against 0.59 for identical copies — because a move adds only the three seams’ worth of new three-character contexts and leaves every other context’s statistics untouched. Rewritten blocks raise it to 0.69 and 0.76, by bringing in fresh text; scattered substitutions to 1.13 and 1.45, by breaking nearly every context they touch.

This bears on a number the last two essays held fixed. The entropy-bounded index was priced at a measured 2.11 bits a character throughout, and the last essay’s honest limit noted that its own collections’ entropy rose from 0.59 to 1.14 under a tenth of scattered change while the price stayed put. Under moves that limit nearly disappears: the entropy hardly moves, so the fixed price is closer to right for moved text than for any other shape measured. The thresholds the plates draw are therefore most trustworthy exactly where they say the repetition indexes win by the most.

Which index is smallest #

Put through the three constants, the shapes divide the contest cleanly.

Under scattered substitutions the entropy-bounded index is the smallest of the three from 2% of the text changed, as the strand found from the start.

Under rewritten blocks of 64 the phrase index is the smallest up to 15% of the text and the entropy-bounded index takes over at 20%, once the parse passes 0.037 phrases a character; the r-index falls behind the entropy-bounded index at 4.4%.

Under moved blocks of 64 the phrase index is the smallest at every share measured, out to a fifth of the text: at 20% it costs about 18,000 bits against 58,000 for the r-index and 35,000 for the entropy-bounded index. The r-index falls behind the entropy-bounded one only at 9.2%.

The order of the two repetition indexes #

The last plate is the contest between the two repetition indexes alone. The r-index is the smaller of the two only when there are more than 1.28 phrases a run, and on these collections there never are: identical copies sit at 0.72 phrases a run and every shape of edit pushes the ratio down. Moves push it down fastest of the block shapes — 0.48 at a tenth of the text, 0.40 at a fifth, against 0.52 and 0.47 rewritten — because a move costs three phrases and eleven runs, a ratio of about 0.3 for every block added, where a rewritten block of 64 adds twelve phrases to twenty-four runs, a ratio of a half.

That ratio is a measure of what each index is paying for. The parse pays for a seam roughly once; the transform pays for a seam once for every displaced position before it. The more an edit is made of seams rather than contents, the further the phrase index pulls ahead, and a move is all seams.

Where and what #

The essay before this one ended by asking whether the measures count what changed or only where, and said a move is the edit that separates the two. The answer is that both measures count where, and that the earlier shapes concealed it because their where and their what were the same thing.

A scattered substitution is a change of content at one place, and it costs two seams. A rewritten block is a change of content over $L$ places, and it costs two seams plus its contents parsed as fresh text, $L/7.5$ phrases. A moved block changes no content at all and costs three seams. Read that way, every edit’s price is its seams plus whatever new text it brings, and the new text is priced as if it were a stretch of an unrelated document — which, to the parse and the transform, it is.

That is a statement a version history can use. A history whose edits are mostly reorganisation — sections moved, paragraphs swapped, lists reordered — is close to free for a repetition index however much text it moves, and a history whose edits are mostly new writing is priced by how much is written. The share of characters touched, the number every plate here is drawn against, is the wrong number to ask of a collection before choosing an index: it puts a moved paragraph and a rewritten one at the same place on the axis, and one costs eleven runs while the other costs twenty-four or seventy-six. The right number is the count of seams and the amount of new text, separately.

What the seams cost the parts that locate #

The three constants price each index whole, but the strand built the r-index in parts, and the parts respond to a move differently, which is worth setting down because a run is not one thing in the r-index’s budget.

The part that stores the transform, as what is still proportional to n took it apart, holds one entry a run: the run’s character and its length. The part that says where an occurrence is — the sampling — was the expensive part in that essay, and the sampling that follows the runs made it proportional to runs too, by storing the text position at each run’s boundary and filling in every other position from it. Every occurrence at the same price then showed that a sampling at the boundaries locates every occurrence for one predecessor query, whatever the collection. So every run a move adds is a run the transform stores and two positions the sampling stores, and a move’s eleven runs are eleven of each. Nothing in the r-index is charged by the length of the block moved.

The phrase index is built the same way at one remove: one pointer and one length a phrase, and a phrase is what a seam costs. That is where the 0.3 phrases a run of a move’s cost comes from in bits — three phrases at 57 bits against eleven runs at 73 — about 170 bits a move for the phrase index and 800 for the r-index.

Neither number is close to a floor. A floor under a run count counted how many texts share a run count and put a lower bound on any structure that stores the transform by its runs; the constants here sit well above it, and no part of this measurement asks how close a better r-index could come. The seams are what each index is paying for; what each pays per seam is still an engineering number.

What these collections leave out #

Moves within a copy only. Each block is pasted back into the copy it came from. A block moved between copies — a paragraph from one version pasted into another — would bring text that is old to the collection but new to the copy, and was not run.

Every copy edited from the same original. All thirty-one changed copies are edits of the first copy, made independently, so no two of them share an edit. A version history is a chain, where each version is an edit of the one before and inherits every edit made earlier. Every measurement in this strand so far has been of the independent kind.

One text, one length. A 512-character English-like base, thirty-two copies, six collections a point — a generated text, not the real revisions a corpus that was not generated measured, whose edits are a mixture of all three shapes in proportions nobody here has counted. The seam count is a property of the edit, not the text, but the runs a seam costs depend on how far the text must be read to tell two contexts apart, which a longer or more repetitive base would change.

The three indexes priced from constants. The sizes come from the constants measured earlier, not from building the indexes on these collections; the entropy-bounded index’s 2.11 bits a character is closest to right here of any shape, for the reason the entropy plate gave.

Still open: edits a history inherits #

Every collection in this strand has been a star: one original, and every other copy an independent edit of it. A real version history is a chain — version eight is version seven with one more paragraph changed — so an edit made early is carried by every later version, and the same seam occurs again and again in the same surroundings.

The measurement that follows builds the collection as a chain, each copy an edit of the one before at a share per step, with the three shapes as here, and compares it to a star at the same total share touched in the last copy. The prediction is that an inherited seam costs the transform and the parse almost nothing after its first appearance, since every later copy repeats the seam together with its surroundings, so a chain of thirty-two versions with one move each costs about what a single move costs per version — around three phrases and eleven runs a step — while the star’s last copy, at the same divergence from the original, pays for every one of its predecessors’ moves again. It could fail where edits land on edits: in a chain a later move may cut through an earlier seam, and a seam cut twice may cost more than two seams. The question is whether a collection’s size is set by how different its copies are from the original or by how many edits were ever made, which a star cannot tell apart and a chain can.