The half that is never asked where

A bidirectional index is two FM-indexes — one over the text, one over the text reversed — and one interval carried by both.

An interval that grows at both ends is the construction, and the structure that was supposed to halve is the finding that it does not halve anything: two indexes cost exactly 2.00 times one, and what they buy is the order the pattern may be consumed in.

This page is about a smaller question that turns out to have a useful answer. What is the reverse half actually asked to do?

Ranks, and nothing else.

What an extension needs #

The interval is four numbers: the rows of the pattern in the forward index, and the rows of the reversed pattern in the reverse index. Both intervals have the same width at every moment — they are the same occurrences counted twice — and keeping them that way is the whole mechanism.

Extending left by a character c is an ordinary backward-search step in the forward index: two ranks give the new forward rows. But the reverse interval has to move too, and the amount it moves by is the total width of the intervals for every symbol sorting before c — because in the reverse index those extensions sit before this one.

So a left extension asks the forward index for two ranks of c and the forward index for a rank of every smaller symbol. A right extension asks the same of the reverse index. Neither asks for a position.

That is not an oversight in the implementation. It is what a bidirectional search is: the search’s job is to narrow an interval, and the occurrences are read out at the end, once.

Why the reverse rows could not be read anyway #

The reverse half’s rows are positions in a text written backwards, so a row of the reverse index says where a reversed suffix begins in a reversed text — which is a number about a string nobody has.

It could be converted: position p in the reversed text is position n − p − 1 in the original. But the conversion is only useful for the reverse pattern’s occurrences, and those are the same occurrences the forward interval already holds, in the forward index, at the right coordinates.

So there is no query anywhere in a bidirectional search that wants a position out of the reverse half. Not “not needed in this implementation” — not available in a useful form at all.

The five parts, and what each answers #

An FM-index here is five things, and the split is not the one a size formula suggests.

The wavelet tree over the transform — 18,377 bits of the 35,305 at eight thousand characters. This is what answers rank, and rank is what backward search is made of. Rank is the only thing it does is the essay about why a whole index reduces to it.

The rank directories — 5,037 bits. The blocks and superblocks that make a rank constant-time rather than linear.

The C table — 100 bits. One cumulative count per symbol.

Those three answer how many. Between them they support count queries, interval extensions, and the whole of a search that only wants to know whether and how often.

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

The sampled positions — 3,598 bits, the positions themselves, one in every 32.

Those two answer where, and they exist only for that. The sampling that goes the other way is the essay about the second sampling a real index needs for extraction; this is the first one, the one that turns a row into a text position.

What dropping them leaves #

An index without the last two is still an index. It counts, it extends intervals, it supports a backward search to completion, and it refuses to say where anything is.

Built and stripped rather than built without: the object here is a full index whose samples and marks are set to null after construction, so that asking it to locate throws rather than silently returning something. That is the same discipline the chainless document listing uses — an object that still holds the arrays and merely promises not to read them proves nothing.

At one sampled position in 32, the two dropped parts are 11,791 bits of a 35,305-bit index — a third of the reverse half, and 16.7% of the whole structure.

The invariant that makes it safe #

The reason this is safe is not that the reverse half is unimportant. It is that the forward interval is exact, and it is exact because both intervals are maintained in step.

If the reverse half drifted — if an extension moved its start by the wrong amount — the forward interval would move too, because a right extension computes the forward start from the reverse one. A search would then read positions out of a forward interval that was wrong, and every position it reported would be a genuine occurrence of something, just not of the pattern.

That failure has a check. The in-step assertion requires both intervals to have the same width at every step of every search, and the deliberate defect — leaving the other interval where it was — fails it on 39 of 39 substrings while changing no answer at all, because a covering search scheme is redundant enough that another search hands back what one loses.

So the guarantee this page relies on already exists: the forward interval is exact, therefore its rows are the occurrences, therefore the forward half is the only one that needs to locate. What is being dropped is the half nobody reads, and what makes that a fact rather than a hope is a check written for a different reason.

How a locate works, and why it costs two parts #

The two parts that answer “where” are two rather than one for a reason that is worth following, because it is what makes the saving depend on a dial.

A row of the index is a rotation of the text, and the position it starts at is what a locate has to produce. Storing all of them is a suffix array — n⌈log₂ n⌉ bits, which is the thing the whole compressed-index family exists to avoid. So an FM-index stores a sample: every 32nd position, say, indexed by row.

The trouble is that a query lands on an arbitrary row, and an arbitrary row is not sampled. The walk that fixes it is the index’s own mechanism: step backwards one character at a time — each step is a rank, which the counting parts support — until a sampled row is reached, then add the number of steps to the stored position. A search that runs backwards is the machinery, used here for a different purpose.

That walk needs to know, at each row, whether this one is sampled. A bit vector of n bits answers it in one rank, and the sampled positions live in a compact array indexed by the rank. Hence two parts: marks, one bit a row, and positions, ⌈log₂ n⌉ bits per kept sample.

The two behave completely differently under the sampling rate. The positions are n/s × ⌈log₂ n⌉ bits and shrink as s grows; the marks are n bits whatever s is. At one in 4 the positions are the larger of the two; at one in 128 the marks are seven times larger. That asymmetry is the reason the saving on this page has a floor, and it is the subject of the page after next.

What it is not #

Three things, because “a third of one half is free” invites more than it says.

It is not a smaller interval or a faster search. The nodes explored are identical, the ranks performed are identical, the rows found are identical. Nothing about the search changes; a search cannot tell which structure it is running on.

It is not free of the sampling parameter. The saving is 16.7% at one sampled position in 32 and 30.5% at one in 4, because the locating apparatus is most of the index when positions are kept densely. A sixth of what, exactly is the page about that, and the short version is that any single number quoted here is a number about a dial setting.

And it is not a new structure. A careful implementation of a bidirectional index ships this, because the person writing it notices that the reverse half’s locate is never called. What is new here is the measurement: how much it is worth, at what sampling rate, and what the bits can be spent on instead.

Why the halves are the same size to begin with #

One number underneath all of this deserves stating, because it is the thing that makes a third of a half worth chasing.

The two halves are the same size. Not approximately: 35,335 bits forward and 35,335 reverse in the measurement that established it, exactly 2.00 times one index. The reverse index is an FM-index over the reversed text, and reversing a text does not change its length, its alphabet, or its symbol frequencies — so the wavelet tree has the same shape, the directories the same size, and the sampling the same count.

What does change is the transform. The Burrows–Wheeler transform of a reversed text is not the reverse of the transform, and its run count is generally different — which matters for a run-length compressed index and not for the plain one measured here.

So the honest starting point for this strand is: a bidirectional index is exactly twice an index, one half of it is asked only for ranks, and a third of that half is machinery for a question it is never asked. That is 16.7% of the whole thing at a common setting, and it is the largest single piece of a bidirectional index that can be removed without changing a single answer.

Which searches this covers #

Worth checking rather than assuming, because “the reverse half is never asked where” is a claim about every search a bidirectional index runs.

A search scheme is a list of searches, each consuming the pattern’s pieces in some order with an error bound per piece. The search that starts in the middle is the essay about why the orders differ and what they buy. Some searches begin in the middle and grow both ways; some go left to right; some right to left.

Every one of them maintains both intervals, because the pieces are consumed in an order that requires both directions. Every one of them ends with a forward interval whose rows are the occurrences. And every one of them reads those rows exactly once, at the end, out of the forward half.

So the claim holds over the whole family, and the measurement below it holds for any of them. What would break it is a search that reported occurrences of the reversed pattern as a separate answer — which is not a query anybody asks, since the occurrences of a reversed pattern in a reversed text are the occurrences of the pattern in the text.

What comes next #

Three pages, and they are one measurement each.

An index that cannot locate builds it and prices the parts: what a counting-only half is made of, and what the whole structure costs when one half is that.

A sixth of what, exactly sweeps the sampling rate, because the number in the title is a number about a setting — and finds that the saving does not fall to nothing at the sparse end, for a reason worth knowing.

The saving, spent is the useful one. The bits removed from the half that never locates can be given to the half that does, and at equal total size the asymmetric index locates five times faster.

What a locate actually costs #

The parts that answer “where” are worth pricing in operations as well as in bits, because the two decide different things.

A row that is not sampled is walked backwards — one LF step per character, each step a rank on the wavelet tree — until a sampled row is reached. At one sampled position in 32 that is 15 steps an occurrence on average, and the measurement agrees with the prediction of half the gap to within a step at four settings of the dial.

So a query returning a thousand occurrences performs fifteen thousand ranks after the search has finished, which is usually more than the search itself did. A sixth of what, exactly sweeps that, and the saving, spent is what happens when the reverse half’s bits are moved to the forward half’s sampling: the same total size, and three steps an occurrence instead of fifteen.

Where this sits #

Four pages. This one is the observation; an index that cannot locate builds the structure and prices its parts; a sixth of what, exactly sweeps the parameter that every price depends on; the saving, spent is the recommendation.

The two locating parts trade places at $s = \lceil\log_2 n\rceil$ #

The asymmetry between marks and positions is described above as the reason the saving has a floor, and the crossing point is a single expression worth writing down.

The marks are $n$ bits whatever the rate. The positions are $(n/s)\lceil\log_2 n\rceil$ bits. They are equal when

$$s \;=\; \lceil\log_2 n\rceil,$$

which at eight thousand characters is thirteen. Below one sampled position in thirteen the positions are the larger part; above it the marks are.

The measurements land on that exactly. At one in 32 the ratio of marks to positions is 8,193 against 3,598, or 2.28, against a predicted $32/13 = 2.46$. At one in 16 it is 8,193 against 7,196, or 1.14, against 1.23. At one in 4 it is 8,193 against 28,686, or 0.29, against 0.31. Three settings, and the simple ratio $s/\lceil\log_2 n\rceil$ describes all of them.

That gives both ends of the saving without sweeping anything.

The sparse end. As the sampling thins, the positions vanish and the removable apparatus tends to the marks alone — 8,193 bits against an index that has shrunk to 31,707, which is 12.9% of the whole structure. The saving does not fall to nothing at the sparse end because $n$ bits of marks do not depend on the rate, and that is the floor the next page finds by measurement.

The dense end. As the sampling thickens, the positions dominate everything and the locating apparatus approaches the whole of the reverse half — so the saving approaches 50%. At one in 4 it is already 36,879 bits of a 120,786-bit structure, which is the 30.5% quoted above, recovered here from the parts.

So the number in this strand’s title is one point on a curve running from 12.9% to nearly 50%, and the curve’s shape is a hyperbola plus a constant with the crossover at thirteen. Quoting 16.7% without the rate is quoting a number about $s = 32$; quoting the range is quoting the structure.

The crossover also says which part to attack. Below $s = 13$ the positions are the target and a smaller position encoding — storing gaps rather than absolute values — is where the bits are. Above it the marks are the target, and the marks are a bit vector with one bit in $s$ set, which is exactly the case a sparse representation is for. Two different optimisations, and which one is worth doing is decided by a comparison between the sampling rate and the width of a position.

Which is a bit for every bit’s finding arriving as a design rule rather than an observation: the vector that says which costs $n$ bits regardless of how few it marks, so at any sparse rate the bookkeeping outweighs what it is bookkeeping for. A sixth of what, exactly sweeps the curve this expression describes, and the floor it reports is the marks refusing to shrink.

What this does not generalise to #

One caution, because “half a structure is never asked half its questions” sounds like it should apply widely and mostly does not.

The reason it applies here is specific: the two halves of a bidirectional index are the same index over two texts, and one of the two texts is an artefact of the construction. Nobody wants positions in a reversed text, so the half over it is structurally exempt from answering “where”.

Contrast a two-level index, or a partitioned one, where both parts index real text and both are asked everything. Contrast a cache in front of a structure, where the front is asked everything and the back is asked what the front misses. Neither has a component with an ability nobody will ever call.

So the finding is not “structures have unused halves”. It is that a construction which duplicates for a mechanical reason — here, so that a pattern can be extended at either end — produces a duplicate whose usefulness is narrower than its interface, and that the narrowing is worth measuring rather than assuming.