Edits a history inherits
A repetitive collection is small to index only if the index can see the repetition — which the entropy that cannot see a copy found no entropy can — and two measures decide whether it can: the runs of the Burrows–Wheeler transform, , which set the size of the index that stores the runs, with a floor under a run count beneath it, and the phrases of the Lempel–Ziv parse, , which set the size of the phrase index. The collection decides which index is small turned both into sizes with three measured constants — about 57 bits a phrase, 73 bits a run, 2.11 bits a character for the entropy-bounded index — and a paragraph rewritten, not a letter changed found that the shape of a collection’s edits decides the measures more than how much was changed.
A paragraph moved costs its seams measured the third shape: a block cut from one place in a copy and pasted at another. A move changes no character, and it cost what its three seams cost — about three phrases and eleven runs whatever the block’s length — so a tenth of the copies moved in blocks of 64 was cheaper for both measures than any other shape at the same share.
Every collection in that strand was a star: one original, and each of 31 other copies an independent edit of it. That essay’s closing section named what a real version history is instead. A 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 prediction: an inherited seam costs the transform and the parse almost nothing after its first appearance, 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 a star whose last copy is as far from the original pays for every one of its predecessors’ moves again. The risk: a later move may cut through an earlier seam, and a seam cut twice may cost more than two.
Three collections of the same edits
Each collection is 32 copies of the same 512-character English text, and each is built three ways with the same edits. A chain: copy is copy with more edits, so copy is edits from the first and has of its own. A star as far apart: copy is the first with independent edits, at the same distance from the original as the chain’s copy , but every edit fresh. And a star of one step a copy: every copy the first with independent edits — the earlier essays’ collections, which pay for edits a copy once.
The edits come in the earlier essays’ three shapes, at 64 characters an edit. A moved block: 64 consecutive characters cut and pasted elsewhere in the same copy. A rewritten block: 64 consecutive characters replaced by fresh text from the same source. Scattered changes: 64 characters replaced one at a time at random places. Every measure is the excess over 32 identical copies, averaged over six collections, so a number is what the edits added.
The hero plate is the comparison the proposal asked for, at one edit a step. For moved blocks the chain adds 93 phrases and 493 runs to identical copies; the star as far apart adds 1,285 and 4,356, fourteen and nine times as many; the star of one move a copy adds 98 and 355. For rewritten blocks and scattered changes the picture is the same in shape: the chain and the star of one edit a copy close together, the star as far apart far above both.
What a new edit costs
An inherited edit costs the parse almost nothing for every shape — a chain pays 3.00, 10.53 and 83.94 phrases for each new moved, rewritten and scattered edit, a star of one edit a copy 3.15, 10.79 and 77.84, within 8% — and the transform is as cheap within 5% for rewritten and scattered edits; but moved blocks cost a chain 15.9 runs a step against a star’s 11.4, 39% more. Half the prediction holds exactly. The parse reads copy of a chain as copy copied in long phrases, broken only where copy ’s own edit lies, so every inherited edit is inside a phrase that copies it from the version before. Three phrases a move a step is what one move in a star costs, to a twentieth.
The other half fails for one shape. A rewritten block or scattered changes cost a chain’s transform what they cost a star’s, a few per cent more; a moved block costs it 39% more, 15.9 runs a step where 11 were predicted. The transform sorts every suffix of the collection by what follows it, and a chain is the first kind of collection in this strand in which the same seam appears in many copies with different seams after it: copy ten carries moves one to ten, copy twenty moves one to twenty. The suffixes just before an early seam are identical across all the later copies up to the next seam each copy has, and then they differ; the sort orders them by those later differences, and the characters before them come out of the sort in an order the later seams decide.
That is a mechanism the plate is consistent with rather than one it measures. What it measures is that the extra cost is a property of moves and not of rewrites, and the next plate says how it grows.
Runs a step, not runs an edit
With more moved blocks a step, a chain’s runs a new edit fall from 15.9 at one to 11.5 at eight, toward the star’s 10.4, while its phrases a new edit stay at 3.00 to 2.90, the star’s to a twentieth; the transform’s extra cost over the star grows more slowly than the edits, 4.5 runs a step at one edit a step and 9.2 at eight. If each inherited seam cost the transform something in every copy that carries it, the extra would grow with the edits made; it grows with less than their square root. Eight times the edits a step doubles the extra runs.
Read as a cost per version, that is good news for a real history, which makes several edits between versions. A version history whose versions differ by eight paragraphs moved costs the transform 92 runs a version and the parse 23 phrases; a star of the same edits a copy costs 83 and 23. At that rate of editing, the two collections are nearly the same size to both indexes, and the chain’s inheritance is invisible to the parse and a tenth of the transform.
The phrases do not move at all with the edits a step, and that is the parse’s whole account of a history: each new edit is three phrases where it lands, and everything inherited is copied from the version before at no cost. Lempel–Ziv sees the chain as the chain it is.
A history against a star as far apart
The gap between a history and a star of the same distances narrows as the edits a step grow, because the star’s later copies are so far from the first that new edits overlap old ones: for moved blocks the star as far apart costs 13.8 times the chain’s phrases at one edit a step and 5.6 times at eight, and 8.8 and 4.2 times its runs. The star pays for every edit in every copy: copy holds steps’ edits made afresh, moves in all at one a step against the chain’s 31. If each cost its seams the star would cost sixteen times the chain; it costs fourteen times in phrases, because some of copy 31’s moves land on others in the same copy.
At eight moves a step the star’s last copies are scrambled — copy 31 holds 248 moves of 64 characters in a text of 512 — and new moves mostly rearrange text that is already rearranged, so they add less. The star’s per-move cost falls from 2.6 phrases at one a step to 1.0 at eight. The chain’s stays at three, because every chain copy has only its own step’s moves to pay for.
This is the plate that answers the proposal’s question. A star cannot tell apart a collection whose copies are far from the original because many edits were made and one whose copies are far because each was edited heavily; a chain can, and its size follows the edits made — 31 steps’ worth — while the star’s follows the distances, 496 steps’ worth.
Edits on edits
The risk is the common case and costs nothing: 91% of a chain’s moved blocks at one a step land on an earlier edit’s seam and 99% at eight, yet each still costs 3.00 and 2.90 phrases — an edit cut through an older one replaces a seam rather than adding to it. A block of 64 characters in a text of 512 covers an eighth of it, and after a few versions every eighth of the text holds a seam; by the middle of the chain nearly every move cuts one. If a seam cut twice cost more than two seams, the cost a move would rise along the chain, and it does not.
Rewritten blocks show the same thing more strongly. At eight rewrites a step a new rewrite costs 5.5 phrases against 10.5 at one, because it often lands on text an earlier rewrite already replaced, and a block of fresh text over fresh text is a smaller change to the parse than over the original: the edge it creates is new, but much of the interior it replaces was already a phrase of its own. The scattered changes, which mark single characters, never land on each other’s marks in a way the count registers.
So the named risk inverts. Edits on edits are cheaper than fresh ones for the parse, and for the transform they are what brings a chain’s runs a move down toward the star’s as the edits a step grow.
The index a history would choose
At one edit a step the chain of moved blocks is 1.77 kilobytes as a phrase index and 6.39 as an r-index; the star as far apart is 10.06 and 40.81, and both stars choose the entropy-bounded index at 4.22 kilobytes — a star as far apart is not repetitive enough for either index built on repetition. The plate turns the measures into the decision the strand has been asking about. Both chains choose the phrase index, by a wide margin over the r-index. Both stars of the same distances choose the index that does not exploit repetition at all, because a collection whose every copy is edited afresh at every distance is, at these sizes, not much more repetitive than its text.
A collection judged by how far its versions are from the first would be judged a star and indexed as one, at twice the size the phrase index needs. The thresholds of the collection decides which index is small — the phrase index wins under 0.037 phrases a character — are met by the chains, at 0.016 and 0.030 phrases a character for moved and rewritten blocks, and missed by the stars, at 0.088 and 0.103.
The r-index loses on every collection here, and on the chain of moves by more than elsewhere: its runs carry the 39% extra that inheritance costs the transform. That is the one place a history is dearer than its edits, and it falls on the r-index, which already trailed the phrase index on every star of moved blocks the earlier essay measured.
Distance or edits
The question the proposal closed on was whether a collection’s size is set by how different its copies are from the original or by how many edits were ever made — a question a star cannot answer, because in a star the two are the same number. A chain separates them, and the answer is edits. A chain of 31 steps is priced at 31 steps’ worth of seams by the parse, exactly, and at a little more by the transform; a star whose copies reach the same distances is priced at 496 steps’ worth, less what its overlapping edits share.
The phrases a text copies from itself described the parse as copying each part of a text from somewhere earlier, and in a chain there is always an earlier copy that differs only by one step. That is what makes a version history cheap: not that its versions are similar to the first, but that each is similar to the one before, and an index built on copying needs only the second.
The difference matters to anything that decides an index from a summary of the collection. A system that measured how far each stored version had drifted from the first — a natural summary, and the one a star’s dial is set by — would see the chain’s last copies as heavily edited and conclude, from the thresholds, that repetition no longer pays. The chain’s own record says otherwise: thirty-one steps of one move each, ninety-three phrases in all. The quantity that predicts the phrase index’s size is the count of edits a version history logs, which a version-control system keeps anyway, and not the distance between its first and last versions, which nobody needs to compute. For the r-index the log undercounts by the 39% that inheritance costs the transform for moves, a correction that the edits’ shape, also in the log, can supply.
What the measurement leaves out
Short texts, small collections. Everything here is measured at sizes where what is still proportional to n — the sampled positions every such index keeps — would dominate a real index’s bytes. Thirty-two copies of 512 characters, so a block of 64 is an eighth of a copy; a real history’s paragraphs are a much smaller share of a document, and its seams land on each other less often.
A straight chain. Every version descends from the one before; a history with branches — two versions edited from the same parent — is neither a chain nor a star, and was not built.
Edits of one shape at a time. Each collection uses one shape; a history mixes moves, rewrites and small changes in every version.
Still open: a history that branches
A real version history is rarely a straight line. Work branches — two people edit the same version, and both results are kept — and sometimes merges back. A branched history has copies whose nearest relative is not the copy before them in the collection’s order but a sibling several copies back, and a parse that copies from earlier text finds that relative only if it is earlier in the order the collection is stored in.
The measurement that follows builds trees of 32 versions — every version the edit of a parent chosen at random among those before it — with one move a step, and stores them in the order they were made and in a depth-first order that puts each version beside its parent. The prediction is that the parse stays at three phrases a step in either order, since every version’s parent lies somewhere before it, and that the transform’s extra cost over a star rises from 39% in a chain toward twice that in a tree stored by creation, because each seam is followed by more different seams across its descendants. It could fail on the parse’s reach: a phrase that copies from a parent sixteen copies back is still one phrase, but a parse with a bounded window would not find it. The question is whether the order a collection is stored in matters to an index that copies, or only the tree its versions form.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- A sampling that costs more than the array burrows-wheeler transform · compressibility · honest limit · index size · r-index
- The measure that cannot see the alphabet burrows-wheeler transform · compressibility · index size · r-index
- The sampling that follows the runs burrows-wheeler transform · compressibility · index size · r-index
- A parse that will not follow a long chain compressibility · honest limit · index size
- A search that runs backwards burrows-wheeler transform · honest limit · index size
- An index with z in its size compressibility · index size · r-index
The objects this essay names
Each one links to every other essay that touches it.
Burrows-wheeler transformCompressibilityHonest limitIndex sizeLempel zivR-index