The index that does not notice

Three structures in this field answer the same three questions — how many occurrences, where are they, and what does the text say — and their sizes are proportional to three different quantities.

The FM-index stores the Burrows–Wheeler transform in a wavelet tree of bit vectors, so its payload is n·H₀ of the transform. The run-length index stores the transform as heads and lengths, so its payload follows r. The phrase index stores a Lempel–Ziv parse and three orderings of its boundaries, so its payload follows z.

Those are three different functions of one text, and on most texts they do not order the same way. This plate is what happens when the text is held fixed and the arrangement is swept.

The flat line #

The FM-index reads 6.43 bits a character at one copy and 6.38 at sixty-four. That is a change of eight tenths of a per cent across a collection that has become sixty-four times more repetitive.

The reason is the entropy that cannot see a copy, and it is not a limitation of an implementation. The Burrows–Wheeler transform is a permutation of the text. A permutation changes no character’s frequency, so it changes a zeroth-order entropy by nothing at all — measured there to fifteen decimal places. A wavelet tree of plain bit vectors, shaped by the character frequencies, costs n·H₀ of the sequence it holds. So the FM-index costs n·H₀ of the text, and duplicating a text leaves H₀ exactly where it was.

The small drift that does appear is the directories and the C table, which are o(n) terms whose constants shift slightly as σ changes. Nothing in the structure is proportional to anything the copying moved.

This is worth stating plainly because the transform is routinely credited with the compression in this family. It is credited with the wrong compression. What it does is gather characters that share a right context, which turns a text’s higher-order structure into runs — and a plain bit vector charges one bit per bit whatever is in it, so those runs cost exactly what the scattered version cost. The transform’s gathering is worth something only to a structure that charges less for a run than for a change, which is the next two lines.

There is a version of this structure that does benefit, and naming it sharpens what the flat line is measuring. Replace the plain bit vectors with block-classed ones — the representation that stores each block of b bits as its class and an offset within that class — and a level that is nearly all zeros becomes nearly free. The transform’s gathering then does pay, because a gathered level has long runs and a run’s offset costs nothing.

That structure is in this collection and it is measured: rank is the only thing it does is where the block representation was priced, and it reaches the text’s higher-order entropy rather than its zeroth. What it does not reach is repetition. A collection of sixty-four copies has the same conditional entropies as one copy — the copies do not make the next character more predictable given the previous few — so the compressed-block index falls a little and then stops, and its line on this plate would sit between the flat one and the two that fall, much closer to the flat one.

Three levels of a hierarchy, then: zeroth-order entropy, higher-order entropy, and repetition. The first two are properties of a text’s local statistics and the third is not, and no amount of the first two implies the third.

The two that fall #

The run-length index goes from 18.5 bits a character to 3.4 — a factor of 5.5. The phrase index goes from 9.4 to 1.6, a factor of 5.7.

Both are following the measures what repetition is worth once the logarithm is gone sweeps: r/n falls by 3.4 and z/n by 4.7 over a comparable sweep, and the index sizes fall slightly further because the width of each stored item also shrinks as the counts do — a run head’s index needs ⌈log₂ r⌉ bits and r is falling.

What the two lines do not do is cross each other. The phrase index is smaller than the run-length index at every point of this sweep, by a factor between 2.0 and 2.2, and the gap is remarkably stable. That is a fact about this collection rather than about the two families: a version history with a small divergence produces long phrases and long runs in roughly fixed proportion, so the two measures move together.

The stability of that ratio is worth one more sentence, because it is the kind of thing that looks like a law and is not. r and z are related — a text with few phrases has few runs — but the relationship is loose, and there are texts where they diverge sharply. A periodic text has a tiny run count and a phrase count that grows with the number of periods; a text built from a Fibonacci word has both small but in a different ratio. The measure that cannot see the alphabet is where the parse’s own blind spots were measured, and it is the reason a plate showing the two moving together should be read as a fact about this collection.

The crossing that decides #

The important feature of the plate is at the left-hand edge, and it is the one that inverts the usual presentation.

At one copy — an ordinary text with no duplication in it — the run-length index is 18.5 bits a character against the FM-index’s 6.4. It is 2.9 times larger than the structure it is offered as an improvement on. The phrase index is 9.4, which is 1.5 times larger.

Both of the repetition-aware structures are the wrong choice on a text that does not repeat, and they are the wrong choice by a wide margin rather than a marginal one. The collection decides which index is small made that argument on one long text; it is unchanged by folding in the document count, and it is worth restating because the literature’s framing does not survive it.

The framing is that these are compressed indexes and the FM-index is the entropy-bounded one, as though the first were a strictly stronger claim. It is not a stronger claim; it is a different one. A structure proportional to r has no bound in terms of H₀ at all, and on a high-entropy text with no repetition r approaches n(1 − 1/σ), which is worse than n bits before the directories are counted.

The asymmetry is not only about size. The FM-index’s query cost is a constant number of ranks per character of the pattern, whatever the text is; the phrase index’s is a chain walk whose length is a property of the parse and is bounded by nothing. The character that costs a chain is that measurement, and it means the phrase index’s advantage in bits is paid for in a query-time distribution with a long tail. Choosing between them on size alone is choosing on one of two axes.

Where the crossings actually are #

Reading the crossings off this sweep: the phrase index crosses the FM-index between one and four copies, and the run-length index crosses it between four and sixteen. Interpolating on the log scale puts the first near two copies and the second near seven.

Those are small numbers, and they are the reason these structures exist. A collection that holds a document and one revision of it is already past the first crossing. A collection with eight near-identical members is past both. Almost every archive of anything is past both, which is why the structures are worth building — and almost every single document is past neither, which is why they are not universal.

A collection sitting near a crossing is the awkward case and it is worth saying what to do there. Near two copies the phrase index and the FM-index are within a few per cent, and the choice should be made on the query profile rather than on the size: the FM-index answers a count in m ranks and the phrase index answers it by a boundary search with a chain walk behind it. Near seven copies the run-length index joins them, and the same reasoning applies with the additional consideration that its sampling term is the part that has not shrunk.

What the document count does to all three #

There is a second axis in this cell and it is nearly invisible on the plate, which is itself the finding.

In a version history the document count and the copy count are the same number, so the sweep above moves both. Separate them — cut the same copies into a different number of documents — and the index sizes follow the copies and not the documents. Cutting sixteen copies into a hundred and twenty-eight documents raises the run count by two per cent and the phrase count by three, which is a movement of a few tenths of a bit a character in structures spanning fifteen.

A boundary that costs nothing is where that measurement is made and the price of a boundary is what precedes it is why. The consequence for this plate is a warning about reading it: a sweep of the document count on a versioned collection is sweeping the copy count, and a reader who takes the x-axis at face value will conclude that fragmenting a collection makes its index smaller. It does the opposite, slightly, and the large effect is entirely the copies.

The parts, and which one is the size #

It is worth opening the two falling structures once, because their sizes are dominated by different things and the domination changes across the sweep.

The phrase index at eight copies holds a length, a source and a literal per phrase — that is z(2⌈log₂ n⌉ + ⌈log₂ σ⌉) — and three permutations of its z boundaries, at z⌈log₂ z⌉ each. On this collection the parse accounts for 55% of the structure and the three orders for 45%. Half an index is three permutations is where that split is measured and where one of the three turns out to be the inverse of another.

The run-length index holds the run heads in a wavelet tree, the run lengths, a sparse bit vector over the run starts, and a suffix-array sampling. At one copy the sampling is a small share and at sixty-four it is the largest single part, because the sampling is n/s values and n has not fallen while everything else has. That is what is still proportional to n, and it is the term the r-index’s run-boundary sampling exists to remove.

There is one more part that none of the three sizes above includes, and leaving it out is a choice rather than an oversight. A collection of documents usually wants to know which document an occurrence is in, and that is a document array plus whatever apparatus reads it — measured separately in this field because it sits on top of any of the three. Its size is a function of the document count and the length distribution, not of the repetition, so it is the one part of a collection’s index that a version history makes worse rather than better: more copies means more documents means a wider document array.

At sixty-four documents that array is a few thousand bits against a run-length index of about twenty-seven thousand, so it is not decisive. At the document counts a real archive has it can be comparable, and the document array is the length distribution is where its own compression is measured.

A collection can be measured before it is indexed #

The practical form of all this is that the choice does not require building three indexes.

Compute r and z on the collection — both are linear-time and both are cheap relative to constructing anything — and compute H₀ from the character frequencies. Multiply n·H₀ for the first, and roughly r(2⌈log₂ n⌉ + ⌈log₂ σ⌉) and z(2⌈log₂ n⌉ + 3⌈log₂ z⌉) for the other two. The three numbers order the same way as the built structures do, to within the directories.

That is not a new observation, and the reason it is worth making here is the shuffled control. A collection reporting a low z/n may be reporting a logarithm rather than repetition, and a structure chosen on the uncorrected number will be chosen on an artefact. The correction is one shuffle, and on a collection where it matters it is the difference between 4.7 and 3.2.

Reading the plate as a decision rather than a description #

The plate has four points on it and a reader who has a collection in hand can locate themselves on it in about a minute, which is the whole of what it is for.

Take the collection, run a Lempel–Ziv parse and a Burrows–Wheeler transform on it, and compute z/n and r/n. Shuffle it and do the same, to get the control. Divide. A corrected ratio near one means the collection is at the left-hand edge of this plate however large it is, and the entropy-bounded structure is the right one. A corrected ratio of three or more puts it at the right-hand edge, and the two falling structures are between two and four times smaller.

The middle is where judgment is needed, and the reason is that the plate’s x-axis is a construction rather than a property. A collection is not really “eight copies of a base”; it is a collection whose repetition happens to be worth about what eight copies would be worth. Two collections at the same corrected ratio can differ in the shape of their repetition — many short duplicated stretches against a few long ones — and r and z weigh those differently. A collection whose duplication is many short stretches has a phrase count that falls slowly and a run count that falls fast, and its point on this plate is two points.

That is the honest limit of a two-line summary of a collection, and it is why the measurement is quick rather than automatic. What the plate settles is the large question — is this collection at the left edge or the right — and that question is settled by the corrected ratio, which no amount of shape can disguise.

The alphabet matters to that procedure and it is easy to forget. On four symbols the control’s own arithmetic falls faster with size, so a rule of thumb calibrated on English overstates what a DNA collection’s repetition is worth. Every structure on this plate is used on DNA more than on anything else, which makes it the case where the correction is most needed and least often applied.

What the flat line is good for #

Ending on the FM-index’s flatness as a defect would be the wrong reading, and it is worth closing that off.

A structure whose size is n·H₀ has a guarantee. It is that size on every text, and the size can be computed from the character frequencies before anything is built. The two falling structures have no such guarantee: their sizes depend on a property of the arrangement that has no bound in terms of anything simpler, and on an adversarial text they are worse than storing the text.

So the three structures trade a bound against an opportunity. The FM-index takes the bound and cannot benefit from repetition. The other two take the opportunity and have no bound. A collection that knows what it holds should take the opportunity; a service indexing whatever arrives should think carefully about the bound, because the worst case is not a rounding.

That framing also explains why hybrid structures exist and why this collection has not built one. A structure taking the minimum of the two — an entropy-bounded index with a run-length representation of the levels whose bit vectors have long runs — gets the bound and most of the opportunity. It is the obvious next thing and it is a different strand.