The price of a boundary is what precedes it

The previous result is a fact without a mechanism: cutting a repetitive text into a hundred and twenty-eight documents raises its run count by two per cent and cutting prose raises it by ten. That ordering is backwards from every account of what a separator does, and an ordering without a mechanism is a coincidence waiting to be contradicted by the next corpus.

The mechanism is one sentence and it is checkable directly, which is what this essay is.

A separator sorts before every ordinary character. In the sorted rotations that means its rows are at the very top of the array, together. The transform character in a row is the character preceding that row’s suffix — so those rows hold the last characters of the documents, gathered into one contiguous 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, in the order the separators sort. Not the document count, not the collection’s length, and not whether the collection repeats.

Reading the two quantities off directly #

The claim is testable without any inference from totals. Cut the text, read the last character of each document, count how many distinct ones there are, and count the runs the cut added. If the mechanism is right the two move together; if it is a story, they will not.

At sixteen documents a version history cut at the copy boundaries ends with one distinct character across all fifteen interior boundaries, and the cut removes a run — the count goes from five hundred and twenty-three to five hundred and twenty-two. At sixty-four it ends with three and adds nine. At a hundred and twenty-eight it ends with six and adds nineteen.

Prose over the same three points ends with eight, seventeen and eighteen distinct characters and adds fifty-two, a hundred and sixty-two and two hundred and ninety-three runs.

That is 0.15 runs a separator against 2.31, and the two series are ordered the same way at every point. The second column is the one the previous essay measured as a total; the first column is a property of the text that can be computed without building a transform at all.

There is one detail in that first row worth pausing on, because a negative cost is the kind of number that usually means an error somewhere. Fifteen boundaries dropped into a text and the run count goes down by one. Nothing about the text changed except that fifteen characters were inserted, and inserting characters into a text can only add rows to its transform. So a run count that falls is a claim that the arrangement improved by more than the fifteen new rows cost, and that claim needs its own account rather than a shrug. It gets one further down; for now it is enough that the sign is not a mistake and that it is reproducible across corpora.

The other thing the two columns settle is that the effect is not the alphabet. Adding a separator adds one symbol, and the run count of a text over σ symbols has no term in σ — a run is a stretch of equal characters and there is no reason for a larger alphabet to lengthen or shorten them on its own. Both collections gain exactly one symbol in this sweep, and their run costs differ by a factor of fifteen — a separation the cell nobody filled draws in both currencies at once, so whatever is happening is not happening in the alphabet. That is the first of two currencies this strand keeps separate, and the separation is the reason the two numbers can be so far apart.

Distinctness is the ceiling and arrangement is the cost #

Prose saturates and its cost does not, and that gap is the part of the story that needs a second sentence.

Eighteen distinct endings out of a twenty-one symbol alphabet is nearly all of them; there is nowhere further for that number to go. Yet the added runs keep climbing from a hundred and sixty-two to two hundred and ninety-three between sixty-four and a hundred and twenty-eight documents. So the cost is not the count of distinct characters.

It is the count of changes. A block of a hundred and twenty-seven characters drawn from eighteen symbols in an arbitrary order has close to a hundred and twenty-seven changes in it, because two adjacent entries agreeing is a one-in-eighteen event. Distinctness bounds the cost from below — a block of one character is one run whatever its length — and arrangement decides where between that bound and the block’s length the answer falls.

The two-ended form of the claim is therefore: a collection whose documents end with one character pays one run for all of its boundaries, and a collection whose endings are drawn independently from a σ-symbol distribution pays about (1 − 1/σ) of a run per boundary. Everything real sits between, and where it sits is a property of how the documents were cut rather than of what is in them.

On a four-symbol alphabet that upper bound is 0.75 runs a boundary rather than 0.95, and the measured gap between the two collections narrows accordingly — which is the second plate, and which is a prediction the mechanism makes and the phrase-breaking account does not.

It also closes. At a hundred and twenty-eight documents over four symbols both collections end with all four characters, so distinctness separates them by nothing — and the runs still separate them by a factor of twenty-six, six added against a hundred and fifty-six. That is the ceiling being reached on one quantity while the other keeps going, and it is why the mechanism’s check is on the endings at the start of the sweep and on the runs at every point.

It is worth writing the bound out, because it is a rare case in this field where a cost has a closed form that is exactly right rather than asymptotically right. Let the d − 1 interior boundaries have ending characters drawn independently from a distribution p. The block of endings has d − 1 entries; two adjacent entries agree with probability Σ pᵢ², so the expected number of changes is (d − 2)(1 − Σ pᵢ²), and the runs the block contributes are one more than that. On a uniform σ-symbol distribution Σ pᵢ² is 1/σ and the expected cost per boundary is 1 − 1/σ.

Substituting σ = 21 gives 0.952 runs a boundary and the measurement on prose gives 2.31, which is not agreement and is not supposed to be. The block is not the only place the separators appear: every row whose transform character was a document ending now carries the separator instead, and the rows that used to hold the endings have moved. So the arithmetic above is a lower bound on the block’s own contribution rather than a prediction of the total. What it is right about is the shape — the cost is (1 − collision probability) per boundary, times a constant the rest of the array supplies — and that shape is what orders the two collections.

A collection whose endings collide with probability near one pays near nothing. A collection whose endings collide with probability 1/σ pays a constant per boundary. The measured 0.15 and 2.31 sit in that ratio to within the constant, which is as much as an argument at this level of detail should be asked for.

Why a version history ends predictably #

The reason a versioned collection has almost no distinct endings is not that it repeats. It is that it was cut at the same offset of near-identical texts.

Documents one and two and three of a version history are copies of one base with a small divergence applied, so all of them end with whatever character the base ends with, unless the divergence happened to land on that position. At a one per cent divergence and a hundred and twenty-seven boundaries the expected number of documents whose final character was touched is a little over one, and a handful of secondary effects — a touched character being changed to something already present — bring the observed count to six.

Cut the same characters at arbitrary offsets instead, so a document may hold the tail of one copy and the head of the next, and the endings are drawn from the base’s own character distribution. The cost then looks like prose’s, because for this purpose it is prose’s: the endings are a sample of the text.

This is where the result stops being about repetition. A repetitive collection with unpredictable endings pays in full. The predictability is what is being charged for, and repetition is merely the most common reason a real collection has it.

Two examples make the point concrete without any new measurement. A directory of software releases cut at file boundaries has predictable endings, because most source files end with a newline and a closing brace. A collection of log lines cut at line boundaries has extremely predictable endings, because a log line ends with whatever the last field is. Neither of those collections needs to be repetitive at all for the boundary cost to vanish, and the second is not.

The same reasoning explains something that looked like an inconsistency in the earlier size sweeps. Documents that are not the same length found that a collection’s document lengths change what a listing apparatus costs; this says the collection’s document endings change what its index costs, and the two are independent properties of the same cut. A collection can have wildly uneven lengths and perfectly uniform endings — fixed-format records of varying content — or the reverse. Neither number predicts the other, and a plate that sweeps document count is moving both unless it says otherwise.

That independence is also why the version-history construction and the cut-up construction have to be carried side by side through this whole strand rather than one being chosen. They agree about every character in the collection. They disagree about the endings, and therefore about the run count, and therefore about the size of two of the three compressed indexes built here.

The shared separator can pay a dividend #

At sixteen documents the cut removes a run. A change that is supposed to cost something and instead pays back is worth understanding, because it is usually a sign of a missing term.

Without a separator, the rows beginning at document starts are scattered through the array — each sorts where the text following it sorts. Their transform characters are the previous documents’ endings, so the same set of characters is present, distributed rather than gathered. Each one is a potential run boundary wherever it lands.

Add the separator and two substitutions happen at once. The rows beginning with the separator are gathered into one block at the top, so the endings become contiguous — and on a versioned collection contiguous and identical, which is one run rather than d scattered contributions to d different runs elsewhere. And every row that used to carry a document ending as its transform character now carries the separator, which is a second constant.

So a shared separator replaces a scattered set of characters with two constants. On a versioned collection that is a small net saving. On prose it replaces a scattered set with one constant and a block of eighteen-ish arbitrary characters, and the block costs more than the scattering saved.

The other currency, which this does not touch #

Everything above is about runs, and the run count is what the run-length index and the r-index are proportional to. It says nothing about the alphabet.

One separator or one for each established the alphabet arithmetic and it is unchanged by any of this: one shared separator adds one symbol, d distinct separators add d, and when σ + d crosses a power of two every character of every document needs another bit. On thirty-two near-copies over twenty-one symbols, distinct separators take the alphabet to fifty-two — across the thirty-two boundary — and cost 20.2% of the packed text against 2.9% in runs.

The two currencies do not merely disagree; they disagree by a factor of seven on the same change, and the disagreement grows as the collection gets more fragmented rather than shrinking. That is the practical content of this essay: the question “what do document boundaries cost?” has no answer until the structure is named, and the two structures a compressed index is usually built from give answers an order of magnitude apart.

There is a limit to how far that dividend goes, and it is worth marking. The saving is bounded by what the scattered endings were costing before the separator arrived, which is at most one run per document and in practice much less, because a scattered character only costs a run when both its neighbours differ from it. So the dividend is a few runs on a collection of a few hundred, and it is not a mechanism anyone should be building on. What it is good for is falsifying the simple story: a cost that can come out negative is not a cost of the kind “a separator breaks something”.

What the transform was already saying #

There is a version of this result that was sitting in this collection already, unrecognised.

The transform that emits nothing established that the Burrows–Wheeler transform is a permutation, so it changes no character’s frequency and therefore changes a zeroth-order entropy by nothing at all. What it changes is arrangement: it gathers characters that share a right context, which is why a run-length code on the transform is worth something and a run-length code on the text is not. The index that stores the runs is where that observation became a structure, and a floor under a run count is where the run count stopped being a free parameter.

The separator result is the same statement read the other way. The transform gathers by right context; a separator gives d positions the same right context — the separator itself — so it gathers their left characters into one block. Whether that block is cheap is a question about those characters, and the transform has no opinion about it.

Stated that way the mechanism is not a discovery about separators at all. It is the transform’s defining property applied to a case where the right context was chosen by the person building the collection rather than found in the text. What is still proportional to n makes a related move: the interesting question about a structure built on the transform is usually which of its terms follows the arrangement and which follows the alphabet, and separators turn out to be a term of the first kind.

One further connection is worth making explicit, because it is the reason this result generalises past separators. The occurrences a join invents showed that running documents together creates strings the collection contains and no document does, and that a separator removes them. That is a correctness argument and it is the usual reason given for the separator. This essay is the cost argument, and the two land in the same place for an unexpected reason: on the collections where the invented strings are most damaging — many near-identical documents, where a window spanning a join is almost always new — the separator is also nearly free. The case where it is expensive is prose, and prose is the case where the invented strings are least likely to be matched.

That is a pleasant coincidence rather than a theorem, and it does not hold at every alphabet size. But it means the careful choice and the cheap choice usually agree, which is not something a reader could have known from either argument alone.

Where this leaves a collection being built #

The rule that comes out is short and can be applied before anything is measured.

Cut a collection at boundaries that end predictably — file boundaries, line boundaries, record boundaries in a fixed format — and the run-based structures will read the collection almost exactly as they read the concatenation. Cut it at arbitrary offsets and expect to pay about a run per boundary, which on a collection of many short documents is a term proportional to the document count in a structure whose whole claim is that it has no such term.

That second case is not hypothetical. It is what happens to a repetitive corpus taken off a shelf and split into fixed-size blocks for parallel indexing, which is a common enough thing to do that the cost deserves to be quoted somewhere. The collection decides which index is small is the sentence that decides whether the cost matters at all, since a collection heading for an entropy-bounded index does not pay it. At a hundred and twenty-eight blocks over eight thousand characters it is about three per cent of the run count; at the block sizes a real system uses it is smaller, and it is never zero, and it is not the cost the phrase-breaking account would have led anyone to look for.