The data that is not a number

Edits a history inherits

Every collection of copies measured so far was a star — one original and every other copy an independent edit of it — and a version history is a chain, each version the one before with one more edit. Built as a chain of thirty-two versions with one moved paragraph a step, a collection adds 93 phrases to the Lempel–Ziv parse of identical copies, three a step, exactly what one move costs a star, as predicted; a star whose copies are as far from the original adds 1,285, fourteen times as many. The parse charges an inherited edit nothing. The transform does not quite: a chain of moves costs 15.9 runs a step against eleven predicted, 39% more than a star of one move a copy, while rewritten and scattered edits cost a chain within 5% of a star. And the risk — a later edit cutting an earlier seam — is the common case, nine moves in ten, and costs nothing. A history is priced by how many edits were made, not by how far its copies have drifted.

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, rr, 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, zz, 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 cc is copy c−1c-1 with ee more edits, so copy cc is c⋅ec \cdot e edits from the first and has ee of its own. A star as far apart: copy cc is the first with c⋅ec \cdot e independent edits, at the same distance from the original as the chain’s copy cc, but every edit fresh. And a star of one step a copy: every copy the first with ee independent edits — the earlier essays’ collections, which pay for ee 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, 83.94 phrases for each new edit of moved, rewritten and scattered kinds, a star of one edit a copy 3.15, 10.79, 77.84, within 8%; the transform is as cheap within 5% for rewritten and scattered edits, but moved blocks cost a chain 15.90 runs a step against a star's 11.44 — 39% morePhrases and runs a new edit adds, one edit a step, for a chain of 32 copies and a star of one edit a copy, by the shape of the edit (blocks of 64; scattered edits change 64 characters one at a time): moved blocks: chain 3.00 phrases and 15.90 runs, star 3.15 and 11.44; rewritten blocks: chain 10.53 phrases and 25.42 runs, star 10.79 and 24.51; scattered changes: chain 83.94 phrases and 211.39 runs, star 77.84 and 200.91.a chaina star of one edit a copyphrases an edit (log)runs an edit (log)moved blocks3.0015.903.1511.44rewritten blocks10.5325.4210.7924.51scattered changes83.94211.3977.84200.91one edit a stepphrases and runs an edit
Fig. 1 Phrases and runs a new edit adds, one edit a step, for a chain of 32 copies and a star of one edit a copy, by shape. Moved blocks: chain 3.00 phrases and 15.90 runs, star 3.15 and 11.44. Rewritten: 10.53 and 25.42, star 10.79 and 24.51. Scattered: 83.94 and 211.39, star 77.84 and 200.91.

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 cc of a chain as copy c−1c-1 copied in long phrases, broken only where copy cc’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.90 at one to 11.51 at eight, toward the star's 10.36, 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.47 runs a step at one edit a step and 9.24 at eightMoved blocks of 64 characters, 32 copies, six collections: phrases and runs added for each new edit at 1, 2, 4 and 8 edits a step, for a chain and for a star with the same edits a copy. chain, runs: 1 15.90, 2 14.79, 4 13.52, 8 11.51; star, runs: 1 11.44, 2 11.16, 4 10.95, 8 10.36; chain, phrases: 1 3.00, 2 2.98, 4 2.96, 8 2.90; star, phrases: 1 3.15, 2 3.05, 4 2.98, 8 2.90.051015edits a step (a copy, in the star)added a new edit1248chain, runsstar, runsstar, phraseschain, phrasesmoved blocksa new edit
Fig. 2 Phrases and runs added for each new edit at 1, 2, 4 and 8 moved blocks a step, for a chain and for a star with the same edits a copy. Chain runs: 15.90, 14.79, 13.52, 11.51. Star runs: 11.44 to 10.36. Phrases, both: 3.15 to 2.90.

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 a 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, 8.8 and 4.2 times its runsmoved blocks, 32 copies: phrases and runs added over identical copies, against edits a step, for the chain and for the star whose copy c is c steps' edits from the first. star as far apart, runs: 1 4,356, 2 6,924, 4 9,670, 8 12,021; chain, runs: 1 493, 2 917, 4 1,676, 8 2,855; star as far apart, phrases: 1 1,285, 2 2,136, 4 3,124, 8 4,046; chain, phrases: 1 93, 2 185, 4 367, 8 718.1003001,0003,00010,000edits a stepadded over identical copies (log scale)1248star as far apart, runsstar as far apart, phraseschain, runschain, phrasesmoved blockslog scale
Fig. 3 Phrases and runs added over identical copies against moved blocks a step, for the chain and for the star whose copy c is the first with c steps’ edits. At one a step: 93 phrases and 493 runs against 1,285 and 4,356. At eight: 718 and 2,855 against 4,046 and 12,021.

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 cc holds cc steps’ edits made afresh, 496496 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 itFor chains of 32 copies at 1 to 8 edits a step, moved and rewritten blocks of 64: the share of edits whose block covered a position an earlier edit had touched (for moves, its seams), and the phrases added for each new edit. moved blocks, 1 a step: 91% on an earlier edit, 3.00 phrases; moved blocks, 2 a step: 96% on an earlier edit, 2.98 phrases; moved blocks, 4 a step: 99% on an earlier edit, 2.96 phrases; moved blocks, 8 a step: 99% on an earlier edit, 2.90 phrases; rewritten blocks, 1 a step: 87% on an earlier edit, 10.53 phrases; rewritten blocks, 2 a step: 94% on an earlier edit, 9.22 phrases; rewritten blocks, 4 a step: 97% on an earlier edit, 7.40 phrases; rewritten blocks, 8 a step: 98% on an earlier edit, 5.47 phrases.share landing on an earlier editphrases a new editmoved, 1 a step91%3.00moved, 2 a step96%2.98moved, 4 a step99%2.96moved, 8 a step99%2.90rewritten, 1 a step87%10.53rewritten, 2 a step94%9.22rewritten, 4 a step97%7.40rewritten, 8 a step98%5.47chains of 32 copiesedits on edits
Fig. 4 For chains of 32 copies at 1 to 8 edits a step, the share of edits whose block covered a position an earlier edit had touched, and the phrases each new edit added. Moved blocks: 91% at one a step, 99% at eight, at 3.00 and 2.90 phrases. Rewritten: 86% to 98%, 10.5 to 5.5 phrases.

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

What a history does to the choice of index: 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 10.06 and 40.81; both chains choose the phrase index and both stars the entropy-bounded index at 4.22 kilobytes — a star as far apart is not repetitive enough for either index built on repetitionIndex sizes from the measured constants — 57 bits a phrase, 73 bits a run, 2.11 bits a character — for 32 copies of 512 characters at 1 edit a step: moved blocks, chain: phrase index 1.77 KB, r-index 6.39 KB, entropy-bounded 4.22 KB; moved blocks, star as far apart: phrase index 10.06 KB, r-index 40.81 KB, entropy-bounded 4.22 KB; rewritten blocks, chain: phrase index 3.39 KB, r-index 9.02 KB, entropy-bounded 4.22 KB; rewritten blocks, star as far apart: phrase index 11.75 KB, r-index 40.09 KB, entropy-bounded 4.22 KB.phrase indexr-indexentropy-boundedmoved blocks, chain1.77 KB6.39 KB4.22 KBmoved blocks, star as far apart10.06 KB40.81 KB4.22 KBrewritten blocks, chain3.39 KB9.02 KB4.22 KBrewritten blocks, star as far apart11.75 KB40.09 KB4.22 KB32 copies of 512 characterskilobytes
Fig. 5 Index sizes from the measured constants for 32 copies at one edit a step: moved blocks as a chain, 1.77 KB as a phrase index, 6.39 KB as an r-index, 4.22 KB entropy-bounded; as a star as far apart, 10.06, 40.81 and 4.22. Rewritten blocks: chain 3.39, 9.02 and 4.22; star 11.75, 40.09 and 4.22.

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.

The objects this essay names

Each one links to every other essay that touches it.

Burrows-wheeler transformCompressibilityHonest limitIndex sizeLempel zivR-index