A boundary that costs nothing

The argument is short enough to be convincing without being checked, which is how it survived four essays.

A separator is a character that occurs in no document. A phrase of the Lempel–Ziv parse is a stretch of text that occurs earlier in the text; a run of the Burrows–Wheeler transform is a stretch of equal characters in the last column. Drop a separator into the middle of a repetitive collection and the phrase that would have run across the boundary has to stop at it, because what follows is a character no earlier position holds. So the phrase count rises. And a repetitive collection is exactly a collection whose phrases are long, so it has the most to lose.

That reasoning is why the cell holding a repetitive collection of many short documents was expected to be a bad place for a compressed index. It has one problem, which is that it is not what happens.

The experiment, and the one that would have been wrong #

The measurement has to hold the characters fixed. Build the repetitive text once — sixteen near-copies of a five-hundred-character base, eight thousand characters in total — and then cut it into one document, two, four, and so on to a hundred and twenty-eight, dropping a shared separator at each boundary. Nothing changes between points except how many separators there are.

The alternative design is the one a reader would reach for first and it does not measure the cut at all. Building a collection of d near-copies at a fixed total length makes the base shorter as d grows, so the text gets more repetitive as the sweep proceeds and the run count falls. The plate then shows the cut being not merely free but beneficial, and what it is showing is a different text at every point. The cell nobody filled states the general form: the axis has to be the thing being varied and nothing else.

The control is prose of the same length, cut identically. That convention came out of the size sweeps — the half of a fall that is the logarithm is where it was set — and its two-ended shape is what makes this essay possible. The control must move, and its movement must be compared against the raw curve rather than assumed to be small.

Here the control moves more than the thing it is a control for, which is a case that shape was not written for and handles correctly anyway.

The numbers #

Across seven doublings of the document count the repetitive collection’s runs per character go from 0.06396 to 0.06526. That is a rise of 1.02, which is to say two per cent for a hundred and twenty-seven boundaries.

Prose over the same sweep goes from 0.29965 to 0.33029 — a rise of 1.10.

In absolute terms the same hundred and twenty-seven separators add nineteen runs to the repetitive text and two hundred and ninety-three to prose. The phrase counts tell the same story with smaller numbers: 1.03 against 1.13.

There is no way to read that as the phrase-breaking argument being merely small. If the mechanism were phrase-breaking, the effect would be larger on the text with the longer phrases, because a boundary interrupts more when there is more to interrupt. The repetitive text’s phrases are several hundred characters long and prose’s are a dozen. The ordering is backwards.

There is a second reading available, and it is worth closing off because it would make the result uninteresting. Perhaps the repetitive text simply has so few runs that nineteen more is a large relative change disguised by a small absolute one — the denominator being small. It is not: five hundred and twenty-three runs going to five hundred and forty-two is a rise of 3.6% in absolute run count, against prose’s two thousand four hundred and fifty-four going to two thousand seven hundred and forty-seven, which is 11.9%. The ordering holds in both the ratio and the count.

Nor is it an artefact of one alphabet. On four symbols the documents can only end with one of four characters, so the ceiling on the endings is low for both texts and the gap should narrow. It does narrow, and it does not reverse — which is the second plate above, and which is the first evidence that the endings are what the mechanism is about.

Where the reasoning goes wrong #

The phrase-breaking argument is not false. It is about the wrong structure.

A phrase of the parse genuinely does stop at a separator, and the parse genuinely does gain a phrase per boundary — that is the 1.03 above, and it is a hundred and twenty-seven boundaries producing about the same number of extra phrases out of nine hundred. On a text with three hundred phrases that would be a large effect. On a text with nine hundred it is three per cent, which is what was measured.

What the argument does not touch is the run count, and the run count is where every quotable size in the run-length family lives. A run is a stretch of equal characters in the last column of the sorted rotations, and the separator’s contribution there has nothing to do with what it interrupts in the text. It has to do with where its rows sort.

The separator sorts before every ordinary character, so its d rows sit at the top of the suffix array, together. The transform character in a row is the character preceding that row’s suffix — so those d rows hold the last characters of the d documents, in a block. A block of the transform costs one run per change inside it.

So the price of a boundary is the number of distinct characters the documents end with. The price of a boundary is what precedes it is the essay that measures that directly rather than inferring it from the totals, and the numbers are stark: at a hundred and twenty-eight documents the repetitive collection ends with six distinct characters and prose with eighteen, and the runs follow at nineteen against two hundred and ninety-three.

Why the versioned collection ends predictably #

There is one more step, and it is the step that makes this a fact about a construction rather than about repetition.

A version history cut into documents at the boundaries between copies ends every document at the same offset of a near-identical text. Documents one and two and three all end with whatever character the base ends with, modulo the divergence that makes the copies near rather than exact. Six distinct endings out of a hundred and twenty-seven is what a one per cent divergence produces.

Cut the same characters at arbitrary offsets instead — the construction the cell nobody filled calls the cut-up text — and the endings are drawn from wherever the cuts landed, which is to say from the base’s own character distribution. The cost then looks like prose’s, because for this purpose it is prose’s.

That is the sharp version of the result and it is not about repetition at all. A collection pays for its boundaries in runs according to how predictable its document endings are. A repetitive collection usually has predictable endings, so it usually pays nothing; but the predictability is what is being charged for, and a repetitive collection with unpredictable endings pays in full.

The measurement that makes this concrete is not a total at all. It is the ending characters themselves, read off the documents and counted, beside the runs the cut added. Two quantities that have no arithmetic relationship in the phrase-breaking story turn out to move together across four document counts, and that is what a mechanism looks like when it has been found rather than assumed.

At sixteen documents the repetitive collection ends with one distinct character across fifteen boundaries, and the cut removes a run. At sixty-four it ends with three and adds nine. At a hundred and twenty-eight it ends with six and adds nineteen. Prose ends with eight, seventeen and eighteen at the same three points and adds fifty-two, a hundred and sixty-two and two hundred and ninety-three. The repetitive collection is paying 0.15 runs a separator and prose is paying 2.31.

That prose saturates — eighteen distinct endings at a hundred and twenty-eight documents, out of a twenty-one symbol alphabet — while its added runs keep climbing is the one part of the picture the simple story does not cover. The block is not merely as many runs as it has distinct characters; it is as many runs as it has changes, and a block of a hundred and twenty-seven characters drawn from eighteen symbols in an essentially arbitrary order has close to a hundred and twenty-seven changes in it. Distinctness is the ceiling on the cost and arrangement is the cost.

What is actually charged #

None of this makes a separator free. It relocates the charge.

One separator or one for each priced the joins on prose, and the arithmetic is unchanged here: one shared separator raises the alphabet by one symbol and d distinct separators raise it by d. When σ + d crosses a power of two, every character of every document needs another bit.

On thirty-two near-copies, distinct separators take the alphabet from twenty-one symbols to fifty-two — across the thirty-two boundary — and cost 20.2% of the packed text. The same change costs 2.9% in runs. One shared separator costs 0.2% packed and less than nothing in runs: the run count falls by three, because the block the separators introduce is more uniform than the characters whose rows they displaced.

A structure whose size is the text’s entropy pays the first column. A structure whose size is the run count pays the second. There is no single number for “what separators cost”, and quoting one is quoting a number about a structure nobody named.

There is one more consequence, and it points at a design choice rather than a measurement. A collection that must not report matches spanning two documents has three options: give up and filter the results, spend a shared separator and accept that a pattern containing it can never match anything, or spend distinct separators. The first is a query-time cost proportional to the occurrences; the second is nearly free; the third is a fifth of the packed text.

Almost every account of this treats the third as the careful choice and the second as the cheap one. On the run-based structures the two are within three per cent of each other, so on a repetitive collection the careful choice is nearly free as well — and it is the alphabet-based structures where the gap opens. That is not a conclusion anyone can reach from the text; it is a conclusion about which structure the collection is going into, which is the collection decides which index is small applied to a decision about the corpus rather than about the index.

Pushed to a hundred and twenty-eight short documents the packed cost of distinct separators grows again, because the alphabet crosses another power of two, and the run cost stays where it was. The two currencies do not converge as the collection gets more fragmented; they diverge.

What the shared separator actually does to the transform #

It is worth looking once at why one shared separator can make a repetitive collection’s run count fall, because a change that is supposed to cost something and instead pays a small dividend is usually a sign that the model is missing a term.

Without a separator, the rows of the suffix array that begin at document starts are scattered: each one sorts wherever the text that follows it sorts, which on near-identical copies means the d copies of a given suffix land adjacent to each other but unrelated suffixes land between the groups. The transform characters in those rows are whatever preceded each start, which on a concatenation is the previous document’s last character — the same set of characters as before, but distributed through the array rather than gathered.

Add the separator and two things happen at once. The d rows beginning with it are gathered into one block at the top, so their transform characters — the document endings — are contiguous, and a block of nearly identical characters is one run rather than d scattered contributions to d different runs. And every ordinary row that used to have a document ending as its transform character now has the separator instead, which is also a constant.

So a shared separator on a versioned collection replaces a scattered set of characters with two constants. On prose the same substitution replaces a scattered set with one constant and one block of eighteen-ish distinct characters, and the block costs more than the scattering saved. The sign of the effect is decided by which of those two the collection is.

That is a satisfying account and it is not a prediction: it was written after the plate showed the run count falling, and the honest label for it is an explanation of a measurement rather than a model that anticipated one. What makes it more than a story is that it says which quantity to look at — the ending characters — and that quantity turns out to order the two collections correctly at every document count tested.

The general shape of the mistake #

This is the third time in this field that a cost turned out to be charged somewhere other than where the argument for it put it, and the three have the same form.

What a ceiling costs in phrases predicted that capping a parse’s copy depth would cost phrases in proportion to the depth distribution, and found the cost concentrated in runs of punctuation nobody had modelled. The ratio that was an implementation found two thirds of a published ratio to be an accounting artefact. And here an argument about what a separator interrupts turns out to be an argument about a structure the separator does not appear in.

In each case the reasoning was sound about a mechanism that exists and small. What made it wrong was that a different mechanism, in a different part of the structure, was larger — and nothing in the argument pointed at that part, because the argument was constructed from the definition rather than from the object.

There is a defence of the original reasoning that is worth making, because it is the reason the argument was written down at all. Nothing in it is wrong about the parse. If this collection had built only a phrase index and never a run-length one, the sentence “a separator breaks a phrase” would have been the right first-order account, the correction would have been three per cent, and no essay would have been needed. What produced the error was carrying the sentence across to a structure whose unit of cost is different — and the two structures are usually described in the same paragraph, as the two routes to a compressed index, which is exactly the circumstance in which a claim about one gets read as a claim about both.

The practical consequence is small and worth saying plainly. A collection of versioned documents can be given a shared separator for almost nothing, in either currency, and the run-based structures will read it almost exactly as they read the concatenation. Distinct separators are affordable in runs and expensive in bits, and the crossing between those two is a property of how many documents there are relative to the alphabet. Neither of those is the sentence the phrase-breaking argument would have produced, and both of them are measurable in a few seconds on the collection in hand.