A bound that has to be paid for

A search that walks an index rather than filling a table has one argument in its favour and it is not speed. It is that the index is small: the text that does not have to be kept is the essay about what that means, and the whole field of self-indexing is built on it.

The pruning in the branch that cannot reach an answer removes seventy per cent of the search tree. This essay is what it costs, and the cost is in the one currency the structure was chosen for.

The bill in operations, which is trivial #

Seventy-two rank operations over a sixteen-character pattern, and they remove 27,906 interval extensions at a budget of three. That is 388 extensions removed per rank spent.

There is no exchange rate under which that is a bad trade, and it is worth checking why rather than accepting it: an interval extension is two rank operations on the same wavelet tree plus a comparison, so the two acts differ by a small constant and not by a class. A trade of 388 to one between two acts within a factor of three of each other is a trade under any accounting.

A rank and an interval extension are close relatives — an extension is two ranks plus some arithmetic — so the two acts are within a small factor of each other, and 388 to one survives any reasonable adjustment.

That is unusual on this site and worth saying when it happens. Most of the trades here need a plate because the answer depends on which resource the reader is short of; this one does not.

The bill in bits, which is not #

Computing $D$ requires extending the pattern to the right while maintaining the interval of text positions where it occurs. An FM-index extends to the left. So the bound needs a second index, over the same text read backwards.

Measured: 17,033 bits for the reverse index against 17,032 for the forward one. The structure doubles.

That is not an implementation detail that a cleverer version would avoid. The two indexes are over different strings — a text and its reverse — and neither can answer the other’s questions. There is a published structure that does both, the bidirectional index, and it is not free either: it stores the transform of both strings and adds machinery to keep two intervals in step.

Why doubling the index is worse than it sounds #

Because of what the structure was chosen for.

A bounded-error search can be answered three ways, and this collection has built all three. Fill the whole dynamic-programming table, which is $n \times m$ cells and needs the text. Use a filter to propose candidate windows and verify them, which needs the text. Or walk an index, which needs no text at all.

The third is not chosen because it is fastest — the search that spends a budget measures the crossing where it stops being so, and it is at a budget of four. It is chosen because the index is smaller than the text and answers without it. A version of it that carries two indexes has spent the advantage it was selected for.

The arithmetic: the forward index is 17,032 bits over three thousand characters of four-symbol text, and the packed text is 6,000 bits. So one index is 2.8 times the packed text, and two are 5.7 times. Against a table-filling search that keeps 6,000 bits of text and allocates a row at a time, the “small” structure is now nearly six times the size.

This is the trade an index larger than what it indexes is about, arriving from an unexpected direction: not because the index is badly built, but because a pruning needed a second copy of it.

Three currencies, and the exchange rates are not available #

The filter strand ended with a four-way plate and no winner, for a reason three savings in three currencies states: a counting filter saves cells, a seed filter saves text reads, an index walk saves both while spending ranks, and there is no rate between a cell, a read and a rank that this collection is willing to assert.

The pruning adds a fourth column to that plate and it is the only one denominated in bits. Ranks removed and bits added cannot be compared at all: one is a cost per query and the other a cost per structure, so the exchange rate between them is the number of queries — which is the reader’s, not the measurement’s.

The honest form of the result is therefore a break-even: the pruning pays when the number of queries times the operations saved exceeds whatever the reader charges for 17,033 extra bits. At a budget of three that is 27,906 operations a query, so a reader running a thousand queries saves twenty-eight million operations for two kilobytes. Almost anyone would take it. A reader running one query would not.

That framing is the same one the rule that pays on a long enough text uses for a precomputation against a scan, and the same one what a second pass buys uses for a pass against a bound. It is the standard shape for a fixed cost against a repeated one, and the only thing that makes it hard here is that the fixed cost is space rather than time.

The sizes, itemised #

The reverse index is the same class of object as the forward one, so its parts are the same parts, and the near-identity of the two totals is worth a moment.

An FM-index over $n$ characters holds a wavelet tree over the transform, the rank directories that make the tree answerable, a bit vector marking the sampled rows, the sampled positions themselves, and a table of first-column offsets. The transform of a string and the transform of its reverse are different permutations of the same multiset of characters, so the wavelet tree’s payload is identical — the same symbol frequencies give the same Huffman shape and the same total code length.

What differs is the run structure, and with plain bit vectors nothing charges for runs. So the two totals come out one bit apart, and that one bit is a rounding in the sample marking.

That is a small illustration of a result this field already has: the transform that emits nothing measures that the Burrows-Wheeler transform changes the size of a plain index by nothing at all, because it is a permutation and a plain bit vector charges one bit per bit. Reversing the text is another permutation, and it changes nothing either. With compressed bit vectors the two would differ, by however much the two texts’ run structures differ.

What could be computed without the second index, and what could not #

Worth asking, because “a second index is required” is the kind of claim that is often an implementation talking.

A bound on the pattern’s suffixes needs no second index: the forward index extends leftwards, so reading the pattern right to left and counting the resets gives a lower bound on the errors in each suffix, for free. It is a perfectly good bound. It bounds the wrong thing — the walk consumes the pattern from the right, so what it has left is a prefix — and using it prunes states that hold answers, which the fourth essay on this ladder measures.

A bound on the prefixes computed some other way would need to know, for each prefix, whether it occurs in the text. Nothing in the forward index answers that without extending rightwards. A suffix array would, at $n\lceil\log_2 n\rceil$ bits and a text; a suffix automaton would, at more; a $q$-gram table would give a weaker bound at $\sigma^q\lceil\log_2 n\rceil$ bits.

So the second index is not the cheapest possible way to compute the bound, but every alternative is a second structure of comparable size, and the reverse index is the one that reuses code that already exists and is checked. The claim that survives is: a bound on prefixes requires a structure that can be extended rightwards, and the forward index is not one.

What a bidirectional index would change #

The published alternative deserves a paragraph, because it changes the accounting rather than removing the cost.

A bidirectional FM-index maintains two intervals — one in the forward index and one in the reverse — and can extend a pattern in either direction. It costs both transforms, so the payload is the same two structures; what it saves is the sampling and some of the machinery, and it buys the ability to compute the bound and run the search over one object.

More interestingly, it makes a different search possible: a bidirectional walk can start in the middle of the pattern and grow outwards, which is a strictly better search order for a bounded-error walk because it reaches the pruning’s evidence sooner. That is not built here and it is the most obviously valuable thing this ladder does not have.

What it does not do is make the bound free. The information the bound is computed from — where each piece of the pattern stops occurring — requires the reverse transform, and the reverse transform is the cost.

The reverse index is not a copy of the forward one #

A small point that decides whether the doubling is avoidable, and it is not.

The reverse index is not the forward index read backwards, and it cannot be derived from it cheaply. The Burrows-Wheeler transform of a string sorts that string’s rotations; the transform of the reversed string sorts a different set of rotations, and there is no cheap map between the two orders. Reconstructing one from the other means recovering the text and transforming it again, which is the whole construction.

So a reader who wants the bound builds two transforms, sorts two suffix arrays, and stores two wavelet trees. Nothing about the two structures is shared except the alphabet and the symbol frequencies.

That is the sharpest form of the essay’s claim. The doubling is not an artefact of keeping two objects where one would do; it is that the bound is computed from information the forward index does not contain, and the information is exactly as large as the index.

The case where it is unambiguously the wrong trade #

Two symbols. The bound removes 0.8% of the search tree and costs 17,033 bits.

That is not a marginal call, it is a clear loss, and it is worth having a case like that in a ladder about a technique. A pruning whose value depends on the alphabet has a range over which it is worth its space and a range over which it is not, and the boundary is where the saved operations times the query count crosses the space charge.

On two symbols the saved operations are 45 per query. On twenty-six they are 8,328. A reader with a binary alphabet — a bit string, an indicator sequence, a compressed representation — should not build this, and nothing in the published accounts of the technique says so, because the published accounts were written for a four-symbol alphabet where the answer is comfortably yes.

What the space buys when it is spent on something else #

A fair comparison needs the alternative use of the bits, and there is an obvious one: spend them on a denser suffix-array sampling instead.

The forward index’s sampling rate is the dial the sampling that goes the other way measures. At rate 32 the sampled positions are $n/32$ values of $\lceil\log_2 n\rceil$ bits — about 1,100 bits of the 17,032 here — and halving the rate to 16 doubles that and halves the walk each located occurrence performs.

So 17,033 bits would buy a sampling rate of about one in two, which would make locating essentially free. That is a real alternative and it is worth naming, because a reader with a fixed space budget is choosing between accelerations rather than deciding whether to accelerate.

Which is better depends on the query. A search with a large budget and few occurrences spends its time in the tree, and the pruning wins by a wide margin. A search with a small budget and many occurrences spends its time locating, and the sampling wins. This collection has both dials measured now, on the same index, in the same units — which is the point of building the structures rather than citing them.

What the plate has to show #

Three bars and a caption, and the caption carries the bits.

The bars are in one currency — operations — and the bits are not in it, so putting them on the same axis would require an exchange rate and would be exactly the error the previous ladder is about. Putting them in the caption is a compromise and it is the site’s convention: a number that belongs to the argument and not to the axis goes in the prose.

What must not happen is the bits being left out. A plate showing 72 ranks removing 27,906 extensions is a plate showing a technique that is free, and the technique is not free — it is the most expensive thing on this ladder in the currency the whole structure was chosen for.

The plate this ladder ends on #

Four numbers, and no single one of them is the answer.

The tree removed, the ranks spent, the bits added and the alphabet the whole thing is a function of. A reader with a wide alphabet and many queries should build it; a reader with a binary alphabet should not; a reader in between should measure the share removed on their own data, which is one search with the bound and one without.

That is a weaker recommendation than “use the pruning” and it is the one the measurements support. This collection’s habit is to end on the parameter rather than on the verdict, because the verdict is the reader’s and the parameter is what a measurement can supply.

Stored bits and working set are not the same doubling #

The doubling is real and it is worth asking when the second index is touched, because the answer changes which resource is doubled.

The bound is computed once per pattern, in seventy-two ranks, before the walk starts. After that the walk extends intervals in the forward index and consults an array of $D$ values; it never returns to the reverse structure at all.

So the reverse index is a preprocessing structure, not a query structure. It is read for a few dozen operations per pattern and then idle for however many thousand extensions the walk performs — which means it does not have to be resident while the search runs. It can page from disk, live on a slower tier, or be shared between processes searching the same text, and none of that touches the walk’s cost.

The doubling is in stored bits and not in working set, and the two are different arguments. The index is small usually means it fits in memory, which is what the text that does not have to be kept establishes a self-index for; the 5.7 times the packed text is a storage figure, and the memory figure stays at 2.8 plus whatever the seventy-two ranks touch.

And for a fixed pattern set the reverse index can be discarded entirely. Compute every pattern’s $D$ array once, keep the arrays — a few bytes per pattern — and delete the second structure. That is the case a signature scanner or a read aligner is in, and it turns a permanent doubling into a build-time one.

Which does not make the trade free, and it moves it into the currency this ladder is better at. What remains is bits on disk against operations at query time, rather than memory against memory — and three savings in three currencies is the reason to say which of the two the doubling was in before deciding it is too expensive.

What is being claimed #

The bound costs 72 rank operations and removes 27,906 interval extensions, which is 388 to one and needs no exchange rate to read.

It also costs a second FM-index, 17,033 bits against the forward index’s 17,032, because the bound extends the pattern rightwards and a backward search extends leftwards.

That doubles the structure whose small size was the argument for the search, taking it from 2.8 times the packed text to 5.7.

So the result is a break-even in queries rather than a saving: the fixed cost is space and the variable cost is operations, and the rate between them is how many times the index is searched. A structure built once and searched a million times is a different object from one built once and searched once, and nothing in a bound or a tree count distinguishes them.

And on a binary alphabet it is a clear loss — 0.8% of the tree, for the same doubling. That is the reading this ladder most wants a reader to keep: the technique is excellent, its published accounts are written from a four-symbol world, and the parameter that decides it is one those accounts hold fixed.