The cell nobody filled

Two questions have been asked here about text, and they have never been asked at the same time.

The first is how much does this text repeat, and the structures that answer it — the run-length index, the phrase index — were measured on one long text made of near-identical copies. The second is which documents hold this pattern, and the structures that answer it — the document array, the range minimum, the chain — were measured on prose cut into short pieces.

Those are two cells of a two-by-two. The other two are a single prose text, which is where this collection started, and a repetitive collection of many short documents, which is where a real archive of versioned files actually lives and which nothing here had ever built.

What the margins say, and what they cannot #

Read across the top row and the effect of cutting prose into documents is small: runs per character move from 0.2996 to 0.3054, phrases from 0.1273 to 0.1302. Read down the left column and the effect of repetition is enormous: runs fall from 0.2996 to 0.0638, phrases from 0.1273 to 0.0354. The first effect is a couple of per cent and the second is a factor of nearly five.

A reader with those two margins would predict the empty cell by multiplying, and would get 0.0651 runs a character. The measured figure is 0.0769. That is 18% over the prediction, which is not a rounding error and is not nothing.

The reason the two effects do not simply compose is that a separator is not a neutral character. It is a symbol that occurs nowhere else in the collection, so it stops a phrase that would have spanned the boundary, and it appears in the transform in a block of its own. Both of those are interactions with the arrangement, and an arrangement is exactly what repetition is.

But the sign of the interaction is not obvious in advance, and this is where the strand stopped being a filling-in exercise. Three effects arrive together and they do not agree about which way to push.

A separator breaks a phrase, which should raise the phrase count on a text whose phrases are long — and a repetitive text is precisely a text whose phrases are long. A separator raises the alphabet, which costs every character of every document a fraction of a bit, and that cost is paid whether the collection repeats or not. And repetition is supposed to be what makes document listing worth doing, because a pattern in the base occurs once in every copy and the whole output-sensitive apparatus exists for patterns that occur far more often than they occur in documents.

Three mechanisms, two of them working against the structures and one of them working for the query. Nothing about the two margins says which wins, and the honest answer is that this had to be built.

The construction is part of the measurement #

There is a decision to make before anything can be measured, and making it silently is how a number about one collection becomes a number about collections.

A repetitive collection of many short documents can be built two ways. One is a version history: each document is a near-copy of one base, so the collection is d documents that resemble each other. The other is a long repetitive text cut up: build the copies first, then divide the result into d documents at arbitrary offsets, so a document may straddle a copy boundary and hold a fragment of one copy followed by a fragment of the next.

Those two constructions produce the same characters in a different arrangement. They are not interchangeable, and the repetition measures do not agree about them — which is the reason both are carried through every plate in this strand rather than one being chosen and the choice forgotten.

The version history is the shape a real archive has. A directory of releases, a document under revision, a table of near-duplicate records: in every case the boundary between documents is also the boundary between copies. That coincidence turns out to matter more than anything else in this strand, and it is the subject of two later essays.

The cut-up text is the shape a synthetic benchmark has, because it is what a repetitive corpus taken off a shelf and split becomes. It has no reason to align its boundaries with anything.

The cut, with its control beside it #

The experiment that isolates the separator is to hold the characters fixed and vary only how many boundaries are dropped into them. Build the repetitive text once; cut it into one document, then two, then four, out to a hundred and twenty-eight; and measure the runs each time.

That design matters and the obvious alternative is wrong. Building a collection of d near-copies at a fixed total length makes the base shorter as d grows, so the text becomes more repetitive and its run count falls — and the plate then shows the cut being free when what it is showing is a different text at every point. A corpus that was not generated records the general version of this: the axis has to be the thing being varied and nothing else.

The control is prose of the same length, cut identically. That is the convention the half of a fall that is the logarithm set: a sweep whose axis could be moving something incidental draws the incidental thing beside it, and the check is two-ended — the control must move, and its movement must account for less than the raw curve.

Across seven doublings the repetitive line rises by a factor of 1.02. The prose line rises by 1.10. The cut costs prose five times what it costs the repetitive collection, which is the opposite of what the phrase-breaking argument predicts, and it is the finding this strand opened with.

The separator is charged where nobody was looking #

The mechanism is not in the phrases at all. It is in where a separator’s rows sit.

A separator sorts before every ordinary character, so in the suffix array its d rows are at the very top. The transform characters in those rows are the characters that precede the separators — which is to say the last characters of the documents. Those d characters form a contiguous block of the transform, and a block of the transform costs one run per change inside it.

So the price of cutting a text into documents is the number of distinct characters the documents end with, in the order the separators sort. Not the document count. Not the collection’s size. Not whether the collection repeats.

A version history cut at the same offset of near-identical copies ends every document with almost the same character. At a hundred and twenty-eight documents it ends with six distinct characters, and adds nineteen runs. Prose ends with eighteen, and adds two hundred and ninety-three. That is 0.15 runs a separator against 2.31 — a factor of fifteen — and it explains the whole of the ordering the previous plate showed.

The result is worth stating in the general form, because it is not about documents: the price of a boundary is the entropy of what precedes it. A collection whose documents end predictably pays almost nothing for its boundaries in the run count, and one whose documents end unpredictably pays a run each. That is a property of the collection’s shape rather than of its size, and it is invisible to every account of separators this collection had written down.

The other currency #

None of that means the separator is free. It means it is charged somewhere else.

One separator or one for each priced the three joins on prose: running the documents together invents strings no document holds, one shared separator fixes that and raises the alphabet by one symbol, and giving each document its own separator raises the alphabet by d. That third option is what a collection needs if a pattern must not be reported as spanning two documents, and its cost is paid by every character of every document through the width of a packed symbol.

On a repetitive collection the same three joins behave differently in the two currencies, and the gap between them is large.

One shared separator costs 0.2% in packed bits and nothing at all in runs — the run count actually falls, because the separator’s block is more uniform than the characters it displaced. Distinct separators raise the alphabet from twenty-one symbols to fifty-two, which crosses a power of two, so every character of the collection needs a sixth bit: 20.2% on the packed text. In runs, the same change costs 2.9%.

A collection that needs distinct boundaries should be told which of those two it is paying in, and the answer depends entirely on which structure it is going into. Documents that are not the same length is where the shape of the collection first started deciding a size here rather than merely decorating one. An index built on the entropy of the text pays the first. An index built on the runs pays the second. Quoting one number for “the cost of separators” is quoting a number about a structure that was not named.

What size does to the measures here #

The other question this cell was built for is the one about scale. A million characters of the same thing swept size on real prose and found that nearly three quarters of the fall in phrases per character was a logarithm: a shuffle of the same characters — same length, same alphabet, same zeroth-order entropy — fell by 1.70 against the collection’s 2.34, leaving 1.37 that was the arrangement.

That measurement was made on the case the structures are not for. The point of a phrase count is that it is small on a text that repeats, and prose does not repeat in the sense the parse is about.

Sweeping the copy count at a fixed base instead — so the arrangement changes and the alphabet does not — the collection’s phrase count per character falls by 4.71 and the control falls by 1.45. What the repetition is worth, after the logarithm is removed, is a factor of 3.24.

That is the number the structures in this field are actually built on, and it is more than twice the 1.37 the same two-ended measurement left on prose. The two are not in conflict; they are answers to different questions. A collection that merely has predictable statistics gives a phrase count a small correction. A collection that contains copies of itself gives it most of what it has.

What the query was supposed to get out of it #

The third expectation is the one the deferral naming this cell was mostly about: the one where a compressed index and a large document count meet. The meeting is supposed to be productive. The output-sensitive listing apparatus — the chain, the range minimum, the answer-so-far bitmap — exists because reading every occurrence costs the occurrences, and it wins exactly when a pattern occurs far more often than it occurs in documents.

The crossing that never arrives measured that on a collection of two thousand short captions and found the crossing sitting at 10.8 occurrences a document against a measured 1.04. The apparatus cost 2.64 times the index it sat on and won nothing, because a phrase in prose is rare and a collection of short prose documents holds each phrase about once.

A repetitive collection looks like the opposite case by construction. A pattern in the base occurs once in every copy, so on thirty-two copies it has thirty-two occurrences, and thirty-two is comfortably past the crossing.

It is not the opposite case. For a pattern drawn from one of the documents — which is what a reader asks for — prose reads 1.87 occurrences a document, a versioned collection reads 1.84, and copies cut across document boundaries read 1.88. All three within a tenth of each other.

The arithmetic is one line once it is seen. In a collection of versions the copies and the documents are the same partition. A phrase of the base occurs once in each copy, and each copy is one document, so the pattern has d occurrences spread over d documents and the ratio is one. Repetition of that kind cannot make a pattern dense inside a document, because it is repetition between documents and the ratio the apparatus turns on is a ratio within them.

Only the collection’s own most frequent string separates the three cells at all, at 4.78 occurrences a document against prose’s 2.38 — and the most frequent six-character string of an English-like text is a fragment of a common word rather than anything a reader would search for.

That is a retraction of the sentence that named this cell, and it is worth as much as a number would have been. It also says where to look instead: the apparatus needs a pattern that repeats inside a document, which is a third collection shape and not this one.

What each index notices #

The last thing this cell is for is the comparison the field exists to make. Three compressed indexes are built here, and they are proportional to three different things.

The entropy-bounded FM-index is flat at about 6.4 bits a character however many copies the collection holds. That is not a defect and it is not a surprise: the Burrows–Wheeler transform is a permutation of the text, so its zeroth-order entropy is the text’s, and a structure whose size is n·H₀ cannot see a copy. The entropy that cannot see a copy is the essay that measured that to fifteen decimal places, and what is still proportional to n is the one that found which parts of a run-length structure keep a term in the text’s length anyway.

The run-length index falls from 18.5 bits a character to 3.4 and the phrase index from 9.4 to 1.6. Both are made of the repetition rather than merely tolerant of it.

And at one copy — an ordinary text with no repetition in it at all — the two repetition-aware structures are the largest of the three, the run-length index by a factor of 2.9. The collection decides which index is small made that argument on one long text; it holds here with the document count folded in, and the crossing is a property of the collection rather than of the field.

The three lines cross, and where they cross is the decision. That crossing is the reason the collection decides which index is small is a sentence about a corpus rather than about a data structure, and it is the reason this cell had to be measured at several document counts rather than at one.

There is one further thing the plate says that is easy to read past. The document count and the copy count are the same axis here only because the collection is a version history. Cut the copies across the boundaries instead and the two come apart: the copy count stays where it was and the document count moves freely, and the index sizes follow the first and not the second. A structure proportional to the runs does not know how many documents there are; it knows how much of the text is a copy of earlier text. That is a nice property and it is also a warning, because a plate that sweeps documents on a versioned collection is sweeping two things at once and can be read as saying either.

What this cell turned out to be #

The two-by-two is filled, and the corner is not what its margins predicted in any of the three respects the header of this strand expected.

The separator does not break the repetition, because its cost is the entropy of the document endings and a versioned collection’s endings are nearly constant. The alphabet cost is real, is large, and is paid in a currency that has nothing to do with repetition. And the third expectation — that repetition would finally give the document-listing apparatus something to do — is the subject of one copy per document is one occurrence per document, and it comes out against the sentence that named it.

What survives is a rule about measurement rather than about text. A two-by-two whose margins are known is not a two-by-two whose cells are known, and the interaction is where the mechanism is. Every one of the three effects above turned out to be charged somewhere other than where the argument for it put it, and in each case the relocation was found by building the cell rather than by reasoning about the edges.