One copy per document is one occurrence per document

The document-listing apparatus exists for one situation, and it is worth stating in the sharpest form before anything is measured.

Given the rows of a pattern in a suffix array, the documents holding it can be read off by visiting every row and looking up its document. That costs the occurrences. The output-sensitive method — a previous-occurrence chain, a range minimum over it, a walk that reports each document once — costs something proportional to the documents, with a logarithmic factor and a substantial constant.

So the apparatus is worth building exactly when a pattern occurs many times in each document that holds it. If a pattern occurs once per document, the two methods do the same amount of work and one of them needs three extra arrays.

The crossing that never arrives measured that ratio on a collection of two thousand short prose documents and found 1.04 occurrences a document, against a crossing sitting at 10.8. The apparatus cost 2.64 times the index it sat on and won nothing at all. The conclusion drawn there was that prose is the wrong collection: a phrase in ordinary text is rare, and a collection of short prose documents holds each phrase about once.

That conclusion points at an obvious next collection. A repetitive one. A pattern in the base of a versioned collection occurs once in every copy, and thirty-two copies is comfortably past a crossing at eleven.

The measurement #

Three collections of thirty-two documents over the same eight thousand characters. Prose cut into thirty-two pieces. A version history: thirty-two near-copies of a base, one per document. And the same repetitive characters cut into thirty-two documents at arbitrary offsets, so a document may straddle a copy boundary.

Two patterns in each, because the choice of pattern is not neutral and pretending it is has been a mistake here before. The first is the collection’s own most frequent six-character string, which is what a collection’s statistics offer. The second is a string drawn from one of the documents, which is what a reader actually asks for.

On the drawn pattern the three collections read 1.87, 1.84 and 1.88 occurrences a document. All three within a tenth of each other; none of them within a factor of five of the crossing.

On the most frequent string they read 2.38, 4.78 and 2.91. The versioned collection is genuinely denser there, and the most frequent six-character string of an English-like text is a fragment of a common word — a space, a definite article, a common suffix — which is not a query.

The gap between the two patterns is the first thing worth reading. On prose the most frequent string is 1.27 times as dense as a drawn one; on the version history it is 2.59 times. So repetition does change something — it makes the collection’s own extremes more extreme — and what it changes is not the quantity anybody would query.

That is a specific instance of a general trap in reporting a collection’s statistics. The most frequent anything is drawn from the tail of a distribution, and copying a text multiplies its tail along with everything else. A structure sized against the most frequent pattern is sized against a query nobody makes, and a structure sized against the mean is sized against a distribution whose shape is the whole question. Distributions, not averages is the habit this collection has settled into for exactly this reason, and the two-pattern plate above is that habit applied to a density.

Why the ratio is one by construction #

The arithmetic is a single line once it has been seen, and the reason it took a measurement to see it is that the sentence naming this cell had the wrong noun in it.

In a version history the copies and the documents are the same partition. A phrase of the base occurs once in each copy. Each copy is one document. So the pattern has d occurrences spread over d documents, and the ratio is one — for every d, at every divergence, on every base text.

Repetition of that kind is repetition between documents. The ratio the listing apparatus turns on is a ratio within them. Those are different quantities and one of them cannot be increased by increasing the other.

That is the retraction, and it is exact rather than approximate. It also says why the measured numbers are 1.84 rather than 1.00: the base is prose, so a six-character string drawn from it occurs a couple of times in the base by ordinary chance, and those extra occurrences are copied along with everything else. The 1.84 is the base’s own internal density, unchanged by any amount of copying. Multiply the copies by a hundred and the ratio stays at 1.84.

The independence of the two quantities can be pushed further, and it is worth doing because it disposes of every variant of the original hope at once.

Increase the copy count: occurrences rise, documents rise by the same amount, ratio unchanged. Increase the divergence between copies: some occurrences are destroyed, so both fall together and the ratio falls slightly. Lengthen the base: more occurrences of a given pattern per copy, so the ratio rises — but that is the base’s internal density again, not the copying. Shorten the documents by cutting each copy in half: occurrences unchanged, documents doubled, ratio halved.

Every operation that makes the collection more repetitive in the sense the compressed indexes care about leaves the ratio alone or lowers it. There is no dial on a version history that raises it, which is what “by construction” means and why this does not need re-measuring at other parameters.

The third construction, and why it barely helps #

Cutting the copies across the document boundaries should break the coincidence, because a document no longer corresponds to a copy. It reads 1.88 — a hundredth above the version history.

The reason is that cutting the partition differently does not change how many occurrences there are or how spread out they are; it changes only which occurrences share a document. Thirty-two occurrences distributed over thirty-two documents at arbitrary offsets land, on average, one per document, whatever the offsets are. Getting two occurrences into one document requires two copies to fall inside one document, which requires documents longer than the base — and a collection of documents longer than its base is a collection of fewer, longer documents, which is the cell to the left.

So the whole two-by-two has one property in common: a pattern’s occurrences per document is a property of the base text, not of the collection built from it. Copying the base, cutting the copies and joining them in any arrangement all leave the density where the base put it.

There is one construction that does move it and it is worth naming so that the claim is not stronger than it should be: a collection where the documents are the repeated unit rather than the copies. Take one document that internally repeats a phrase forty times, and make thirty-two near-copies of it. Every copy has forty occurrences and there are thirty-two documents, so the ratio is forty. The apparatus wins comfortably.

But the forty came from the base document, not from the copying. The same forty would be there with one copy and one document. So the collection is not paying its density to repetition; it is inheriting it from a base that was already dense, and the copies are along for the ride. That is the sense in which the ratio is a property of the base: whatever it is before copying, it is after.

What would move it #

It is worth being constructive about the collection that would make the apparatus pay, because the negative result is only useful if it says where to look instead.

The requirement is a pattern occurring many times inside a single document. That is a property of long documents with internal repetition: a source file with a repeated idiom, a log file with a repeated message, a genome with a repeated motif, a legal document with a repeated clause. In each of those a query occurs dozens of times in one document and appears in a handful of documents out of thousands.

That is a real shape and it is not the one anybody reaches for when they say “a repetitive collection”. The phrase in the literature means near-identical documents — versions, mirrors, near-duplicates — and that is exactly the shape that cannot produce the ratio.

Two collections, both correctly described as repetitive, with opposite answers about whether an entire apparatus is worth building. A model is not a corpus is the general version of that, and this is a sharper instance than the one it was written for: not a generated model behaving differently from real text, but two real shapes that share a word.

Lengthening the pattern makes this worse rather than better, which is the direction a reader might not expect. A longer pattern is rarer, so it occurs in fewer documents — but its occurrences fall at least as fast, because most of the occurrences it loses are the extra ones inside a document rather than the one per copy. So the ratio moves toward one from above as the pattern lengthens, and the collection’s own most frequent string is short for exactly the reason that makes it dense.

That means a workload of long, specific queries — which is what a search over a versioned archive mostly is — sits at the least favourable end of this. The apparatus is furthest from paying precisely where the collection is most useful.

The number that should have been quoted #

There is a reporting failure underneath this and it is the same one this collection keeps finding.

“This collection is repetitive” was treated as a reason to expect the listing apparatus to pay. It is not a reason for anything about the listing apparatus. The quantity the apparatus turns on is occurrences per document for the patterns the workload actually asks, and that quantity has a name, is one number, and takes a second to measure on a collection already in hand.

A sixth of what, exactly makes the general argument: a quoted share carries what it is a share of. This is the same rule applied to a quoted property — “repetitive” is a share of something too, and which something decides whether it is relevant.

The practical form is a decision procedure with one step. Before building a document-listing apparatus, take the twenty patterns the workload asks most often, count their occurrences and count the documents holding them, and divide. If the answer is under about ten, the apparatus will lose to reading every occurrence, and the collection’s repetitiveness has nothing to do with it.

What is still true about the apparatus #

None of this makes the apparatus useless, and it is worth separating the two claims.

The apparatus is correct and its cost genuinely is proportional to the answer rather than to the range — the cost that is the size of the answer established that and it is not in question. The strand that removed the chain and then the range minimum made it three times smaller and then eight times smaller again, and every one of those improvements stands.

What is in question is when the proportionality is worth having. A method proportional to the answer beats one proportional to the range when the range is much bigger than the answer, and on every collection this field has built the range is about twice the answer. The improvements to the apparatus made a structure that loses by less.

That is not nothing. An apparatus costing 14% of what it cost, as the apparatus, three times smaller again measures, changes the crossing: the constant falls, so the ratio at which the method starts winning falls too. Whether it falls below 1.87 is a question about the constants, and it is the one measurement that would turn this negative result into a positive one.

There is a second measurement that would be worth having and this collection has not made: the crossing itself, on the improved apparatus, measured rather than inherited. The 10.8 quoted throughout came from a structure holding a chain, a range minimum and a document array. The current one holds a compressed document array and nothing else, and its per-document cost falls as the answer grows rather than rising. Where the two lines cross now is an open number, and it is the one number that would decide whether any of this is worth building.

That measurement is not made here for a reason worth stating: it needs a collection with a density above the crossing to be measured at, and the point of this essay is that no collection in this field has one. Constructing one to measure a crossing would be constructing the answer, which is the failure a model is not a corpus exists to prevent.

Two things a corpus can be #

The last thing worth extracting is a distinction the word “repetitive” has been carrying without marking.

A collection can be repetitive in the sense that the collection contains copies of itself, which is what the run count and the phrase count measure and what makes a compressed index small. That is a global property, and it is the one every structure in this field is built on.

A collection can also be repetitive in the sense that a query occurs many times in one place, which is what an output-sensitive method needs. That is a local property of the query and the document, and nothing in the first sense implies it.

The two are independent. A collection of thirty-two identical documents is maximally repetitive in the first sense and has a density of exactly one in the second. A single document consisting of one sentence repeated a thousand times is repetitive in both. A thousand documents each containing one repeated sentence, all different, is repetitive in the second and not the first.

Every structure this field builds is indexed by the first. The one apparatus that is not was measured on collections chosen for the first, twice, and lost both times.

What a reader should take from a word #

There is a practical instruction hiding in the distinction above and it is short enough to state as one.

When a paper, a benchmark or a colleague says a collection is repetitive, ask which sense. If the answer is “it contains near-duplicate documents”, every compressed index in this field will be small on it and no output-sensitive listing method will pay. If the answer is “individual documents repeat themselves internally”, the listing methods may pay and the compressed indexes may not be especially small, because internal repetition inside short documents produces far fewer long phrases than duplication between them.

The two are usually conflated because the benchmark corpora used in this area happen to have both — a versioned software repository has near-duplicate files and individual files full of repeated idiom — and a structure measured on one of those cannot say which property it was benefiting from. Separating them requires two collections that have one property each, which is what the three cells above are, and it is why the negative result here is worth more than a re-measurement on a larger archive would have been.

The index that does not notice draws the first sense as three curves, and the price of a boundary is what precedes it shows that even the cost of cutting a collection into documents is decided by a property of the documents rather than by their number. Every quantity in this cell turned out to be like that: named after the collection, decided by something one level down.

The deferral, answered #

The sentence that named this cell called it the one where a compressed index and a large document count meet. They do meet, and the meeting is uneventful.

The compressed index is smaller, by a factor of five in the run-length structure and six in the phrase structure, and the document count costs it almost nothing. The listing apparatus is smaller too, by a factor of seven, and it still loses. Neither of those outcomes needed the other; the two halves of the cell turn out to be independent, which is itself the answer to the question of whether they interact.

A deferral answered by a retraction is worth as much as one answered by a number, and this one is worth slightly more than usual, because the retraction has an exact arithmetic reason rather than an empirical one. Nobody needs to re-measure it on a larger version history. The copies and the documents are the same partition, and one over one is one.