The collection decides which index is small

This field now holds three compressed self-indexes, and each of them is proportional to a different measure of the same text.

The entropy-bounded FM-index follows $nH_k$, the empirical entropy of the symbol distribution. The r-index follows $r$, the number of equal-letter runs in the transform. The phrase index follows $z$, the number of phrases in the greedy parse.

None of the three holds a text. All three answer the same three questions. And on the same collection, the largest of them is four times the smallest.

The reversal #

At one copy of a 512-character English text: the FM-index is 3,511 bits, the phrase index 7,285, the r-index 10,974.

At thirty-two copies of the same text: the phrase index is 8,892 bits, the r-index 17,047, the FM-index 34,615.

The FM-index went from smallest to largest and the phrase index from middle to smallest, and the reason is entirely in the measures. $nH_3$ runs from 324 bits to 10,175 across that sweep because the entropy of a distribution cannot see a copy. $r$ and $z$ go from 229 and 155 to 233 and 156, because both can.

The entropy that cannot see a copy is where that property was first measured, and it is the whole of the reversal: the structures are following their measures faithfully.

And the other reversal #

Repetition is not the only axis and the ordering moves on the other one too.

On a four-symbol text with no copying, the FM-index is 1,715 bits, the phrase index 6,615 and the r-index 16,714. The entropy-bounded structure wins by a factor of four over the next and by ten over the last, because a four-symbol alphabet is where a wavelet tree is cheapest and where both repetition measures are at their worst — 0.75 runs per character, and phrases of two or three characters.

So there are two properties of a collection and they push in opposite directions. A small alphabet favours the entropy-bounded structure; repetition favours the other two; and a repetitive collection over a small alphabet is a genuine contest.

Two numbers decide it, and both cost one pass #

The decision does not need a benchmark. It needs $r/n$ and $z/n$ on the corpus in hand, and both are one pass over the text.

If $z/n$ is under about a fiftieth, the phrase index will be the smallest of the three by a factor.

If $r/n$ is under about a fiftieth but $z/n$ is not, the r-index is competitive; if $r/n$ is over a half, its sampling alone will exceed the whole suffix array, which is what a sampling that costs more than the array measures.

If neither is small, the entropy-bounded index is the right structure and the other two are paying for machinery they cannot use.

Those thresholds are constants of this collection’s own structures rather than universal, and they are stated as approximations for that reason. What is exact is that the three sizes are $c_1 nH_k$, $c_2 r\log(n/r)$ and $c_3 z\log n$ with measurable constants, so the ranking is decided by the measures once the constants are known — and this strand measures the constants.

The size is not the whole comparison #

Three structures with the same interface do not have the same costs behind it, and a decision made on size alone would be made on a third of the evidence.

Counting — how many times a pattern occurs — costs two ranks per pattern character in the FM-index and the r-index, independent of the answer size. The phrase index cannot count without enumerating.

Locating — where the occurrences are — costs up to $s$ LF steps per occurrence in a regularly sampled FM-index, one predecessor query per occurrence in the r-index, and two stages in the phrase index: a search over the boundaries plus a propagation per occurrence.

Extracting — producing the text — costs one LF step per character in both transform-based structures and a chain walk in the phrase index, whose depth on a collection of thirty-two copies averages 17.89 and reaches 38.

So the smallest structure has the dearest character and the only structure that answers how many cheaply is not the smallest. The character that costs a chain is that price in full, and every occurrence at the same price is the locate comparison between the other two.

The costs that are not sizes, tabulated #

The three questions have nine answers between them and they are worth setting down in one place, on the collection of thirty-two copies where the sizes are 8,892, 17,047 and 34,615 bits.

Count. The FM-index and the r-index both narrow an interval, two ranks per pattern character, independent of how many occurrences there are — 144 ranks for a six-character pattern with 112 occurrences. The phrase index has no interval and no count: it finds the primaries, propagates, and reports the length of the list.

Locate. The r-index takes one predecessor query per occurrence and no LF step, checked by a counter that must be unchanged after the query. A regularly sampled index at one value in thirty-two takes 14.2 LF steps per occurrence on the same query. The phrase index takes a flat three candidates in its search stage and 4,352 phrase examinations in its propagation, to produce 32 occurrences.

Extract. One LF step per character in both transform-based structures; a chain of 17.89 follows on average in the phrase index, with a worst of 38 and a ninetieth percentile of 31.

Nothing in that table is comparable across rows. A rank, an LF step, a phrase examination and a chain follow are four acts, and this collection’s rule is to name them rather than to sum them — which the count somebody chose is the argument for and three savings in three currencies is this phase’s other instance of.

What each structure is best at #

Set out as three sentences, because a reader wanting the decision should not have to assemble it.

The compressed FM-index is the general-purpose structure: smallest on text that does not repeat, cheapest per character extracted, and the only one whose costs do not depend on a property of the collection. Its size grows with the collection whatever the collection contains.

The r-index is the structure for a repetitive collection that is queried for positions: its sampling is $2r$ values and its locate is one predecessor query per occurrence, so it is the only one of the three whose locate cost is both constant per answer and independent of a rate.

The phrase index is the smallest structure on a repetitive collection and the most expensive to read: no counting, a two-stage locate, and a chain per character.

None of those sentences is a ranking, and a plate that produced one would have chosen an axis.

The measures are not interchangeable either #

It would be convenient if $r$ and $z$ were two estimates of one quantity and a structure could be sized from whichever was cheaper to compute. They are not, and this strand measured three ways in which they differ.

They order texts differently in magnitude. On the five texts here $z$ is between 1.4 and 3.8 times smaller than $r$, and the ratio is not constant.

One of them depends on the alphabet’s order. Renaming the symbols leaves $z$ exactly unchanged and moves $r$ by two to sixteen per cent on ordinary texts, and by a factor that grows without bound on a constructed family. That is the measure that cannot see the alphabet.

They fail differently. A text with no repetition gives $r \approx 0.75n$ and $z \approx n/\log_\sigma n$, so both structures degrade, and the run-based one degrades further.

What the strand added to the field #

Two structures and one repair, and it is worth being precise about which is which.

The r-index is a repair of a structure this field already had. The index that stores the runs built a run-length FM-index whose transform was $O(r)$ and whose sampling was not, and what is still proportional to n measured the consequence: half the structure was the part that had nothing to do with runs. Replacing the sampling with two values per run and a function with $r$ pieces removes that term.

The phrase index is new capability. Nothing in this field could be sized by $z$ before, because $z$ was a number the collection measured and built nothing on.

And both of them make the same point from different sides, which is why they arrived in one phase: the measure a structure is proportional to is a design decision, and it decides what the structure is small on. That is the theme this strand contributes, and it is not a statement about compression at all.

The three constants, measured #

The sizes are constants times measures and the constants are what a decision needs, so here they are on the collection of thirty-two copies.

The phrase index is 8,892 bits for $z = 156$ phrases: 57 bits a phrase, which is two positions at fifteen bits, a literal at five, and three boundary orderings at eight bits each.

The r-index is 17,047 bits for $r = 233$ runs: 73 bits a run, which is two suffix-array values at fifteen, a predecessor anchor, a wavelet-tree symbol and the sparse vectors’ shares.

The FM-index is 34,615 bits for 16,384 characters: 2.11 bits a character, against an order-three entropy of 0.62 — so the structure is 3.4 times its own bound, which is where its rank directories and sampling go.

Those three constants are the reason the ordering is not simply the ordering of the measures: $z < r$ by 1.49 and the structures differ by 1.92.

What a fourth structure would have to beat #

The field’s three structures leave an obvious gap and it is worth naming precisely, because it is the shape of the next thing.

The phrase index is the smallest and cannot count. The r-index counts cheaply and is twice the size. Nothing here is both — a structure proportional to $z$ that answers how many without enumerating, or one proportional to $r$ at the phrase index’s constant.

The published literature has candidates on both sides, and this collection has built neither: an index proportional to $z$ with a grid over the boundaries answers a search faster than the filtering used here, and an r-index with a compressed predecessor structure is smaller than the one measured here by a term this strand does not estimate.

So the constants above are this collection’s, on this implementation, and the ordering they produce is robust to the constants moving by a third and not by a factor of two.

Where a fourth measure would come from #

Three measures is not the end of the list, and the two that are missing are worth naming because they bound what this field can still do.

There is a measure smaller than both of these — the size of the smallest set of positions such that every substring of the text has an occurrence touching one of them — and structures proportional to it are known to exist. This collection has not measured it and builds nothing on it.

And there is the number of phrases in a non-greedy parse, which can be smaller than $z$ and is harder to compute. The greedy parse is optimal in phrase count among parses that always take the longest match, and a parse allowed to take a shorter match now to enable a longer one later is a different optimisation.

Both would be measured the same way as $r$ and $z$ were: count them on the five texts, put them on the plate beside the others, and see whether they order the collections differently. That is the method this strand used and it is cheap; what is expensive is building a structure on the answer.

The seal, which all three are measured under #

One thing is constant across all three structures and it is what makes their sizes comparable at all.

None of them keeps a text. Each is handed one at build time, and afterwards a query that reads a character is stopped at the read — so a structure that quietly kept a copy to compare against would be caught rather than reported as small and fast.

That check matters most for the phrase index, whose search compares characters and therefore has an obvious reason to want the text. It matters least for the FM-index, which has no reason to touch it. And it is the reason the text that does not have to be kept came before any of this: a size claim about a self-index is a claim about what it does not have.

The decision, in one paragraph #

Measure $r/n$ and $z/n$. If both are large, build the entropy-bounded index and stop. If $z/n$ is small and the workload is searching rather than reading, the phrase index is the smallest structure by some factor. If the workload includes counting, or extracting long stretches, or locating patterns with many occurrences, the r-index is the one whose costs stay flat.

And if the corpus is a collection of near-copies — versions of a document, genomes of one species, logs with a fixed skeleton — then all three of those questions have the same answer as they do here, because that is what the sweep in this strand is a model of.

The thresholds, derived from the constants rather than estimated #

The decision above is stated with thresholds about a fiftieth, and three sections later the constants are measured. Putting the two together turns the rules of thumb into crossings, and one of the three turns out not to be a crossing at all.

Set the three sizes against each other. The phrase index is $57z$ bits, the r-index $73r$, and the entropy-bounded index $2.11n$ on this collection:

• phrase beats entropy-bounded when $57z < 2.11n$, so when $z/n < 0.037$ — about a twenty-seventh;
• r-index beats entropy-bounded when $73r < 2.11n$, so when $r/n < 0.029$ — about a thirty-fifth;
• phrase beats r-index when $57z < 73r$, so when $z/r < 1.28$.

Every size on this page obeys them. At thirty-two copies $z/n$ is 0.0095 and $r/n$ is 0.0142, both under their thresholds, and both repetition-based structures are indeed under the entropy-bounded one. At one copy the same ratios are 0.303 and 0.447, both far over, and the entropy-bounded index is smallest. Six predictions, six agreements, from three constants.

Two things follow that the paragraph of thresholds does not say.

The first two thresholds are not fractions; they are multiples of the entropy. The 2.11 bits a character is 3.4 times an order-three entropy of 0.62, so the real condition is $z/n < 0.060\,H_k$ — and a fiftieth is only right at the entropy this collection happens to have. On four-symbol text, where the FM-index measures 3.35 bits a character, the same arithmetic puts the crossing at $z < 30$ phrases in 512 characters, and DNA parses into phrases of two or three, giving several hundred. That is why the entropy-bounded structure wins there by a factor of four, and it is a prediction rather than an observation once the constant is in hand.

The third threshold is not close. $z/r < 1.28$ is the only one of the three with no entropy in it — it is a ratio of two measured constants and nothing else — and every text in this strand sits far below it. The measures section reports $z$ between 1.4 and 3.8 times smaller than $r$, which is $z/r$ between 0.26 and 0.71, against a crossing at 1.28.

So the phrase index is smaller than the r-index on every text this collection has measured, and would stay smaller if its constant rose by 80%. That is not a contest, and the decision paragraph is right to send a reader to the r-index for reasons that are never about size: it counts, its locate is one predecessor query per occurrence, and its extraction does not walk a chain. Every occurrence at the same price is the argument for it, and it is an argument about costs.

The condition under which the ordering could reverse is worth naming, because it is reachable rather than hypothetical. $z/r$ would have to exceed 1.28, which needs a text whose runs are far cheaper than its phrases — and $r$ is the measure that moves with the alphabet’s order, by up to a factor without bound on the constructed family the measure that cannot see the alphabet builds. An adversarial symbol ordering is the one thing on this page that could put these two structures in the same size band.

The honest limit #

Every measurement here is on generated texts at a few thousand to sixteen thousand characters, and every constant quoted is this implementation’s. A published r-index uses a better predecessor structure and a published phrase index uses a grid rather than a filter, so both would be smaller and faster than the ones measured here by amounts this collection has not estimated.

The collections are copies with an optional uniform substitution rate. Real repetitive corpora repeat in structured ways — a version history changes a paragraph, not one character in a hundred — and both measures respond to the difference.

And no construction cost appears anywhere. The parse here is quadratic, the transform is built by sorting rotations, and the peak memory during construction is larger than any of the three structures. On a real corpus that is the term that decides whether an index can be built at all, and it is measured nowhere in this field.