Algorithms & Data Structures
the bound is a claim, and it is checkable
What the libraries do

A collection is a construction

The same characters, arranged as one copy per document or cut across the copies, give a different run count, a different boundary cost and a different answer about which structure to build. Which one a benchmark used is usually not recorded.
19 min read 8 figures Measured, not assumedA model is not a corpusThe measure decides the structure

There is a decision that has to be made before a repetitive collection of documents exists, and every measurement in this strand turns out to depend on it.

The collection can be a version history: d documents, each a near-copy of one base. Or it can be a cut-up text: build the copies into one long string first, then divide the result into d documents at offsets that have nothing to do with where the copies begin.

The two produce the same characters. They differ only in where the document boundaries fall relative to the copy boundaries, and in the first construction those two coincide exactly while in the second they are independent.

That sounds like a detail and it is the difference between a boundary costing 0.15 runs and costing 2.31.

The four cells, and the two measures in eachRuns of the transform and phrases of the parse, per character, on 8,192 characters arranged four ways. The top row is prose and the bottom is 16 near-copies of one base; the left column is one text and the right is that text cut into 16 documents with a separator between them. Everything the repetition strand measured is the bottom left cell and everything the document strand measured is the top right; the bottom right is the one nothing here had filled. Cutting the repetitive text raises r/n from 0.0638 to 0.0768 — 1.20x — and cutting prose raises it from 0.2996 to 0.3053. Those two factors are the subject of the next plate, and they do not come out in the expected order.one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty
Fig. 1 The two texts and the two arrangements, with runs and phrases per character in each cell. The bottom-right is a version history; the same characters cut differently move it.

What differs, quantity by quantity

The run count. A version history cut at the copy boundaries ends every document with the same character of the base, so the block of endings the separators gather is nearly constant and costs almost nothing. A cut-up text ends its documents wherever the cuts landed, so the endings are a sample of the base’s character distribution and cost close to a run each. The price of a boundary is what precedes it is the measurement: six distinct endings against eighteen, nineteen added runs against two hundred and ninety-three.

The phrase count. Almost identical. Both constructions hold the same copies, so the parse finds the same long phrases; the separators break a few of them and the number of breaks is the same either way. This is the quantity a reader would expect to differ and it does not.

The occurrences per document. 1.84 for the version history and 1.88 for the cut-up. Also almost identical, and for the reason one copy per document is one occurrence per document gives: the density is a property of the base and no rearrangement of the copies changes it.

The document array’s entropy. Equal-length documents in both cases, so equal in both. This would differ if either construction produced uneven lengths, and the version history does not.

So of four quantities the constructions differ sharply on one, and it is the one that decides the size of two of the three compressed indexes.

There is a fifth quantity worth adding to that list because it is the one a system operator would notice first, and it does not differ either: the size of the packed text. Both constructions have the same length, the same alphabet before separators, and the same separator count, so they pack to the same number of bits. A collection reported by its on-disk footprint is reported by a number that cannot distinguish them.

And a sixth: construction time. Both take the same time to transform and the same time to parse, to within noise, because both are the same characters in a different order and neither algorithm’s cost depends on that order. So a benchmark reporting build throughput cannot distinguish them either.

The list of things that do not separate the two collections is getting long enough to be the point. Six quantities that a corpus is routinely described by, all identical, and one that differs by a factor of fifteen.

Why the asymmetry is in that quantity

The reason only the run count notices is that only the run count is a property of arrangement at the boundary.

The phrase count asks how much of the text occurs earlier, which is a question about the copies. The density asks how often a pattern recurs in a document, which is a question about the base. The array’s entropy asks how the characters are apportioned, which is a question about the lengths. None of those looks at what sits immediately before a separator.

The run count does, and only because of where a separator sorts. It is first, so its rows are gathered, so their preceding characters form a block, so the block’s internal changes are runs. Every step of that chain is about position rather than content, and position is exactly what the two constructions differ in.

The separators sort first, so their rows hold the documents' last charactersWhy the cut is nearly free on a repetitive collection. A separator sorts before every ordinary character, so its rows sit at the top of the suffix array — and the transform characters in those rows are the LAST characters of the documents. Those characters form one block of the transform, and a block costs one run per change inside it. At 128 documents a repetitive collection cut at one offset of near-identical copies ends with 6 distinct characters and prose ends with 18. The runs follow: 19 added against 293, which is 0.15 a separator against 2.31. The price of a boundary is the entropy of what precedes it.051015255075100125documentsdistinct characters the documents end with+7+52+162+293+4+-1+9+19prosecopies of one basethe label is the runsthe cut added128 documents0.15 against 2.31 runs a separator
Fig. 2 The quantity the two constructions disagree about, isolated: the distinct characters the documents end with, and the runs each cut added.

There is a symmetric statement that makes this less mysterious. The transform gathers positions by their right context; a separator gives d positions an identical right context, so it gathers their left characters. Whether that gathering is cheap is a question about the left characters, and the two constructions differ in exactly the left characters of the boundaries. Every other measure in this strand looks at content or at counts, and this one looks at a specific set of d positions chosen by whoever cut the collection.

That is why the effect is invisible to summary statistics: it is a property of a set of d characters out of n, and d is a thousandth of n on any collection worth the name. No aggregate over the whole text can see a thousandth of it moving, and the transform amplifies exactly that thousandth into a block.

Which one is the real collection

Both are real and they are real in different places, which is why neither can be picked as the default.

The version history is what an archive is. A directory of releases, a document under revision, a table of near-duplicate records, a set of mirrored files: in each, the boundary between documents is the boundary between copies, and it is not a coincidence — the documents are the copies. That construction is the reason this cell was thought to be interesting.

The cut-up text is what a benchmark is. A repetitive corpus is taken off a shelf as one file, split into fixed-size blocks for parallel indexing or for a distributed store, and the block boundaries have no relationship to anything in the data. That construction is what a system actually does to a collection before indexing it.

So a paper reporting “a repetitive collection of documents” has usually measured one and a reader has usually pictured the other, and the two differ by a factor of fifteen on the cost of the thing the paper is most likely to be about.

A third construction exists and is worth naming, because real archives sometimes have it: documents that are near-copies of each other but not of a single base — a chain, where each version is a copy of the previous one with a small change, so document thirty-two differs from document one by thirty-two small changes rather than by one. That is a different repetition structure, its phrases point to the immediately previous copy rather than to a common ancestor, and its copy chain is deep in the sense the character that costs a chain measures.

Its endings are as predictable as the version history’s, so its boundary cost is the same. Its extraction cost is not, and that is the axis on which the three constructions separate. Nothing in this strand measures it; it is named here so that “a version history” is not read as one thing.

What a corpus description has to say

The list of things that turn out to be necessary is short and none of them is standard.

The construction — whether document boundaries coincide with the repeated unit. This is the one that costs a factor of fifteen and it is almost never recorded.

The ending distribution — the number of distinct characters the documents end with, or better, the collision probability of those characters. One number, computable in a single pass, and it predicts the boundary cost directly.

The corrected repetition — r/n and z/n against a shuffled control, so that a falling phrase rate is not read as evidence when it is arithmetic. What repetition is worth once the logarithm is gone is the procedure, and it costs one shuffle.

The query density — occurrences per document for the patterns the workload asks. This decides whether an entire apparatus is worth building and it is not implied by anything else on the list.

Repetition does not give the listing apparatus anything to doOccurrences per document for two patterns, in three collections of 32 documents. The pale bar is the collection's own most frequent 6-character string and the dark bar is a string drawn from one of its documents, which is what a reader asks for. On the drawn pattern all three cells read within a tenth of each other — prose 1.87, one copy per document 1.84, copies cut across documents 1.88. In a collection of versions the copies and the documents are the same partition, so a phrase of the base occurs once in each of d documents: d occurrences and d documents, and a ratio of one. The apparatus needs a pattern that repeats INSIDE a document, and repetition of this kind does not provide one.prose, many short documents2.38 most frequent1.87 drawn from a documentone copy per document4.78 most frequent1.84 drawn from a documentcopies cut across the boundaries2.91 most frequent1.88 drawn from a documentoccurrences per document holding the pattern32 documents · 6-character patternsall three within a tenth on the drawn pattern
Fig. 3 The fourth item on the list, measured on both constructions and on prose: three collections whose descriptions differ enormously and whose densities do not.

Four numbers, all cheap, none of them “the collection is repetitive”. That sentence carries none of the four and is the one usually supplied.

There is a reasonable objection to that list, which is that four numbers is more than anybody will supply and the marginal one is not obviously worth it. The answer is that they are not all needed for every decision. The corrected repetition decides which of three index families to build, and it is needed always. The ending distribution decides the boundary cost, and it is needed only if the collection is being cut. The query density decides whether a listing apparatus is worth adding, and it is needed only if documents are being asked about. The construction is needed to interpret anybody else’s measurements, which is a different use.

So the list is a menu rather than a checklist, and the item that is always needed is the one already standard except for the control. Adding a shuffle to a measurement everybody already takes is the whole of the marginal cost for the most important of the four.

The generated-model trap, one level up

This collection has met a version of this before and it is worth putting the two side by side, because the shape is the same and the level is different.

What the generated collection was right about compared a model-generated corpus against real text and found the model right about some measures and wrong about others, with no way to tell in advance which. The failure there was substituting a model for a corpus.

Here both collections are made of the same real characters. Nothing is generated and nothing is modelled. The failure is substituting one arrangement for another, and it is harder to notice, because the two collections have identical character frequencies, identical entropies, identical phrase counts and identical query densities. Every summary statistic anybody reports about a corpus agrees, and the thing that differs is not summarised anywhere.

That is the sharper version of the trap. A model can be caught by comparing it against real data on enough measures. Two arrangements of the same real data cannot, unless the measure that separates them happens to be one of the ones taken.

Cutting a repetitive text into documents costs it almost nothingRuns per character against the document count, on one fixed text of 8,192 characters cut more and more finely — so nothing moves but the number of separators. The expectation this measurement was made against is that a separator breaks a run, which would make a repetitive collection pay for its document count in the measure it exists to be small in. It does not. Across seven doublings the repetitive line rises by 1.02x and the PROSE line rises by 1.10x — the opposite ordering. In absolute terms the same 127 separators add 19 runs to the repetitive text and 293 to prose. The reason is not in this plate; it is in the characters the documents end with.1101000.1documentsruns of the transform, per characterprose: 1.10xcopies: 1.02x8,192 characters, cutthe control rises further
Fig. 4 What the separation looks like as a sweep: one text cut more and more finely, with prose as a control, where the two lines cross the expected ordering.

There is one more property of this trap worth stating, because it says when to expect it. Two collections indistinguishable on every aggregate must differ in something local, and something local can only matter if some structure amplifies it. The transform is such an amplifier: it takes a set of d positions chosen by the corpus builder and turns them into a contiguous block whose internal structure is charged for.

So the trap arises wherever a structure has an amplifier in it, and the way to look for it is to ask which small sets of positions the structure treats specially. A suffix array’s special positions are the row-zero rotation and the sampled rows. A phrase index’s are the boundaries. A wavelet tree’s are none, which is why nothing in this strand separated the two constructions through the tree.

That is a way of predicting where a corpus-construction detail will matter, and it is more useful than the general advice to be careful. Find the amplifier and the detail that matters is the one it amplifies.

What this does to the earlier numbers

Every number in this strand was measured on both constructions, which is why they can be reported at all. It is worth saying which ones would have been wrong under a single choice.

Measuring only the version history would have produced “cutting a repetitive collection into documents is free”, which is a factor of fifteen away from what a benchmark’s blocks cost. Measuring only the cut-up would have produced “a repetitive collection pays about a run per boundary”, which is wrong about every archive.

The occurrences-per-document result survives either choice, and that is what makes it a strong retraction rather than a construction artefact: both constructions give a density indistinguishable from prose’s, so the negative result about the listing apparatus does not depend on the decision at all.

The index sizes survive too, at a couple of per cent. So of the strand’s four findings, one is construction-dependent, two are not, and one — the two-currency separator result — is dependent in one currency and not the other.

A separator each is paid in the alphabet, not in the runsThe three joins on a collection of 32 near-copies. Running the documents together costs nothing and invents strings no document contains. One shared separator raises the alphabet from 21 symbols to 22 and the runs by 1.00x — which is to say by nothing. Giving each document its own raises the alphabet to 52, which crosses a power of two and so costs a whole bit on every character of every document: 20.2% on the packed text. It costs 2.9% in runs. The two currencies disagree by more than an order of magnitude, and a collection that needs distinct boundaries should be told which one it is paying in.run together1.00xsigma 21 · 5 bitsone separator1.00xsigma 22 · 5 bitsa separator each1.20xsigma 52 · 6 bitsruns 1.00xruns 1.00xruns 1.03x32 documents of 512 characterspacked bits, against running them together
Fig. 5 The finding that is half dependent: the packed cost of a join is the same under both constructions and the run cost is not.

What the strand as a whole came out at

It is worth collecting the strand’s findings in one place, because the pattern across them is more informative than any of them.

The cell was expected to be where a compressed index and a large document count meet — where the structures suffer from the fragmentation and the queries benefit from the repetition. Neither happened. The structures do not suffer: cutting a versioned collection into a hundred and twenty-eight documents costs its run count two per cent, which is inside the noise of any real decision. The queries do not benefit: a pattern drawn from a document occurs 1.84 times per document holding it, which is prose’s number, because the copies and the documents are the same partition.

What did happen is that three separate quantities turned out to be charged somewhere other than where the argument for them put them. A separator’s cost is in its neighbours rather than in what it interrupts. Repetition’s benefit to a listing apparatus is in the base rather than in the copying. And a collection’s identity, for the purposes of every structure here, is in the placement of its boundaries rather than in its content.

On a genuinely repetitive collection the fall is the collectionPhrases per character against size, with the axis being the copy count at a fixed base of 2,048 characters — so the arrangement changes and the alphabet does not. The pale line is a shuffle of the same characters: same length, same alphabet, same zeroth-order entropy, no arrangement. It falls by 1.45x across the sweep, which is the logarithm every text pays because z/n is about one over log_sigma n. The collection falls by 4.71x, so what the repetition is actually worth is 3.24x. On real prose the same two-ended measurement left 1.37x; here the control accounts for 30.8% of the raw curve rather than for most of it, which is the difference between a collection that repeats and one that is merely predictable.10⁴0.1charactersphrases of the parse, per charactershuffled: 1.45xthe collection: 4.71x4,111 to 65,551 charactersworth 3.24x after the control
Fig. 6 The one expectation the strand confirmed: on a collection built of copies, most of the fall in the phrase rate is the arrangement rather than the arithmetic.

The one expectation confirmed is the size sweep. On a genuinely repetitive collection the fall in phrases per character is 3.24 after its control, against 1.37 on prose — the structures really are built on something real, and the correction that removed most of prose’s headline removes less than a third of this one.

Cutting a repetitive text into documents costs it almost nothingRuns per character against the document count, on one fixed text of 8,192 characters cut more and more finely — so nothing moves but the number of separators. The expectation this measurement was made against is that a separator breaks a run, which would make a repetitive collection pay for its document count in the measure it exists to be small in. It does not. Across seven doublings the repetitive line rises by 0.99x and the PROSE line rises by 1.01x — the opposite ordering. In absolute terms the same 127 separators add 6 runs to the repetitive text and 156 to prose. The reason is not in this plate; it is in the characters the documents end with.1101000.1documentsruns of the transform, per characterprose: 1.01xcopies: 0.99x8,192 characters, cutthe control rises further
Fig. 7 The same cut on a four-symbol alphabet, where fewer distinct endings are available and both collections are pushed toward the same bound.

The practice that comes out

Three habits, and the first is the one that would have caught everything else.

Build a collection two ways when the boundary placement is a choice. Not as a robustness check but as a measurement: the difference between them is a quantity, and here it was the largest quantity in the strand.

Report the arrangement, not just the content. Two thousand documents of two hundred characters and a million characters of the same thing are this collection’s two corpus descriptions, and both name a size and a document count and neither names a construction. The four numbers above are a corpus description that another person could use. “Two hundred megabytes of versioned source” is not, and neither is a compression ratio.

Expect the separating measure to be the one nobody takes. A corpus that was not generated is where this collection stopped trusting a generated model, and the lesson generalises further than it was written for: a real corpus arranged two ways is still two corpora. Character frequencies, entropies, sizes and compression ratios are all reported by default, and all four agree between these two collections. What separates them is a distribution over positions immediately preceding a boundary, which nothing reports because nobody has needed it before.

One index does not notice the repetition and two of them are made of itThree compressed indexes on 8,192 characters, against how many near-copies the text is made of — which in this cell is also the document count, because each document is one copy. The entropy-bounded FM-index is flat at about 6.4 bits a character throughout: the transform is a permutation, so its zeroth-order entropy is the text's, and no amount of repetition changes it. The run-length index falls from 18.5 to 3.4 and the phrase index from 9.1 to 1.6. At one copy the two repetition-aware structures are the LARGEST of the three, by a factor of 2.88x; the crossing is what decides which structure a collection wants, and it is a property of the collection rather than of the field.051015204060documents, which here is also the copy countbits a characterFM-indexrun-length indexphrase index8,192 characters throughout2665 runs down to 427
Fig. 8 What the choice ultimately decides: which of three structures is smallest, and by how much, on a collection whose description is the same either way.

Underneath the three is a question about what a corpus is, and it has a short answer that this strand earned. A corpus is not a bag of characters. It is a bag of characters together with a partition, and the partition is data. Every structure here charges for the partition somewhere — the alphabet, the run count, the document array’s width, the boundary block — and a description that omits it has omitted an input.

That is not a deep observation and it is not one this field’s own conventions reflect. Corpus descriptions in this area are sizes, alphabet sizes and compression ratios, all of which are functions of the bag alone.

The last of those is the generalisable part. A measurement that separates two objects the standard statistics agree about will not be a standard statistic, by definition — if it were, they would not agree. So a strand that finds two collections indistinguishable on everything it measured has either found them the same or has not measured the right thing, and telling those apart requires constructing the difference deliberately rather than looking for it.

Where this goes next

051015204060documents, which here is also the copy countbits a characterFM-indexrun-length indexphrase index8,192 characters throughout2665 runs down to 427 The 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. 100100occurrences of the patternreadsmost frequent ", and " · 388 occurrencesthe scanthe chain12 documents · 144,617 characters3 of 6 won What the generated collection was right about Five strands of conclusions, drawn on collections made by one line with one dial, checked against a corpus nobody made. Most hold. One headline was a property of the generator's alphabet, and one crossing that was guessed at turns out to be met — but only with the structure the strand on range minima built. one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty The 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.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

Burrows-wheeler runsControlCorpusDocument collectionIndex sizeMeasurement designPhrase countRepetitionSeparator