The structure that was supposed to halve

This is a short answer to a question that was worth asking, and the reason it gets an essay rather than a sentence is that the sentence is wrong in an instructive way.

The question was recorded like this. A walk over an index with an error budget can be pruned by a lower bound on the errors the rest of the pattern must cost, and computing that bound needs an index of the reversed text. A bound that has to be paid for measured the trade: seventy per cent of the search tree removed, for a second index the same size as the first. The structure whose small size is the whole argument for walking it doubles.

The deferral said: a bidirectional index would let the error bound and the walk share one object. It would. The object holds both transforms.

The measurement #

Over eight thousand characters, a forward index is 35,335 bits and an index of the reversal is 35,335 bits. Together they are 70,670: 8.63 bits a character against 4.31.

The two halves are not approximately the same size. They are the same size, and it is worth saying why, because it is the reason there is no clever asymmetry to exploit. The reversal has the same characters as the text, so the same alphabet and the same frequencies; a wavelet tree shaped by frequency therefore has the same shape and the same total depth. The sampled positions are the same count at the same rate. The transform’s number of runs happens to match too, which is not forced but is unsurprising: a run in one is a repeated context in the other.

Why there is no single-index version #

The temptation is to look for one structure that answers both directions. There is not one, and the reason is structural rather than a matter of effort.

The transform an index is built on stores, for each row of the suffix array, the character preceding that row’s suffix. A rank over that column answers “how many rows beginning with this suffix are preceded by c”, which is exactly what prepending a character needs. There is no column holding the character that follows a row’s suffix — the suffix itself follows it, and the index does not store the suffix.

So a rightward extension is not a harder query against the same structure; it is a query about a different order. Getting it means sorting the same occurrences by what precedes them, which is the suffix array of the reversal, which is the second index.

What the deferral got right, and what it slid over #

The deferral was right that the bound and the walk can share one object, and that sharing is not nothing — it removes a real duplication of work.

Before: the walk holds an index; the bound holds a second, separate index of the reversal; the bound is computed by a search over that second index that has nothing to do with the walk’s own state, and every state the walk explores consults a precomputed array of bound values.

After: one structure, one search state, and the two directions are two methods on it. Nothing is built twice and nothing is computed twice.

What the deferral slid over is that “sharing one object” is a statement about code and the complaint was about bits. The complaint was that the index doubles, and the index still doubles. It doubles inside one object now.

That is the whole finding, and it is worth naming the mistake precisely because it is easy to make: a structure named after the thing it unifies is not thereby a structure that costs less. The name says the two indexes are one thing; the size says they are two indexes.

What the doubling is worth, on its own terms #

Two indexes over eight thousand characters is 70,670 bits, against a packed copy of the text at about 34,000 and a plain suffix array with its text at about 140,000.

So the bidirectional structure sits between the two, and it is still smaller than the naive alternative it replaced. That is worth keeping in view: this strand’s complaint is that a compressed index doubles, not that it has stopped being compressed.

The comparison a reader actually faces is with the unpruned walk, which needs one index at 35,335 bits and explores a tree seventy per cent larger. Doubling the space to cut the tree by seventy per cent is a trade, and whether it is a good one depends entirely on whether the index has to fit somewhere.

The four ways to hold this, side by side #

It helps to lay the options out, because the strand has now built enough of them that the comparison is real rather than notional.

One index, no bound. 35,335 bits. The walk explores its whole tree, which at two errors on four symbols is 830 interval extensions for the pattern measured here.

One index and a stored bound array. Still 35,335 bits of index, plus a bound of one small number per pattern character — negligible — except that computing the bound needs a second index and the second index cannot be thrown away afterwards if patterns keep arriving. So in practice this is the next line.

Two indexes, the walk pruned. 70,670 bits, and roughly thirty per cent of the tree left. This is what a bound that has to be paid for priced.

Two indexes as one bidirectional structure. 70,670 bits, the same bound available, and the pattern consumable in any contiguous order — which takes the tree from 830 extensions to 303 on the same problem.

The last two lines cost the same and the last one does more. That is the only sense in which this structure is a saving, and it is a real one: it is a saving against the previous answer to the same question rather than against one index.

What it does buy, priced #

The second index is now paying for two things rather than one, and that changes the arithmetic even though it does not change the bits.

Before, the second index bought a lower bound and nothing else. Now it buys the bound and the freedom to consume the pattern in any contiguous order, which is what the search that starts in the middle shows is worth a factor of 2.7 on the tree — on top of whatever the bound is worth.

So the honest summary is not “the doubling was not removed”. It is: the doubling was already being paid for one benefit, and it now delivers two. A reader who was already paying it gets the schedules free; a reader who was not is being asked for the same 100% overhead the bound asked for, in exchange for more.

It is worth being careful about what “free” means there. The schedules are free in bits and not in ranks: an interval that grows at both ends measures a bidirectional extension at 16.5 ranks on four symbols against a backward search step’s two, because moving the other interval means counting every smaller symbol’s width.

So the tree shrinks by a factor of 2.7 and each of its nodes costs about eight times as much. In the currency this collection has been counting since the index field opened — ranks — the schedule is close to a wash, and the reason it is still worth having is that the operation which would make an extension cheap is a real operation that real implementations use and this one does not. That is stated on every plate in the strand rather than folded into a ratio.

The sampling, which is the term that could have been shared #

There is one part of an index that in principle need not be duplicated, and it is worth chasing to its end because the answer is not obvious.

An index stores sampled suffix-array positions so that a row can be turned into a text position. The reverse index’s samples are positions in the reversed text, and a position p in a text of length n is n − 1 − p in its reversal — an arithmetic relation, not a lookup.

So could the reverse index do without samples and use the forward index’s? No, and the reason is the row numbering. Converting between the two requires knowing which row of the reverse index corresponds to which row of the forward one, and that map is exactly what neither structure holds. The relation between the two is a relation between positions, and getting from a row to a position is the operation the samples exist to perform.

The reverse index is never asked where anything is, though, which does open a real saving: its samples could be dropped entirely. That is not done here, because it makes the two halves different structures and the strand’s central claim is a comparison of like with like — but it is the one term a real implementation would take, and it is about a sixth of the second index.

A deferral answered by measurement rather than by construction #

This collection’s habit is that a structure named and not built is a structure whose constants are unknown, and the usual outcome is that building it produces a number. Here building it produced a retraction, and that is worth as much.

The sentence on record — that a bidirectional index would stop the index doubling — was written from the shape of the idea rather than from its parts. It is the same kind of error as predicting that a constant-time range minimum would move a crossing “to a handful”, which where a crossing moved to measures at a factor of three. In both cases the reasoning was about which asymptotic quantity changes, and in both cases the thing that mattered was a constant the asymptotics do not mention.

And a correction gets an essay rather than a footnote, because the account of how a number came to be wrong is the transferable part. Here the transferable part is a test: before recording that a structure will save space, ask what it holds, not what it is called.

The general shape, which this collection keeps meeting #

A structure that holds two of something is not made smaller by being given one name, and that sounds too obvious to record until one notices how often the opposite is assumed.

The same reasoning error is available in three places in this collection and has been made in two of them. The candidates a filter cannot avoid records a grid that was expected to be small because it stores no coordinates, and which turned out to be a quarter of the index it accelerates. The structure paid for before the first query records the first version of that same grid at six times its own payload, all of it directory. And this essay records a structure expected to halve an index because it unifies two of them.

In all three the reasoning was about what the structure is and the measurement was about what it holds, and the two came apart by a large factor. The habit that catches it is the one this collection applies to algorithms and had not been applying to structures: report the parts, require them to sum to the total, and compare the total.

What a reader should do with this #

Two questions, and they have different answers.

Does the index have to fit? Then the doubling is the whole story and nothing here removes it. The unpruned walk over one index is the structure to build, and its tree is three times larger. That is a legitimate choice and this strand does not argue against it.

Is the collection queried constantly? Then the doubling was already paid for the bound, and the schedules arrive at no further cost in bits. Build the bidirectional structure, and read a schedule nobody writes down for which schedule, because that decision is worth more than anything else in this strand and is the one nothing in the pseudocode names.

The one thing the measurements here rule out is the middle position — building a bidirectional index in order to save space. It does not, by a factor of exactly two, and the number is not close.

The deferral’s answer is already bracketed, and the band is eight per cent #

The structure named at the end of this essay — a reverse half with counting machinery and no locating machinery — is offered as the obvious next measurement, and its answer can be bounded now from numbers already on this page. It is worth doing, because the bound turns out to be tight enough to decide whether the measurement is worth taking.

The only shareable part is the sampling, at about a sixth of an index. Everything else the reverse half holds — the wavelet tree over its transform, the rank directories under it, the character table — is what counting needs, and counting is exactly what the reverse half is for. So its floor is five sixths of a full index, and the structure’s total is bracketed:

$$1.83 \;\le\; \frac{\text{bidirectional}}{\text{one index}} \;\le\; 2.00.$$

That is 64,781 bits against 70,670 at the sizes measured here — a saving of 8.3% of the structure, or 16.7% of the half it comes out of.

Which settles the recommendation without building anything. The two questions this essay leaves a reader with are does the index have to fit and is the collection queried constantly, and eight per cent moves neither. An index that does not fit at 2.00 does not fit at 1.83; a deployment that has already accepted the doubling for the bound is not going to reconsider over a sixteenth. The one genuinely avoidable term in the doubling is worth building and is not worth deciding on.

That is a useful thing to be able to say about a deferral, and it is the same discipline this collection applies to a break-even: compute the bounds on what a construction could possibly be worth before writing it, because a bound that is cheap to derive can retire a measurement that is expensive to take. Here the derivation is one fraction and it caps the prize at eight per cent.

It also says where the effort on this structure should go instead, and the answer is not in bits at all. The neighbouring strand’s compound walk removes a factor of σ from every interval extension — 13.97 on a twenty-six-symbol alphabet — for a tree ordering that costs a few per cent of one wavelet tree. Set the two side by side: a bounded eight per cent on the space, against a measured factor of fourteen on the operation this structure exists to perform. The structure’s expensive half is its extensions rather than its bits, and this essay’s own accounting is what makes that comparison possible.

So the honest close is a redirection rather than a deferral. Every child at once is where the extension’s cost collapses, and a factor of fourteen, for four per cent puts both of its currencies on one frame — which is the accounting this essay asks for, applied to the term that turns out to be worth it.

What is checked #

Three things, and the first is the one this essay rests on.

The two halves are the same size within two per cent, and the total is exactly twice one index. That is asserted rather than observed, so a change that made one half cheaper — a different wavelet shape on one side, a different sampling rate — would fail rather than quietly turn this essay’s claim into a different claim.

Both halves are complete indexes. Each is built by the same construction the index strand ships and each answers an ordinary backward search on its own text. A structure that shared some machinery between them would be a different structure, and would need a different accounting.

And the structure answers what exhaustive comparison answers, at two budgets, on every scheme. A space claim about a structure that finds the wrong occurrences is not a claim about anything.

The deferral that replaces it #

The one this leaves is sharper than the one it answers.

A structure that walks an index with an error budget wants two things: a way to extend in either direction, and a bound on what the unmatched part of the pattern must cost. Both need the reversal. Neither needs the reversal’s samples, and one of them — the bound — needs only counts rather than positions.

An index whose reverse half holds counting structure and no locating structure is therefore a real object, smaller than 2n and larger than n, and nothing here builds it. It is the shape of what a careful implementation would ship, and pricing it is the obvious next measurement in this strand.