An index that cannot locate

The structure is easy to describe: an FM-index with two of its five parts removed.

It is harder to build honestly. An object that still holds the sampled positions and merely promises not to read them proves nothing about what it costs — so this one is constructed in full, its own size recorded, and then its samples and marks set to null. After the constructor there are no positions anywhere in it, and asking it to locate raises rather than returning something plausible.

What it keeps #

The wavelet tree. 18,377 bits over eight thousand characters of a four-symbol alphabet. This is the transform, stored as one bit vector per level of a code tree, and it is what makes rank possible at all — rank is the only thing it does is the essay about how much of an index reduces to that one operation.

The rank directories. 5,037 bits. Block and superblock counts, so that a rank is a table lookup and a short scan rather than a walk.

The C table. 100 bits — one cumulative count per symbol, which is what turns a rank into a row.

Between them, 23,514 bits of the 35,305 the full index costs. That is what an index needs to answer how many and to move an interval, which is what a search does from its first character to its last.

What it drops #

The sample marks, 8,193 bits: one bit per row, saying whether this row’s text position was kept.

The sampled positions, 3,598 bits at one in 32: the positions themselves, ⌈log₂ n⌉ bits each.

Together 11,791 bits, a third of the index, and every one of them exists so that a row can be turned into a place in the text.

What it can still do #

Everything a search does.

It counts: a backward search over a pattern narrows an interval to the rows beginning with it, and the width of that interval is the occurrence count. It extends: a bidirectional extension asks it for the rank of a symbol and the total width of the smaller symbols’ intervals, both of which are ranks. It refuses, loudly, when asked where anything is.

The search does not notice. Same rows found, same interval extensions performed, same positions reported — because the positions were always read out of the forward half, for the reason the half that is never asked where sets out: the reverse half’s rows are positions in a reversed text, and the occurrences everybody wants are already in the forward interval at the right coordinates.

What a bidirectional index costs with one of these in it #

The arithmetic is one line: a full forward half at 35,305 bits, a counting-only reverse half at 23,514, against two full halves at 70,610.

58,819 bits against 70,610 — a saving of 16.7%, at one sampled position in 32 over eight thousand characters.

That is what the deferral naming this structure predicted: about a sixth of the second index. It is exactly a sixth of the whole thing, and it is a third of the half it comes out of.

What the three kept parts actually do during a search #

Following one extension through the counting half makes the split concrete, and it is worth doing once because it explains why the three parts that stay are exactly the ones that stay.

A right extension by symbol c needs two things from the reverse index. It needs the rows of c within the current interval, which is C[c] + rank_c(sp) and C[c] + rank_c(ep) — the C table for the base, the wavelet tree and its directories for the two ranks. And it needs the total width of every smaller symbol’s interval, which is a rank of each symbol below c, or one compound walk once the tree’s leaves are in the alphabet’s order.

Every one of those is a rank or a table lookup. There is no step in an extension that consults a position, and there is no step that consults the text — the transform is inside the wavelet tree, and the wavelet tree is what is being asked.

Then the search finishes, and the last step reads occurrences out of the forward interval. That is one locate per occurrence, on the forward half, using the forward half’s marks and samples. The reverse half’s part in the query ended at the last extension.

So the three kept parts are the ones every step of the search touches, and the two dropped parts are the ones only the final step touches — on the other structure.

Why “a sixth” needs a footnote #

Because the sampling rate is a dial and the answer moves with it.

At one sampled position in 4 the locating apparatus is 36,879 bits of a 120,786-bit structure and the saving is 30.5%. At one in 128 it is 14.0%. Same construction, same text, same alphabet: a factor of two between the ends of a parameter that nobody quotes when quoting an index’s size.

A sixth of what, exactly is the page about that, and about why the curve does not go to zero at the sparse end — the marks are n bits however rarely a position is kept, so the saving has a floor that the positions cannot reach.

The check that makes it a measurement #

An index that has been stripped has to be unable to answer, and that is a thing to test rather than to assert.

The check is two lines: ask the counting half to locate, require it to raise; then look at the object and require the samples to be gone. Both halves of that matter. An index that raises because a flag was set but still holds the arrays has the same size as a full one, and the number on this page would be a claim about code somebody read.

The mirror check matters more. Strip the forward half instead — the one that does locate — and the search still runs, still finds the same interval, and then fails at the last step when it tries to read a position out of it. That failure is the one that says the asymmetry is real and in one direction only, and it is in the gate: a bidirectional index with its forward samples removed must not be able to report occurrences.

What this is not a saving on #

Three things, so the number is not read wider than it is.

Not on query time. The counting half performs exactly the ranks it performed before. Removing the locating apparatus removes no work, because the work was never done.

Not on the forward half. Everything above is about one of the two indexes. The forward half keeps all five parts, because it is the one that answers the question at the end.

And not on a single index. An FM-index on its own has to locate — that is what it is for. This saving exists only where there are two indexes and one of them is structurally exempt, which is a bidirectional index and, as far as this collection has looked, nothing else.

What it means for the text #

There is a fourth thing an FM-index usually has to do, and it is worth saying why it does not appear in the split above.

An index of this family is self-indexing: it can produce the text back, so the text does not have to be kept beside it. The text that does not have to be kept is the essay about that property, and it is what makes the size on every plate here the whole cost rather than a cost beside a file.

Extraction walks backwards from a known row, one LF step per character, so it needs the wavelet tree and the C table and nothing else — no samples, no marks. A counting-only index can therefore still hand back the entire text. What it cannot do is start in the middle: extraction from an arbitrary position needs a second sampling indexed by position rather than by row, which this collection has priced and not built, and which the counting half would not carry either.

That is a pleasing accident of the split rather than a design. The two parts that answer “where in the text is this row” are exactly the two that a reversed text has no use for, and the parts that produce text are shared. So a counting-only reverse half can still, in principle, reproduce the reversed text — which is the forward text backwards, and therefore the forward text.

Where the asymmetry comes from #

Worth naming, because it is a pattern rather than a trick.

Two structures answer the same questions and only one of them is asked all of them. That happens when a construction keeps a redundant copy for a mechanical reason — here, so that a pattern can be extended at either end — and the redundancy is only needed for part of what the copy can do.

The response is to ask, of every part of the redundant copy, which question it answers and whether that question is ever put to it. Here the answer sorted the five parts into three and two, cleanly, and the two were a third of the structure.

That question generalises past this structure, and an index has a size is the theme it belongs to: a size table with parts in it is a size table somebody can subtract from, and a size quoted as one number is one nobody can.

What the same reasoning removes elsewhere #

Two other places in this collection, found by asking the same question of a different structure.

The chain of previous occurrences in a document index is n⌈log₂ n⌉ bits, and the listing algorithm compares one entry of it against the start of a range — never using the value for anything else. The array the walk never reads is where that goes, and the answer is that the array can be dropped entirely rather than shrunk.

A range minimum’s values. The structure answers “where is the smallest” by storing the shape of the array and not its numbers, so the numbers belong to the caller — and a caller that only ever compares the answer can drop them too.

Both are the same move: separate what a structure holds from what its callers ask, and remove what nothing asks for. The counting-only index is the smallest of the three and the easiest to see, which is why it is the one that had been named in a plan and left unbuilt.

What it is worth building #

The honest answer is that it is worth building when the saving is spent rather than banked.

Sixteen per cent off a structure is not nothing, and it is also not the kind of number that changes what is possible. What changes something is the next page: the bits removed from the half that never locates can be given to the half that does, and a denser sampling there makes a locate several times faster at the same total size.

What is not measured here #

Compressed bit vectors. Every size on this page uses plain bit vectors with block and superblock directories. A run-length or entropy-compressed vector changes the wavelet tree’s size and the marks’ size by different factors — the marks are a sparse vector, one bit in 32 set, which is exactly the case a compressed representation is good at — so the 16.7% would move, probably down, and by an amount nothing here computes.

Larger alphabets. Eight thousand characters of a four-symbol alphabet gives a wavelet tree two levels deep. On English or on source code it is five, and the counting parts grow while the locating parts do not — so the saving falls as the alphabet grows. The direction is clear and the amount is not measured, which is a gap worth naming since the collections this field is actually about have alphabets of a hundred.

And the second sampling. A real index that supports extraction from an arbitrary position carries a position-indexed sampling as well, which this collection names and does not build. It belongs to the forward half, it is about the same size as the row-indexed one, and adding it would make the forward half larger and the saving on the reverse half a smaller share of the total.

What a larger alphabet does, derived rather than left open #

The alphabet is named above as a gap — the direction is clear and the amount is not measured — and it can be closed from the parts already on this page, because each of the five scales in a known way.

The locating apparatus does not depend on the alphabet at all: $n$ bits of marks plus $(n/s)\lceil\log_2 n\rceil$ of positions, and neither expression contains $\sigma$. The counting parts do. A wavelet tree’s size is the text length times its mean code depth — the identity a factor of fourteen, for four per cent establishes — and the directories are a fixed fraction of the vectors beneath them, measured here at 27%.

So the saving is

$$\frac{1 + (\log_2 n)/s}{2\left(1.27\,d + 1 + (\log_2 n)/s\right)}$$

where $d$ is the tree’s mean depth. Checking it at the parameters on this page: $n = 8192$, $s = 32$, and a tree of 18,377 bits over 8,192 characters, so $d = 2.24$. The numerator is 1.41, the denominator is $2(2.85 + 1.41) = 8.52$, and the quotient is 16.5% against the 16.7% measured. The expression is the parts, rearranged.

Now move the alphabet. A hundred symbols under a fixed-length code gives $d = 7$, and the same expression returns 6.8%. Under a Huffman-shaped tree, where English’s mean depth is nearer 4.5, it returns 9.8%.

So the saving falls from about a sixth at four symbols to between a fifteenth and a tenth at a hundred — a factor of two, and the direction the essay predicts, now with a number and a mechanism.

Two consequences worth having.

The first is that this strand’s headline is at its most favourable on the alphabet it was measured on. Four symbols is the shallowest wavelet tree there is, so the counting parts are as small as they get and the locating parts are as large a share as they get. On the collections the field is actually about — text, source, protein — the counting-only half is a smaller economy than sixteen per cent, and quoting the sixth without the alphabet is quoting a best case.

The second is that the two dials pull the same way. The sampling rate and the alphabet both move the ratio between the counting parts and the locating ones, and both are usually left unstated: a saving of 30.5% at one position in four on four symbols and one of 6.8% at one in 32 on a hundred are the same construction, a factor of four and a half apart, with neither number wrong.

Which is why the expression is more useful than either. It has four quantities in it — the length, the alphabet’s effect through $d$, the sampling rate and the directory fraction — and every one of them is knowable before the structure is built. A sixth of what, exactly sweeps one of the four; this is the other three, and the gap the essay names is closed by arithmetic rather than by a second sweep.

Where this sits in the strand #

The half that is never asked where is the observation this structure implements. A sixth of what, exactly is the parameter sweep that turns 16.7% into a range. The saving, spent is what the bits buy when they are moved rather than banked.

And the thing all four rest on is an invariant from an earlier strand: the two intervals of a bidirectional search have the same width at every step, which is what makes the forward interval exact and therefore the only one anybody needs to read positions from. That check exists because a deliberate defect — the pruning that loses an occurrence is the neighbouring failure — is otherwise invisible in the answers.

The same question, asked of a different structure #

The move here is: find a component that is duplicated for symmetry, and ask which of its abilities are exercised.

The array the walk never reads is the same question asked of a document index, and it produces a stronger answer: the chain of previous occurrences is not half-used, it is entirely unused, and it is n⌈log₂ n⌉ bits — as wide as the suffix array.

Two structures, two redundancies, and both were found by reading what the callers actually call rather than what the structure offers. Neither is a clever encoding; both are deletions.

That is worth generalising into a habit rather than a technique. A size table is a list of things somebody might not need. Reporting a structure as one number makes the question unaskable, which is why every plate in this collection reports parts.

And the reason the whole strand is four pages rather than one: three of them are measurements and only the last is advice, so the measurements stay checkable on their own.