The text that does not have to be kept

Every size on the last three pages rests on a claim that has not yet been made good: that the text does not have to be kept.

If it does, the comparison collapses. An index of 36,804 bits beside a text of 81,920 is 118,724 bits, which is more than the plain index and not far off the suffix array, and the word “compressed” would be describing an accounting convenience.

So the claim has to be demonstrated rather than argued, and the demonstration is short. Hand the structure a text, take the text away, and ask it for the text back.

1,024 characters out, matching the original at every position, in 1,024 mapping steps and zero reads of anything.

How the text comes back #

Row 0 of the sorted rotations is the one beginning with the sentinel — the character that marks the end of the text and sorts before everything. Its rotation is therefore the sentinel followed by the whole text, so the last column of that row holds the text’s final character.

Take it. Then apply the LF mapping — one rank query and one addition — to step to the row whose rotation begins one character earlier, and take that row’s last character. Repeat.

The text arrives backwards and is reversed at the end. There is no cleverness in it: this is the inverse of the transform, which the compression field needed anyway, because a transform without an inverse is a claim rather than a transform. What is new here is that it is being used as evidence about size rather than as evidence about correctness.

The gate requires the output to equal the input at every character, and requires the text-read counter to be zero while it happens. Both together are what makes “the text does not have to be kept” a measurement.

Three questions, three prices #

An index gets asked three different things and they cost three different amounts. Almost every description of a self-index quotes the first price and calls it the cost of a search.

How many. Backward search: two rank queries a pattern character, independent of the text and of the number of matches. Twelve for a six-character pattern.

Where. Each row of the found interval has to be turned into a position, and a row is not a position. The only route is to walk LF backwards until reaching a row whose position was sampled — stored explicitly — and then add the number of steps walked.

What is there. Extraction, as above: one LF step per character produced.

The second is where the dial is, and it is the interesting one because the dial moves the structure’s size.

The sampling rate #

Keep every position and locating is free and the samples cost $n\lceil\log_2 n\rceil$ bits, which is a suffix array with extra steps. Keep one position in $s$ and the samples cost $\frac{n}{s}\lceil\log_2 n\rceil$, and every occurrence costs up to $s-1$ LF steps to reach one.

Measured over eight thousand characters, a six-character pattern with 66 occurrences:

Three things in that table.

The index shrinks by 3.3 times and the samples by 126. The samples are 70% of the structure at one-in-one and 1.8% at one-in-128; everything else is fixed. So the dial is almost entirely a dial on the sample array, and the returns flatten hard: going from 32 to 128 saves 5% of the index and quadruples the cost of a location.

The last column is the one to look at. Rank queries rise from 118 to 37,950 — a factor of 322 — because every LF step is itself an access and a rank on the wavelet tree. Counting the occurrences cost about forty-four bit-vector ranks. Locating them at one-in-128 cost thirty-seven thousand nine hundred. The location is 860 times the search.

And the count did not move. Every row of that table returns the same 66 occurrences and every one of them found the interval at the same price. The dial has no effect whatever on the question the structure is famous for answering quickly.

How a sample is stored, and what that costs #

“Keep one position in sixty-four” is two structures rather than one, and the second is easy to forget.

There is the array of kept positions, which is $\lceil n/s \rceil$ entries of $\lceil\log_2 n\rceil$ bits — the obvious cost, and the one the table above tracks.

And there is the problem of knowing, at a row, whether that row is sampled and if so which entry of the array holds it. That needs a bit vector over the rows, one bit each, with a one at the sampled rows — and then the entry’s index is a rank on it.

That vector is $n$ bits whatever the sampling rate. At one-in-64 over sixteen thousand characters the array of positions is 3,855 bits and the marks vector is 16,385 — four times as much, for a structure holding 256 ones.

Unless the marks are stored in the compressed form the payload uses, in which case a vector with 256 ones in 16,385 positions is mostly all-zero blocks, and it costs 1,441 bits. From 16.2% of the plain index to 3.9% of the compressed one.

That is the class-and-offset encoding paying for itself in a second place, and it is a nice illustration of why the two halves of this structure belong together: a sparse bit vector is the case the encoding handles best, and a sampling scheme produces one by construction.

What a walk actually costs #

The mean number of LF steps per located occurrence should be about $(s-1)/2$ — an occurrence sits at some offset from the nearest sample below it, and if the offsets were uniform the average would be half the gap.

Measured against that expectation:

Close at the tight end and 14% over at the loose one. The reason is not mysterious and is worth stating rather than smoothing: there are sixty-six occurrences, so the residues of their positions modulo the sampling gap are a sample of size sixty-six, and at a gap of 128 that is a sample of sixty-six from a hundred and twenty-eight buckets. The excess is sampling noise about a quantity this measurement is not large enough to pin down.

Which is the honest version of the row rather than a defect in it. The table is a measurement of this pattern in this text, the expectation is what a uniform model predicts, and the two agree to within what sixty-six draws can show. A plate quoting 72.3 as a property of the structure would be quoting a property of one query.

And the worst case is neither number: an occurrence sitting one character after a sample costs $s - 1$ steps, so at one-in-128 a single location can cost 127. The mean is the interesting quantity for a query returning many results and the worst is the interesting one for a query returning one.

Why this is the field’s version of an old picture #

A curve of one resource against another, convex, with no point on it dominating another, is a shape this collection has drawn before.

The difference is where the dial sits. A sort’s position on its frontier is decided by which algorithm was chosen; a self-index’s position on this one is decided by an integer in a configuration file, and it can be changed without changing a line of the search. That is unusual and worth naming: a structure with a continuous, cheap, post-hoc space-time dial is a rare thing, and it is the reason these indexes are deployed at wildly different sizes for the same data.

What the split is actually for #

A search that reports 40,000 results and shows ten of them is doing exactly what the table above describes, and it is not a caching trick.

The count comes from the interval’s width, at a price that does not depend on 40,000. The ten shown come from ten locations, at a price that does. Reporting the count is cheap and reporting the results is not, and the ratio between them grows with the sampling rate.

The same accounting on the compressed representation is where the asymmetry becomes obvious. Compression acts on the parts that hold characters — the transform, the marks vector, the rank directories — and it has nothing to act on in an array of positions, which is a list of arbitrary integers with no structure to exploit. So the compressible parts shrink and the sample array does not move at all, which changes what fraction of the index it is without changing what it costs.

The other end of the dial #

At one-in-one the structure is a suffix array with a different search. Its samples are $n\lceil\log_2 n\rceil$ bits — exactly a suffix array — plus the transform and its directories, so it is strictly larger than a suffix array and answers the same questions. Nobody would build it, and it is on the plate because a trade-off drawn without its degenerate ends is a trade-off drawn without its scale.

At the far end there is a real limit rather than a diminishing return. Keep no samples and locating becomes impossible: the LF walk has nothing to stop at, and it will circle the whole text and return to where it started. That is a refusal in this collection’s machinery rather than an infinite loop — an index with an empty sample array raises when asked to locate, and the gate requires it to.

What extraction here does and does not do #

Two limitations, both stated rather than papered over.

Extraction runs from the end. The walk starts at the sentinel’s row, so producing the substring at position $p$ costs $n - p$ LF steps to reach it. Producing the whole text is $n$ steps and is what the gate checks; producing a hundred characters from the middle of a large text is not a hundred steps.

The repair is a second sampling — position to row rather than row to position — so that a walk can start anywhere. It costs the same bits as the first sampling, it is what a deployed index keeps, and it is not built here. So every size on these pages is the size of a structure that counts, locates and reproduces the whole text, and a structure with constant-time random access to the middle of it would be larger by one more sample array.

Nothing here is a duration. LF steps and rank queries are counted; how long one takes on a machine is not measured anywhere in this collection, and the two ends of the table above differ by a factor in steps that need not be the factor in seconds. A location walk is a chain of dependent memory accesses with no locality at all, which is the case a processor handles worst, and the counting field’s oldest finding is that a count and a duration rank things differently.

Two things are called sampling one row in s #

The phrase covers two policies that produce the same size, the same interface and the same code shape, and only one of them bounds anything.

Sample by text position. Keep the row of every text position that is a multiple of $s$. Then every position is within $s$ of a sampled one, so a walk from any row reaches a sample in at most $s-1$ steps. That is a worst case, it holds on every text and every pattern, and it is what makes the expectation of $(s-1)/2$ a statement about a distribution rather than a hope.

Sample by row. Keep the position of every $s$-th row of the sorted rotations. The array is the same length, the marks vector has the same number of ones, and the structure weighs exactly the same. But the rows are sorted by suffix and the positions they hold are scattered arbitrarily through the text, so nothing relates a row’s distance from the nearest sampled row to its distance along the LF walk. The walk from an unsampled row can be arbitrarily long — up to the whole text — and no parameter bounds it.

The measurements above are of the first policy, which is why the expected column matches the measured one to within sampling noise at every rate. An implementation of the second would produce means in the same neighbourhood on ordinary text, because scattered samples are still samples and the average gap is still about $s$, and would have a tail nothing in the table would reveal.

That is the shape of defect this collection keeps finding. Two implementations, one description, identical sizes, identical answers, and a guarantee present in one and absent in the other — with the difference visible only in a worst case that a benchmark on ordinary text will not produce. The check that separates them is not on the mean but on the maximum: the longest walk over all occurrences of all patterns must be under $s$, and an implementation sampling rows fails it on the first text that is not uniform.

The array is more compressible than it looks #

The marks vector compresses because it is sparse, and the section above uses that. The array of positions is described as the part that cannot, and one line of arithmetic recovers a large share of it.

Under sampling by position the stored values are not arbitrary. They are exactly the multiples of $s$ — the entry says which multiple, and there are only $n/s$ of them. So an entry needs $\lceil \log_2 (n/s) \rceil$ bits and not $\lceil \log_2 n \rceil$, and the difference is precisely $\log_2 s$ bits per entry.

Over eight thousand characters at one sample in thirty-two that is eight bits an entry rather than thirteen — a 38% saving on the array, for a shift at read time. At one in 128 it is six bits against thirteen, better than half. The saving grows exactly as the sampling gets sparser, which is the opposite direction from the array’s own size and means the two effects partly cancel: the array is already small where the per-entry saving is largest.

Nothing is given up. The value recovered is the same position, the multiplication is one shift when $s$ is a power of two, and the structure answers identically. It is a plain encoding improvement of the kind that is available whenever a stored set is known to lie on a lattice, and the reason it is easy to miss here is that the array’s type is a text position — so the obvious width to give it is the width a text position needs.

The general form is worth carrying, because this collection has now met it in three structures. A stored value’s width should be the logarithm of how many values it can take, not the logarithm of the range its type covers, and the two differ whenever the values are constrained. A timestamp modulo twice the window rather than a global clock is the same observation; a run’s start stored as a high part and a low part is the same observation; and a sampled position stored as its index among sampled positions is this one.

The sentence the whole field rests on #

The text does not have to be kept, and this is the page that shows it.

Everything else — the sizes, the ratios, the comparison against the entropy, the claim that an index can be smaller than what it indexes — is downstream of a structure being able to hand back what it was given. Without extraction, all of those numbers are about a structure that has to sit next to a copy of the text, and the honest comparison would be against the suffix array’s bar with its text included rather than against the text alone.

With it, the index is the whole cost. Which is what makes it worth asking how few bits that cost can be.

There is one more thing the demonstration settles, and it is the reason to run it on every build rather than once. An index that quietly kept a reference to its text would pass every other check on these pages: the counts would be right, the locations would be right, the sizes reported would be whatever the size function said. Reproducing the text with the text withheld is the only one of these measurements that could not be faked by a structure that had not thrown the text away, and it is therefore the one the rest of the field’s arithmetic hangs from.