The sampling that goes the other way

The claim that makes a self-index self-indexing is that it can hand the text back. Ask for characters 100 to 131 and it produces them, having stored no text.

Ask for them from an index over 8,192 characters of English and it performs 8,092 steps. Ask for the last thirty-two characters and it performs 33.

Reading thirty-two characters from the front of the text costs the whole text. The asymmetry has no reason to exist, is not a property of the transform, and is not mentioned in any statement of what a self-index does.

Why extraction runs backwards at all #

The whole of an FM-index is the LF mapping: from the row of the rotation beginning at text position $p$, one operation gives the row of the rotation beginning at $p - 1$. Backwards, one character at a time, and there is no forward equivalent that costs one operation.

So extraction starts at a row it knows and walks left. The only row it knows for certain is row 0 — the rotation beginning with the sentinel, whose last column holds the final character of the text — and from there the walk reaches position $p$ after $n - p$ steps.

The index already has one sampling. locate needs to turn a row into a text position, so one row in every $s$ keeps its position, and a row that is not sampled walks back until it finds one that is. That sampling is the dial the field measured, and at $s = 32$ it is 3,598 bits of the index’s 52,712.

It cannot help here, because it is indexed by row. Extraction knows a position and wants a row, and there is no way to ask an array indexed by rows a question about positions.

The second sampling is the same array read the other way #

Keep, for one text position in every $s$, the row of the rotation beginning there.

That is the inverse suffix array, sampled. It has the same number of entries as the first sampling, each entry is the same width, and it costs the same number of bits:

With it, extracting $[i, j)$ starts at the first sampled position at or after $j$, jumps straight to its row, and walks back to $i$. The overshoot is at most one sampling interval, so:

$$\text{steps} \le (j - i) + s$$

Measured, the worst case over twelve positions spread across the text is 62 steps against a bound of 64, and the best is 32. Flat, everywhere, at 6.4% of the index’s size.

It is a second structure, not an optimisation of the first. That is the sentence worth carrying, and the arithmetic above is what makes it one: nothing is shared, nothing is derived, and the index that can both locate and extract is the index that stores both arrays. The figure of 52,712 bits this field has been quoting for a compressed self-index over 8,192 characters is the size of one that can locate and cannot extract from the middle.

The overshoot, and where the sampling rate goes #

Both samplings have the same dial and it does opposite things to the two operations, which is worth putting side by side because implementations set one number for both.

Symmetric, and it looks as though one number is right for both. It is not, and the reason is that the two operations are charged differently by the thing above them.

A locate walk is paid once per occurrence. A pattern with 66 occurrences pays it 66 times, and the field measured that locating costs 860 times what counting does — so the sampling rate is the difference between a query that returns instantly and one that does not.

An extraction’s overshoot is paid once per extraction, and it sits beside a cost of $(j-i)$ that the caller chose. A snippet of two hundred characters at $s = 64$ pays a 32% overhead; the same snippet at $s = 256$ pays 128%. So the extract side wants the rate tuned to the typical extraction length, which is a property of the application, and the locate side wants it tuned to the typical number of occurrences, which is a property of the corpus.

Nothing forces the two rates to be equal. An index sampling positions at one in 16 and rows at one in 128 is a perfectly ordinary thing to want, and it is what an implementation serving snippets from a search result should have. Whether any of them does is a question about implementations.

Against the obvious alternative, which is keeping the text #

There is a third option and it has to be priced, because it is what every index that is not self-indexing does: keep a copy of the text beside the structure and extract by reading it.

Over 8,192 characters of English on twenty-one symbols, a packed copy is 40,960 bits. Extraction is then free — a memory read per character, no LF steps at all — and the whole index-plus-text is 93,672 bits.

The second sampling is 3,598 bits and makes extraction cost $(j-i)+s$ LF steps.

$$\frac{40{,}960}{3{,}598} = 11.4$$

Eleven times cheaper for an operation that is no longer free but is bounded, and that ratio is the entire argument for building a self-index rather than an index. It is also the ratio that decides whether the second sampling is worth having at all: an application that extracts constantly and has memory to spare should keep the text, and one that extracts occasionally over a corpus that does not fit should not.

The comparison also says something about the earlier essays in this field. The index that is smaller than the text is smaller by a factor that these 3,598 bits barely dent — they are 6.4% of a structure that is already 29% under the packed text — so adding random access does not change the field’s headline claim. It changes the operation set the claim is about, which is a different kind of change and one that was not being tracked.

What the walk actually costs #

An LF step is not a unit. It is an access to the transform to find the character, and a rank of that character up to the row — which in a wavelet tree is as many bit-vector ranks as the character’s code is long, and on English text that is about four.

So the flat line above is flat in LF steps and, in the unit a machine charges, is about four times the number of bit-vector ranks. The falling line is 8,192 LF steps at the front of the text, which is some thirty thousand rank operations to read thirty-two characters.

That multiplier does not change the shape of anything above — both curves are multiplied by the same number — but it changes what the numbers mean, and it is why the plate says LF steps rather than operations.

Why a sampling is where an index keeps its n #

Both samplings share a property that becomes the subject of another essay in this collection: they are the only parts of a self-index proportional to the length of the text rather than to its content.

Every other part compresses. The transform goes into a wavelet tree of bit vectors whose size follows the text’s entropy; the rank directories are a fixed fraction of those vectors; the C table is one entry per symbol. The samples are $n/s$ entries of $\lceil \log_2 n \rceil$ bits, and nothing about the text makes them smaller — two texts of the same length sample identically whether one of them is a thousand copies of the other.

At $s = 32$ over ordinary English that is 6.8% of the structure and easy to overlook. Over a collection that repeats itself it is most of the structure, because everything else has shrunk and the samples have not. The repair there is to sample at the boundaries of the transform’s runs rather than at regular intervals, which makes the sampling proportional to the same quantity the rest of the index is proportional to — and it is a different construction from either array here.

So the two arrays in this essay are the last regularly-spaced thing in a structure that is otherwise entirely content-shaped, and that is worth noticing before the next field pulls on it.

The defect this admits, and the check for it #

The natural way to write the extraction loop is to start at the anchor and emit everything down to $i$. It produces a substring of the wrong length from the wrong place, and it produces one every time — an off-by-$s$, where $s$ is the sampling interval and the error is therefore invisible whenever the requested range happens to end on a sample.

The rejection carried with this machinery asks for characters 101 to 133 at $s = 32$. The anchor is position 160, so the loop that emits from the anchor returns 59 characters where 32 were asked for. A length check catches that one; a range ending exactly at 128 would produce 32 characters from the wrong offset and no length check would catch anything.

Which is why the check compares against the text rather than against a length. Every extraction in the sweep above is compared character for character with the substring it was asked for, at twelve positions across the text, on every build — the same standard the field applies to handing the whole text back, applied to handing part of it back.

The three operations, and what each one’s parameter is #

The field now has three operations over the same structure, and the useful thing about having all three is that their costs are decided by three different numbers.

The middle row is the one that surprised this field when it was measured: locating costs 860 times what counting does on a six-character pattern with 66 occurrences, because the per-occurrence walk is paid per occurrence and the count is not paid at all.

The bottom row has the opposite shape. Its overshoot is paid once however long the extraction, so the relative overhead falls as the snippet lengthens, and an application extracting whole documents pays almost nothing for the sampling rate while one extracting single words pays double.

Which is why a search engine’s behaviour is what it is. The result count arrives immediately because counting is cheap and independent of how many results there are. The first ten results arrive next because ten locates is ten walks. The snippets arrive with them because each is one extraction of a couple of hundred characters, which is a couple of hundred LF steps plus an overshoot nobody notices. Three operations over one structure, three costs, three parameters — and the middle one is the reason the tenth page of results is not free.

The same pairs, indexed twice #

The two arrays come to the same number of bits, and that is not a coincidence worth passing over. They hold the same information.

Sample the text positions that are multiples of $s$. Each one has a row, so the sampling is a set of $n/s$ pairs $(\text{row}, \text{position})$. Store that set sorted by row and it answers locate: given a row, is it sampled, and if so where in the text is it. Store the identical set sorted by position and it answers extract: given a text position, which row begins there. One set of pairs, two orders, and neither order can answer the other’s question.

So the second array is not new data. It is the same permutation read in the opposite direction, and the reason it cannot be derived on demand is that inverting a permutation without storing the inverse means searching for the entry that maps to what is wanted — which is a scan of $n/s$ entries, turning a constant-time lookup into a linear one.

That is a shape this site has already met one field over, and meeting it twice in two unrelated structures is what makes it worth naming. Rank and select are inverse questions about one bit vector — how many ones before here, and where is the $k$-th one — and the structure answering one of them cannot answer the other, so an implementation wanting both builds both and pays twice. Locate and extract are inverse questions about one permutation, with the same consequence and the same remedy.

A structure indexed by one thing does not answer questions asked in another, and the fact that the underlying information is identical changes nothing about the cost. That sentence covers both cases and it covers a great many others: a directory sorted by name does not find a file by size, a hash table does not enumerate in order, an index over rows says nothing about positions. Every one of them is repaired the same way and none of them is repaired for free.

There is one asymmetry between the two examples and it favours this one. Rank and select over a bit vector genuinely need two differently-shaped structures, with different constructions and different costs. Here the two arrays are the same array with a different subscript, so the second one requires no new code, no new parameters and no new analysis — which is a large part of why its absence from descriptions of the FM-index is so easy to miss. There was never anything difficult to describe.

What the two rates should actually be #

The two operations are charged by different quantities, so the rule for setting each rate can be written down and neither rule mentions the other.

Extraction. The overshoot is at most $s_{\text{pos}}$ steps beside a genuine cost of $L$, the length being read. So the overhead is $s_{\text{pos}}/L$ and holding it under a tenth means $s_{\text{pos}} \le L/10$. For search-result snippets of a couple of hundred characters that is a sampling rate of about one in twenty; for an application extracting whole documents it is one in several hundred, and the array shrinks accordingly.

Location. The walk is $s_{\text{row}}/2$ steps on average and it is paid per occurrence, against a count that costs about two ranks per pattern character and is paid once. So the ratio between locating and counting is roughly $o\,s_{\text{row}}$ against $m$, and holding it under some factor $k$ means $s_{\text{row}} \lesssim km/o$ — a rate that has to fall as the pattern gets more occurrences.

The second rule is the uncomfortable one. On the six-character pattern with 66 occurrences this field measured, keeping locate within ten times the cost of count would need a sampling interval of about three, which is an array a tenth of the text’s length and a structure no longer worth calling compressed. At the interval actually used the measured ratio is 860, which is what the arithmetic predicts to within the accuracy the arithmetic deserves.

So the two rates are set by unrelated quantities and one of them cannot be satisfied. Extraction’s rule is easy to meet because $L$ is chosen by the caller and is usually large. Location’s rule is not, because $o$ is a property of the corpus and the pattern, and a common pattern has thousands of occurrences whatever anybody sets. That is the real reason locate is the expensive operation in this family — not the sampling rate, which is a parameter, but the fact that the cost is per answer while the parameter is per structure.

What this does not fix #

The direction is still backwards. The second sampling makes the start of a walk cheap and does not make the walk forwards. Extracting a long range still costs one step per character, and there is no self-index in which it does not.

Nothing is faster; a bound was added. Reading the last thirty-two characters cost 33 steps before and costs 33 now. What changed is that the cost stopped depending on where in the text the characters are, and a bound that holds everywhere is the whole product.

The bits are real. 3,598 of them, 6.4% of this index, and they buy an operation the index could already perform. An index that never extracts from the middle — one answering only “how many occurrences” and “where are they” — should not have them, and the field’s earlier size measurements are correct for that index.

And the rate is still the caller’s problem. The sampling interval is one number chosen once for the whole index, and the overshoot it produces is a property of that number against the length somebody asks for. Halving the interval halves the guaranteed overshoot and doubles the array; the two plates below turn that sentence into two measurements rather than an assertion.

What none of those settings changes is the shape of the term. Both samplings hold one value per sampled position and neither is compressible, so both are proportional to $n$ over the interval however the interval is set — and the only quantity that moves with the size of the text is what share of the index they are.