An index with z in its size

An index proportional to the phrase count has no transform in it. There is no Burrows-Wheeler permutation, no wavelet tree, no rank directory, and no backward search. It stores a parse and three orderings of its boundaries, and everything it does it does from those.

On thirty-two copies of a 512-character text that is 8,892 bits, against the r-index’s 17,047 and a compressed FM-index’s 34,615 — and none of the three holds a copy of the text.

What is stored #

Four arrays, all of them $z$ entries long.

The phrase lengths. One value per phrase, from which the phrase starts are the running sums — so a boundary costs a length and nothing else.

The phrase sources. Where each phrase was copied from, one position per phrase, with a reserved value for a literal.

The literals. One character per phrase, used only by the phrases that have one.

Three orderings of the boundaries. The phrase starts sorted by the suffix beginning there, the same starts sorted by the reversed text ending there, and the phrases sorted by the source they copy from. Each is a permutation of $z$ items and costs $z\lceil\log_2 z\rceil$ bits.

That is the whole structure. On the collection above it comes to 0.543 bits a character, which is a number worth pausing on: the text it indexes is drawn from an alphabet of nineteen symbols and cannot be stored in less than about four bits a character without compression.

No transform, and therefore no rank #

The absence worth dwelling on is the one that changes what a query is.

Every other index in this field answers a search by narrowing an interval of rows: a search that runs backwards is the mechanism and rank is the only thing it does is the primitive it rests on. The pattern’s characters are never compared with anything; they index into a table.

Here there is no such table. A search compares pattern characters against text characters, in binary searches over the boundary orderings — which means the structure has to produce text characters, and it produces them by following the parse backwards until it reaches a literal.

So an index proportional to $z$ trades the transform’s machinery for a chain walk, and the chain walk is charged in its own counter throughout this strand. What that costs is the character that costs a chain; this essay is what it buys.

Why three orderings #

A search over a parse has one idea in it and the orderings are what make the idea executable.

An occurrence of a pattern either lies inside a single phrase, in which case it is a copy of an occurrence earlier in the text and does not have to be searched for at all, or it crosses a phrase boundary. There are $z$ boundaries and $m-1$ ways to split the pattern, so there are at most $z(m-1)$ places to look rather than $n$.

Finding them needs two questions per split point: which boundaries have the pattern’s left part ending at them, and which have its right part starting at them. The first is answered by the boundaries sorted by the reversed text ending there; the second by the boundaries sorted by the suffix starting there. An occurrence is a boundary in both ranges.

The third ordering — by source — is for the other kind. Given an occurrence, every phrase whose source region contains it produces a copy of it somewhere else, and finding those phrases is a range query over the sources.

What a boundary knows #

The three orderings are the structure’s whole search capability, and it is worth being precise about what each of them can answer, because the asymmetry explains the shape of every cost in this strand.

Sorted by the suffix that starts at a boundary, the boundaries answer which boundaries are followed by this string. That is a binary search with the pattern’s right-hand part as the key, and each comparison produces text characters from the parse — so a search over $z$ boundaries costs $\log_2 z$ comparisons, each of them a chain walk of whatever depth the position happens to have.

Sorted by the reversed text that ends at a boundary, they answer which boundaries are preceded by this string. Same cost, opposite direction, and it is the ordering that has no analogue in a transform-based index at all: a backward search reads the pattern from its end and needs nothing sorted the other way.

Sorted by source, the phrases answer which phrases copied from a region containing this position. That is not a question about the pattern; it is a question about an answer already found, which is why it belongs to the propagation stage rather than to the search.

Three orderings, three questions, and only the first two are used before an occurrence is known.

The sizes, and where each structure wins #

The plate at the top of this essay is one collection. Three of them are worth reading together, because the ordering of the three structures changes twice.

One copy, ordinary English. The compressed FM-index is 3,511 bits, the phrase index 7,285, the r-index 10,974. The entropy-bounded structure wins, because there is no repetition to exploit and both of the others are paying for machinery.

Thirty-two copies. The phrase index is 8,892, the r-index 17,047, the FM-index 34,615. The order has reversed completely: the structure sized by the entropy is now four times the structure sized by the parse.

Four-symbol text, no copying. The FM-index is 1,715 bits, the phrase index 6,615, the r-index 16,714. The entropy-bounded structure wins again and by more, because a four-symbol alphabet is where a wavelet tree is cheapest and where both repetition measures are largest.

There is no structure here that is always right, and the differences are factors of four to ten rather than constants. The index that is smaller than the text established that the compressed index’s size follows the text’s entropy; this strand’s finding is that following a different measure changes which text it is small on.

The part that does not shrink #

The phrase index has an alphabet-sized floor under it and it is visible in the numbers.

Nineteen of the 156 phrases on the repeated collection are literals — one per symbol of the alphabet, near enough — and they are there whatever the collection does. Their share is small on this text and would not be on a text with a large alphabet and heavy repetition, where a structure proportional to $z$ is mostly proportional to $\sigma$.

The other part that does not shrink is the widths. A source position is $\lceil\log_2 n\rceil$ bits, so the phrase table grows with the collection even when $z$ does not: 7,644 bits at two copies and 8,892 at thirty-two, which is 1.16 times across a sixteenfold growth in length. That is the same logarithmic creep the sampling that follows the runs reports for the r-index, from the same cause, and it is why “no term in $n$” is the wrong phrase for both structures.

What is deliberately not built #

Two pieces of the published structures are missing here and both are replaced by a counted approximation rather than assumed away.

The first is the intersection. Finding the boundaries that are in both ranges is a two-dimensional range query on a $z\times z$ grid, and the published indexes build a wavelet tree over that grid to answer it in logarithmic time. This one filters the smaller of the two ranges and counts the points it examines.

The second is the propagation. Finding every phrase whose source contains a given occurrence is another range query; this one walks the sources in order and counts the phrases it looks at.

Both counts are reported on every plate that mentions them, which is the point: the number of candidates examined is exactly what the grid exists to reduce, so a plate that showed a search cost without it would be describing a structure this essay did not build. On the collection above the propagation examines 4,352 phrases to produce 31 occurrences, and that ratio is what a grid would attack.

The measure and the structure are not proportional #

One arithmetic point deserves separating out, because it is the commonest way to misread a plate like the one at the top of this essay.

At thirty-two copies, $z$ is 156 and $r$ is 233 — a ratio of 1.49. The structures built on them are 8,892 and 17,047 bits, a ratio of 1.92. The structures are further apart than the measures, and the difference is machinery: the r-index carries a wavelet tree over its run heads, three sparse bit vectors, a $C$ table and a predecessor structure, and the phrase index carries four flat arrays.

The gap runs the other way on four-symbol text, where $z$ is 148 and $r$ is 412 — a ratio of 2.78 — while the structures are 7,844 and 25,177, a ratio of 3.21.

So the measures give the direction and the constants give the size, and a reader deciding between structures on the strength of $z < r$ would be right about the ordering here and wrong about the margin by a factor of about a third. That is the same warning the constant the notation drops makes about running times, arriving in a field where the quantity in question is a size.

The seal is live here too #

Every structure in this field is measured under the rule that a self-index may not read the text it claims to have replaced, and this one is no exception — which is more interesting here than elsewhere, because this structure’s search compares characters.

The comparisons are against characters the structure produces from the parse. The text handed in at build time is sealed afterwards, and the gate’s check is that a query performs zero reads through it. A structure that kept a copy of the text to compare against would search faster, report the same answers, and be a different structure with a different size.

That check is the one the text that does not have to be kept introduced, and it is load-bearing here in a way it is not for a transform-based index: an FM-index has no obvious reason to touch the text, and a parse-based one has an obvious reason on every comparison.

Correctness is checked against exhaustion #

The searching machinery here has more moving parts than a backward search — three orderings, $m-1$ split points, a range intersection and a propagation queue — and every one of them can be wrong in a way that returns plausible positions.

So the check is exhaustive rather than comparative: for four pattern lengths and five patterns each, the index’s occurrence set must equal the set found by scanning the text at every position. Not the same size, the same set.

That is the check that catches the failure this structure is most exposed to, which is reporting only the occurrences the search stage found. Those are all real occurrences and there are far too few of them — one against eight, on the measurement in the occurrences that cross a boundary. A gate asking whether the reported positions are occurrences passes it; a gate asking whether they are all of the occurrences does not.

What this adds to the field #

The field now holds three compressed self-indexes and they are sized by three different quantities: an entropy, a run count, and a phrase count.

That is not three implementations of one idea. Each of the three is small on a different kind of text, each answers a locate by a different mechanism, and one of them cannot be made to read the text at all while another has to be stopped from doing so. Which one to build is a question about the corpus, and the corpus answers it with two numbers that cost one pass each.

The collection decides which index is small is where that decision is set out with all three costs on the table. What this essay establishes is the middle one: the structure exists, it is the smallest of the three on a repetitive collection, and its size is $z$ times a width with nothing else in it.

Why a locate needs no sampling at all #

The structure has no analogue of a suffix-array sampling, and the reason is worth putting beside the two essays of this phase that are about nothing else.

A transform-based index finds occurrences as rows and has to convert them into positions, which is what a sampling is for and what the sampling that follows the runs and every occurrence at the same price are about. The conversion is a separate structure with a separate cost and a dial on it.

A parse-based index finds occurrences as positions from the start. A boundary is a text position; a split point is an offset; an occurrence is a boundary minus an offset. There is nothing to convert, so there is no sampling, no rate and no walk.

That is a real structural advantage and it is paid for elsewhere. The transform-based index answers how many without producing a single occurrence, in time proportional to the pattern and independent of the answer size; this one has to enumerate to count. Two structures, two questions each cheap on one side, and no ordering between them that survives both questions.

Fifty-seven bits a phrase, decomposed #

The structure’s size is $z$ times a width, and the width is worth writing out, because it turns out to be three logarithms with no measured constant in it at all.

Each phrase carries a length and a source at $\lceil\log_2 n\rceil$ bits, a literal at $\lceil\log_2\sigma\rceil$, and a slot in each of three orderings at $\lceil\log_2 z\rceil$:

$$\text{bits per phrase} \;=\; 2\lceil\log_2 n\rceil \;+\; \lceil\log_2\sigma\rceil \;+\; 3\lceil\log_2 z\rceil$$

Evaluate it. On the English collection at thirty-two copies, $n = 16{,}384$ gives 14, $\sigma = 19$ gives 5, and $z = 156$ gives 8 — so $28 + 5 + 24 = \mathbf{57}$, against a measurement of $8{,}892/156 = 57.0$. On the four-symbol text, $n = 8{,}192$ gives 13, $\sigma = 4$ gives 2, and $z = 148$ gives 8 — so $26 + 2 + 24 = \mathbf{52}$, against 53.0.

Two collections, two alphabets, no fitted term. The structure’s constant is not a constant; it is a formula, and it can be evaluated before the parse is run given only a guess at $z$.

Which lets the creep be checked rather than described. Between two copies and thirty-two, $n$ goes from 1,024 to 16,384 — four doublings — so the two position fields widen by four bits each and nothing else moves, since $z$ is 156 throughout and the alphabet is unchanged. That predicts $156 \times 8 = 1{,}248$ extra bits. The measurement is $8{,}892 - 7{,}644 = \mathbf{1{,}248}$.

Every bit of the sixteen per cent growth is two integer fields getting wider, and the prediction for the next sixteenfold growth is another 1,248. That is a sharper statement of the point about “no term in $n$” than the phrase itself: there is a term in $\log n$, it is $2z$ bits a doubling, and it is exactly computable.

The decomposition also relocates which part is which. Of the 57 bits, 33 are the parse — two positions and a literal — and 24 are the three orderings, so the structure is 58% the object it stores and 42% the index over it. The plate calls the orderings the largest part, and they are the largest single row; they are not the majority, and the distinction matters because the two halves scale against different variables.

The parse’s share grows with the collection and the orderings’ share does not. On a repetitive collection $z$ stops moving while $n$ keeps rising, so every additional copy widens the positions and leaves the orderings alone: at thirty-two copies the split is 33 against 24, and at a thousand copies of the same text it would be 43 against 24. The part that a published index replaces with a grid is the part that has stopped growing.

That is the opposite of the intuition the parts plate invites, and it changes what a size improvement would be worth. Replacing three permutations with a grid attacks a fixed 42% that is shrinking as a share; narrowing the two position fields — by storing sources relative to the phrase rather than absolutely, say — attacks the part that grows. Neither is built here, and the collection decides which index is small prices the whole structure against its neighbours on the assumption that both stay as they are. The r-index’s own logarithmic creep, which the sampling that follows the runs reports from the same cause, is the same arithmetic with $r$ in place of $z$.

The honest limit #

The three orderings are stored as permutations and the sizes above charge them at $z\lceil\log_2 z\rceil$ bits each. A published index stores the grid rather than the permutations and pays a related but different amount; the comparison here is therefore between structures that answer the same questions with different constants, and the plates say what each is storing rather than claiming a canonical size.

The search costs are not sizes and are not on these plates. The intersection is a filter and the propagation is a scan, so the query costs measured in this strand are upper bounds relative to a structure with the grids, and every plate that reports them reports the candidate counts beside them.

What is not measured anywhere here is construction. The parse is quadratic in this implementation, and the orderings are built by sorting with a comparator that reads the text while it is still open. Neither cost appears in any figure, and on a real corpus the parse is the expensive part of building the structure.