The array that says where is twice the samples

An FM-index answers how many with a backward search and where with a sampling. The sampling is two arrays and the accounting for them is usually written as one.

The sampled positions: one suffix-array value in every s, kept because a locate walks a row backwards until it reaches a sampled one and then reads the answer. That is n/s values of ⌈log₂ n⌉ bits each, and it shrinks exactly as s grows.

The marks: a bit vector over all n rows with a one at each sampled row, so that a locate can ask is this row sampled in one rank. That is n bits, whatever s is.

At sixteen thousand three hundred and eighty-four characters and one sampled position in thirty-two, the values are 7,695 bits and the marks are 16,385.

The array saying where the samples are is twice the samples.

Why nobody notices #

The locating cost is written, in every account of this structure, as (n/s) log n bits. That is the values. The marks are inside the “+ o(n)” that follows, along with the rank directories and the C table.

o(n) is an asymptotic statement and n bits is not o(n). The marks are a term proportional to n with a constant of one, and they are being carried in a notation whose whole purpose is to say that such terms have been accounted for.

The reason the omission survives is that it is invisible at the sampling rates asymptotics are written about. As s → ∞ the values vanish and the marks do not, so the locating apparatus tends to n bits rather than to zero — but nobody writes a bound about s → ∞, because a locate then costs n steps.

At the rates a real index uses, one in sixteen to one in a hundred and twenty-eight, the marks are between one and nine times the values.

The ratio is worth writing as a formula because it makes the crossing explicit. The values cost (n/s)⌈log₂ n⌉ and the marks cost n, so the marks dominate when s > ⌈log₂ n⌉. At sixteen thousand characters that is s > 15.

So the crossing is at a sampling rate of about one in fifteen, and every rate a real index uses is above it. A structure sampling one row in four is in the regime where the values dominate; one sampling one row in thirty-two or more is in the regime where the marks do.

That the crossing is at log n rather than at some tuned constant is a pleasant fact and it means the answer does not change much with the collection’s size: doubling n moves the crossing by one.

What the picture shows #

The marked rows are the rows whose suffix-array value is a multiple of s. In the text those positions are perfectly regular — every thirty-second character — and in the suffix array they are scattered, because the transform sorts by context and a position’s context has nothing to do with its index.

That scattering is why the picture above has no structure in it, and it is the reason two of the three representations this strand compares behave the way they do. A representation exploiting runs has almost nothing to work with; one exploiting sparsity has everything.

It also means the marks cannot be derived. A structure that knew the sampling rate could compute which text positions are sampled and could not compute which rows they are, because that is the suffix array — the thing being sampled to avoid storing.

There is one structure in the scattering that is worth naming because it bounds what any representation can do. The marked rows are not a random subset of the rows: they are the rows whose suffix-array value is a multiple of s, and the suffix array is a permutation, so the marks are the image of an arithmetic progression under that permutation.

A permutation of a structured set is not a random set in the information-theoretic sense — it is one particular subset out of C(n, m), determined by the text. But nothing about it is computable without the suffix array, so no representation can exploit the structure without storing the thing being avoided.

That is why the strand treats the marks as an arbitrary sparse set. It is not one, and it is one for every purpose available here.

The two parts against the dial #

Sweeping the sampling rate separates them completely.

At one in four: values 61,455 bits, marks 16,385. The values dominate by four to one, and the whole locating apparatus is 49.1% of the index.

At one in thirty-two: values 7,695, marks 16,385. The marks dominate by two to one. Apparatus 23.0% of the index.

At one in a hundred and twenty-eight: values 1,935, marks 16,385. Marks dominate by eight and a half to one. Apparatus 18.5%.

The apparatus’s share falls from 49.1% to 18.5% and then stops falling, because everything left is the marks and the marks do not move.

The floor every curve flattens onto #

That flattening is not local to this plate. It is the reason several results in this field have a shape nobody explains.

The half that is never asked where measured what dropping a bidirectional index’s reverse locating apparatus is worth, and reported the saving falling from 31.2% at one in four to 13.5% at one in two hundred and fifty-six — and flattening. The essay named the reason correctly: the marks are n bits however rarely a row is kept, and that is the floor the curve flattens onto.

A sixth of what, exactly made the same observation from the reporting side: a saving of 16.7% at one rate is 14.0% at another and 30.5% at a third, and half the apparatus does not shrink with the rate at all.

Both essays identified the floor and neither removed it, because removing it means representing a bit vector with n/s ones in fewer than n bits — which is a different structure and is the subject of this strand.

What the marks are for #

Before replacing them it is worth being exact about what they do, because they do two things and only one is obvious.

A locate walks a row backwards by LF steps until it reaches a sampled row. At each step it asks is this row sampled — one at on the mark vector.

When it arrives, it needs to know which sample: the kth one, so that it can index into the values array. That is rank1 on the mark vector.

So the marks support two operations, a membership test and a rank, and a replacement has to support both. A sorted array of positions supports both — the first by a search and the second by the same search — and a bit vector supports both in constant time.

That is the trade the strand is about, and it is not the trade a reader would guess. The obvious replacement for a sparse bit vector is a list of positions, and a list of positions is slower in a way that the size accounting does not show. A price with no structure under it is where that gap is measured.

The arithmetic of what could be saved #

A bit vector with m ones in n positions carries log₂ C(n, m) bits of information, which for m ≪ n is about m log₂(n/m) + m log₂ e.

At n = 16,384 and m = 512 — one row in thirty-two — that is 512 × 5 + 512 × 1.44 = 3,297 bits.

The plain vector spends 16,385 plus its directory, so it is spending about five times the information the set contains.

That is the whole opportunity: five-fold, at this rate, and larger as the sampling thins. Whether a structure can reach it while still answering both operations in something like constant time is what Elias–Fano is, and a position split in two is the construction.

What the whole index looks like at the rate everybody quotes #

It is worth putting the five parts side by side at one in thirty-two, because the ordering is not what an account of the structure implies.

The wavelet tree’s payload — the transform itself, which is the information — is 66,724 bits. The rank directories over it are 13,626. The sample marks are 16,385. The sampled positions are 7,695. The C table is 290.

The marks are the third-largest part of the structure and larger than the thing they index. They are also the only part whose size does not depend on the text at all: change the collection, change the alphabet, change the entropy, and the marks are still n bits.

That invariance is the tell. Every other term in the structure is a function of something about the data, and this one is a function of the data’s length and nothing else — which is what a dense encoding of a sparse set looks like from the accounting.

Why this term and not another #

There are several n-sized terms in a self-index and it is fair to ask why this one is worth a strand.

The wavelet tree is n·H₀ and is the index’s payload — it holds the transform, which is the information. Reducing it is compression and is what the rest of the field is about.

The rank directories are o(n) with a small constant and are genuinely small: about 6% of the vectors they index.

The C table is σ log n, which is nothing.

The marks are n bits holding n/s bits of information. They are the only n-sized term in the structure that is pure redundancy — not a compressed representation of something, not a directory over something, but a dense encoding of a sparse set.

That is what makes them the obvious thing to attack and the odd thing to have survived. Every other part of this structure has had its representation examined; this one was inherited from the first description and kept.

What replacing them cannot do #

The strand’s limit is worth setting before its results, because a five-fold saving on a fifth of a structure is not a five-fold saving.

At one in thirty-two the marks are 15.6% of the whole index. Reducing them to a fifth saves 12.5% of the index.

At one in a hundred and twenty-eight they are 16.6% and the saving is 15.0%.

At one in four they are 10.3% and the saving is under one per cent, because at that rate the sampled positions dominate and shrinking the marks barely moves the total.

So the strand’s headline is a saving between nothing and fifteen per cent of a self-index, depending entirely on the sampling rate — which is the same dial every other quantity in this neighbourhood depends on, and the reason a sixth of what, exactly exists.

The one place the marks are not there #

There is a variant of this structure where the problem does not arise, and it is worth naming because it says what the marks are really for.

An index that samples by text position rather than by row — keeping SA[i] for every row i that is a multiple of s — needs no marks at all: whether a row is sampled is i % s == 0, which is arithmetic. The values are then n/s entries and there is no vector.

That variant answers a different question. It supports extracting a substring at a known text position, because it can find a starting row quickly; it does not support locating, because a locate arrives at an arbitrary row and needs to know whether that row is sampled.

So the marks are the price of sampling by value rather than by index, and sampling by value is what makes a locate’s walk bounded by s. An index doing both keeps two samplings and two sets of machinery, which is what a real implementation ships and which this collection has not built.

The sampling that goes the other way is where the two directions were first separated here, and the marks belong entirely to one of them.

What it does to the other results #

The more interesting consequence is not the direct saving but what it does to the shape of the earlier curves.

Remove the flat term and the half-index saving no longer flattens. Measured: with plain marks it falls by 2.31 across the dial and levels at 13.5%; with sparse marks it falls by 17.6 and reaches 1.8%.

That is a change in the conclusion rather than in a number. The earlier result was “dropping the reverse half’s locating apparatus is worth about a sixth, and does not go below an eighth however sparse the sampling”. The corrected one is “it is worth about a tenth at ordinary rates and almost nothing at sparse ones, because most of what was being dropped was one badly represented array”.

The floor was the marks is that retraction in full, and it is the strand’s largest result — larger than the saving that produced it.

What a locate actually spends #

The size accounting above says nothing about time, and the two are entangled here in a way worth setting out before the strand’s later essays lean on it.

A locate walks a row backwards until it reaches a sampled one. The expected number of steps is s/2 and the worst case is s − 1, so the sampling rate is a time-space dial and not merely a space one: at one in four a locate is two LF steps and at one in a hundred and twenty-eight it is sixty-four.

Each step costs a mark lookup — at on the vector — plus an LF step, which is a rank and an access on the wavelet tree. The wavelet tree’s part dominates: a rank on a Huffman-shaped tree over twenty-one symbols is about 4.5 bit-vector ranks, against the mark vector’s one.

So the marks are about a fifth of a locate’s operation count and a sixth of the index’s bits, which is a coincidence and a useful one: any replacement that keeps the mark lookup at roughly constant cost will not move a locate’s time much, and one that makes it a search will.

Every occurrence at the same price is where a locate’s per-occurrence cost was pinned down here, and its numbers are the baseline the strand’s replacements have to not damage.

The general shape #

Two things generalise and both are about accounting rather than about bit vectors.

A term inside an o(n) is not necessarily o(n). The notation is a promise about a limit and the marks are proportional to n with a constant of one. Anything carried in that notation without being named is a term nobody has looked at, and a structure whose account has one is a structure with a place to look.

A curve that flattens is a curve with a constant term in it, and the constant is where the next result is. Both earlier essays in this neighbourhood drew a flattening curve and both named the reason correctly. Neither treated the flat part as the subject, because a plate showing a quantity going to a limit reads as a quantity that has been understood.

The instruction is short: when a sweep flattens, ask what the asymptote is made of, and price it.

There is a third thing, and it is the one that made this strand possible rather than merely worthwhile. The floor was named in the prose of two earlier essays and drawn on their plates. What was missing was not the observation but the next question — the observation was treated as an explanation of the curve’s shape rather than as a description of a term that could be attacked.

An explanation and a target look identical on the page. The difference is whether anybody asks what the term costs to remove, and in this case the answer turned out to be a structure that has existed since 1974.