The index that stores the runs

The same collection, indexed three ways, as it grows from one copy of a text to thirty-two.

At a single copy the run-length index is 1.11× the compressed one — the larger structure. At thirty-two it is 0.39×, and at every point in between the two are moving in different directions.

That ordering reversal is what makes this a claim about repetition rather than a claim that one structure is smaller. Run the same experiment on thirty-two unrelated texts of the same total length and the run-length index is 2.16× the compressed one at every size, never crossing.

What is stored #

The entropy-bounded index stores the transform: $n$ symbols in a wavelet tree of bit vectors, with rank directories over them. Its size follows $H_k$ because the wavelet tree’s does.

This one stores the transform’s runs, and nothing else about it. On 16,384 characters with 224 runs:

Run starts is a bit vector over the $n$ positions with a one at the start of each run. Storing it plainly would cost $n$ bits and defeat the whole exercise, so it is stored the way Elias and Fano account for a sparse set: split each of the $r$ positions into a high part and a low part of $\lceil\log_2(n/r)\rceil$ bits, write the low parts plainly and the high parts as a unary-coded sequence of exactly $2r$ bits. The total is

$$r\left\lceil \log_2 \frac{n}{r} \right\rceil + 2r$$

which is 2,016 bits for 224 runs in 16,384 positions — an eighth of a bit per position.

Run heads is the string of $r$ run characters, in a wavelet tree. It is the part that scales with the alphabet, and it is the part the floor essay shows cannot be dropped.

Run lengths per symbol is, for each character, a sparse vector over that character’s own occurrences with a one at each of its runs’ starts. It is what turns “how many $c$-runs precede this one” into “how many copies of $c$ they held”.

A rank is three counted operations and an addition #

Everything an FM-index does is built on one question: how many copies of $c$ there are in the transform before position $i$. The entropy-bounded index answers it by walking a wavelet tree, one bit-vector rank per level of the character’s code. This one answers it with the three structures above.

Find the run containing position $i - 1$ — one rank on the run-start vector, a binary search over $r$ positions. Ask how many runs of $c$ precede it — one rank on the wavelet tree of heads. Ask how many copies of $c$ those runs held — one select on that character’s length vector. Add the part of the current run that is behind $i$, if the current run is a run of $c$.

$$\text{rank}_c(i) \;=\; \text{cum}_c\big(\text{rank}_c(H,\, j)\big) \;+\; [\,H_j = c\,]\cdot(i - \text{start}_j)$$

Three operations rather than one, each on a structure sized by $r$ rather than by $n$, and each counted separately on every plate — because a rank on a bit vector, a rank on a symbol and a select are three different acts and a number summing them would belong to no level of the structure.

The two structures cross, and the crossing is repetition #

The right-hand column is the honest way to read it. Two of the three structures are flat per character and one falls, and a structure that gets cheaper per character as its input grows is a structure measuring something other than the input’s length.

At a single copy the run-length index loses, and it loses for a reason worth stating rather than apologising for: 512 characters of English produce 222 runs, so $r/n$ is 0.43 and the transform is barely run-structured at all. Storing 222 runs of average length 2.3 costs more than storing 512 symbols compressed. The structure is not smaller; it is differently proportioned, and which proportion wins is a property of the collection.

And on unrelated texts it never wins #

The negative half, which is what makes the positive half a claim about repetition:

$r$ rises from 222 to 15,334 — 0.94 runs per character, close to the maximum — and the structure that was tracking it rises with it. A test run only on repetitive collections would have been passed by an implementation whose run detection had stopped working, so both directions are asserted on every build.

What a run costs to store, against what a symbol costs #

The arithmetic that decides the crossing is worth doing directly, because it says where the crossing is without running anything.

A symbol in the entropy-bounded structure costs about $H_0$ bits of wavelet-tree payload plus its share of the rank directories — on this collection 1.87 bits, measured. So that index is about $1.87n$.

A run in this structure costs three things: its start, at $\lceil\log_2(n/r)\rceil + 2$ bits; its head, at about $H_0$ of the head string; and its length, at another $\lceil\log_2(n_c/r_c)\rceil + 2$. At thirty-two copies that is $5{,}989/224 = 26.7$ bits a run.

$$1.87\,n \quad\text{against}\quad 26.7\,r$$

so the run-length representation wins when $r/n < 0.070$, which is one run in fourteen characters. At one copy $r/n$ is 0.43 and it loses; at two copies it is 0.22 and it should still lose — and it does not, because the compressed structure is not at its own limit either and both constants move with the collection.

Which is the useful form of the statement, and it is not asymptotic. Whether an index built on runs beats one built on entropy is a comparison between two constants times two measurable quantities, both of which can be computed from the collection before either structure is built. Nothing about it requires the collection to be large.

What it does not buy #

Not a faster query. A rank here is three operations against the wavelet tree’s four or five; the difference is a constant and it goes the wrong way as the alphabet widens, because the run heads are themselves a wavelet tree. Nothing above is a claim about speed.

Not the r-index. The sampling here is at regular intervals in the suffix array, exactly as the entropy-bounded index samples, so that the comparison is between two representations of the transform rather than between two sampling policies. The structure known as the r-index samples at run boundaries instead, which removes the last $n$-sized term — and that term is 50% of this structure at thirty-two copies and is the subject of the next essay.

And not a smaller structure than the text. At one copy this index is 3,798 bits against a packed text of 2,560 — 1.48× the thing it indexes. The claim that a self-index can be under the text it indexes belongs to the entropy-bounded one on ordinary text, and to this one only once there is repetition for it to find.

Why the runs are in the transform and not in the text #

The transform of a text has long runs where the text does not, and it is worth being exact about why, because the mechanism decides which collections this works on.

The transform sorts every rotation and reports the character preceding each. So two positions are adjacent in it when the text that follows them is similar. A passage occurring twice puts every one of its positions beside its twin, and the character before each is the same character — so the twin pair is a run of two, and a passage occurring thirty-two times gives runs of thirty-two.

Which is why the collection has to repeat rather than merely be predictable. A Markov-like text is highly compressible by any entropy and has ordinary runs, because predictability at three symbols does not make any two positions share a long context. The transform’s runs need long shared contexts, and only literal repetition produces them.

Everything above is checked against the structure it replaces #

Two structures answering the same questions is a fact that has to be established rather than assumed, and the ways it can quietly fail are specific.

The answers. Every pattern of one, three, six and eleven characters taken at intervals across a two-thousand-character text is counted and located through the run-length index, and both the count and the sorted list of positions are required to equal what an exhaustive scan of the text finds. Forty-four patterns, on every build.

The text. The structure is required to hand back the text it was given, character for character, from its own bits and a walk from the sentinel — which is the check that makes “self-index” a claim rather than a category. An index that had lost a run, or mis-ordered its heads, would still count correctly on most patterns and would not survive this.

The samples. The rejection carried beside it removes the sampled rows and requires locate to raise rather than to return something. A walk that never reaches a sample has no answer, and the failure mode of not saying so is a query that loops.

And the run counter itself. A counter that misses a run of a single character is the natural off-by-one here, and it makes every structure smaller and every claim in this essay stronger. The rejection feeds a faulty counter a transform whose runs it undercounts — eight runs reported as three — and requires the difference to be caught.

The size is its parts, and the parts are checked #

Every size on every plate in this family comes from a bits() that names its components and is required to sum to the total it reports, on every call. That rule was set when this field opened and it matters more here than it did then, because the interesting fact about this structure is not its total.

The total at thirty-two copies is 11,900 bits and it grew 2.7× from its value at two copies, which sounds like a structure that is not really independent of $n$. Opened up, 5,989 of those bits are proportional to $r$ and grew 1.45×, and 5,911 are the sampling and grew 18.3×.

A total cannot show that one of its terms is the majority of it. This field has hit that before — an exponential histogram whose timestamps outweighed its payload, reported inside a correct total — and the repair is the same: the parts are named, the names are stable across the family, and the sum is checked rather than trusted.

The statistic that decides is a by-product of work both structures need #

The crossing condition — build on runs when $r/n$ is below about one in fourteen — is only useful if $r$ can be had before committing to a structure. At first reading it cannot: counting the runs means having the transform, and computing the transform is the expensive part of building either index.

That objection dissolves on inspection, and the way it dissolves is worth stating because it makes the rule practical rather than theoretical.

Both structures are built from the same transform. The entropy-bounded index puts it in a wavelet tree; this one cuts it into runs. Neither can begin without it, and neither needs anything the other does not. So the transform is not a cost of the decision — it is a cost of the outcome, paid whichever way the decision goes.

Once it exists, counting the runs is a single linear scan comparing each character with its predecessor. On sixteen thousand characters that is sixteen thousand comparisons against a construction that sorted every rotation. The decision costs a scan and is taken after the only expensive step, which means it never has to be guessed.

That is an unusually comfortable position and it is worth noticing how rarely a choice of structure is in it. Most such decisions are taken from a property nobody has measured — the eventual cardinality, the skew of the key distribution, how many occurrences a typical query will have — and have to be guessed at design time from something a person believes about the data. Here the deciding statistic is exact, cheap, and available at precisely the moment it is needed.

There is one caveat and it is about deployment rather than arithmetic. A collection that grows changes $r/n$ over time, and it changes it in the direction that favours the run-length structure whenever the new material resembles the old. So a system that measured once, chose the entropy-bounded index and never looked again is on the wrong side of a crossing it has since passed. The rule is cheap enough to re-run whenever the collection is rebuilt, which is the only sensible time to change structures anyway.

The marginal cost of a document is not a constant #

The tables above grow a collection by adding copies, and reading them as growth curves conceals a fact that matters more than either curve: what a document costs this structure depends entirely on what is already in it.

Take the two extremes from the measurements already made. Growing from one copy to thirty-two adds thirty-one documents and takes $r$ from 222 to 224 — about 0.065 runs per document. Growing a collection of unrelated texts over the same range takes $r$ from 222 to 15,334, which is about 487 runs per document. The same operation, described the same way in any interface, differing in cost by a factor of seven thousand.

Two consequences follow and both are the kind of thing that surprises a system in production.

A per-document size budget is meaningless. A structure whose size is proportional to the length can be budgeted by multiplying: a thousand documents of a thousand characters is a million characters, and the index is some rate times that. This structure has no such rate. A thousand near-identical documents cost barely more than one, and a thousand unrelated ones cost more than the entropy-bounded index would have. Any capacity plan that treats the index as a function of the total length is planning for a collection it has not looked at.

And the marginal cost is a property of the set rather than of the order. Nothing above depends on which document arrived first, because the transform sorts every rotation of the whole collection and has no notion of arrival. That is worth setting against the parse-based measures, where the order genuinely does matter — the first document is parsed against nothing and pays full price. Here the same set of documents in any order gives the same runs, so a system cannot improve its index by sorting its inputs and cannot damage it by shuffling them.

The practical form of both points is a single instruction: measure $r$ on the collection in hand, and re-measure it when the collection changes character. A number that varies by three orders of magnitude across collections of identical size is not a number to inherit from a benchmark, and the sections above have now given two independent reasons why it is cheap to take.

What is not measured here #

Locate and extract are not compared. The samples in this structure are regular and its locate walk is the same walk the entropy-bounded index performs, so the query costs are the same by construction and the comparison would be uninformative. The interesting version of that comparison needs run-boundary sampling and does not exist here.

The alphabet’s effect on the run heads. The heads are $r$ symbols in a wavelet tree, so the head cost scales as $r \cdot H_0(\text{heads})$; how that behaves on a large alphabet is unmeasured, and it is the part of the structure most likely to misbehave there.

Construction. Every structure here is built from a transform computed by sorting rotations, which is quadratic and is fine at the sizes a figure draws and is not how anything real is built. Nothing above is a statement about build time — and build time is where the practical difficulty of this family actually lives, because computing the transform of a collection large enough to be worth this structure is the step that does not fit in memory.

And the collection here is a concatenation. Real repetitive collections are sets of documents with boundaries, and the boundaries matter: a pattern spanning two documents is an occurrence of nothing, so a real index either separates them with distinct sentinels — which costs runs — or filters afterwards. Nothing above pays either price.