An index larger than what it indexes

Building a suffix array is a good trick and this collection made a lot of it: every suffix of a text sorted without examining a single character, a search answered in ninety-one character comparisons where a scan costs 1,472, and the whole thing paying for itself at six queries.

Every number in that account is about time. Not one of them is about what the structure weighs, and the structure weighs a great deal.

Sixteen thousand three hundred and eighty-four characters of English-like text, at five bits a character because the alphabet has twenty-one symbols in it, is 81,920 bits. The suffix array over it is sixteen thousand three hundred and eighty-four integers, each of which must address a position in the text, so fourteen bits each: 229,376 bits. And the array on its own answers nothing, because a binary search over it compares the pattern against a suffix, and a suffix is a window onto a text the array does not contain.

Three hundred and eleven thousand two hundred and ninety-six bits, all in, to index eighty-one thousand nine hundred and twenty. Three and eight-tenths times the text, and two and a third times the file it came from.

Weighed how #

Everything on this page is bits computed from the shape of a structure, not bytes measured off a serialisation.

That is a deliberate choice and it is the same one this collection makes when it counts a summary’s state or a table’s cells. A serialised size is a fact about a file format, a language runtime and whichever library did the writing; it is not reproducible across any two of those, and it is not the quantity anybody designing a structure is trying to control. An array of $n$ values each needing $\lceil \log_2 n\rceil$ bits is $n\lceil \log_2 n\rceil$ bits, whether the language that holds it uses thirty-two-bit integers or sixty-four, and that is the number that decides whether the design is possible.

So: a counter array is its length times the bits one counter needs. A bit vector is its bits plus its directory. A table of character offsets is the alphabet size times the length times the bits an offset needs. Nothing is rounded up to a machine word, nothing is compressed by a library, and every number here can be recomputed with a pencil from the structure’s description.

The text is not an implementation detail #

It is worth being precise about why the text has to be there, because “the text is needed as well” sounds like a footnote and is not one.

A search over a suffix array is a binary search over the sorted suffixes. At each step it must decide whether the pattern is before or after the suffix beginning at position $\mathrm{SA}[i]$ — and the array holds $\mathrm{SA}[i]$, which is a number. To compare, it has to read characters at that position. On the sixteen-thousand-character text above a six-character pattern costs ninety-one character comparisons, which is ninety-one reads of a text the structure does not hold.

This collection now enforces that rather than mentioning it. A structure is handed its text while it is being built and the text is taken away before any query runs; every structure declares in advance whether it needs one; and a structure that declared it does not and then reads a character is stopped at the read, with a distinct error saying so.

The declaration alone would be worthless. The cheapest way to make a search fast is to keep the text around for a verification step, and nothing in the occurrences returned would ever reveal it — the answers would be correct, the counts would be correct, and the size claim would be false by however many bits the text takes. That is exactly the class of failure that survives every check a person thinks to write, which is why the check here is behavioural rather than declarative.

Measured under it: the suffix array reads 91 characters during a query, and the compressed index in the same plate reads zero.

The obvious way to make it faster is enormous #

Before the good answer, the instructive bad one.

There is a way to search a text that needs no character comparisons at all and answers in time proportional to the pattern alone: build, for every symbol of the alphabet, a running count of how many times that symbol occurs before each position. Then any question of the form how many $c$ before position $i$ is one array read.

It works, it is the fastest thing here, and it is $\sigma \cdot n \cdot \lceil \log_2 n\rceil$ bits.

It earns its place in this collection for the same reason a naive scan does: it is the structure a first implementation reaches for, and without it the clever structure looks like an implementation detail rather than the thing that makes the idea possible at all.

The index grows faster than the text #

A suffix array is often described as taking “$n$ integers”, which sounds linear. It is $n \lceil \log_2 n \rceil$ bits, and the logarithm is not decoration.

Two bits a character per fourfold increase, exactly as the formula says, and no sign of stopping. On a text of a billion characters it is thirty-five bits per character of text — seven times the text, to index the text.

The comparison in the last two rows of the table is worth pausing on. The suffix array’s slope is steeper than the text’s, so the ratio between index and text gets worse without limit. There is no size at which the overhead stops mattering. That is a different situation from a structure with a constant factor, and it is invisible in a description that says “$n$ integers”.

What the alphabet does to it #

Widening the alphabet makes the text cheaper and the index no cheaper at all, so the ratio gets worse.

The counter table moves in the opposite direction: fewer symbols means fewer arrays, so it falls from sixty-six times the text to thirty-eight — and it falls by less than the text shrank, which is the same effect from the other side. It is still the largest thing on the plate by two orders of magnitude.

What is not counted here, and why #

Three things are outside the number on every plate above, and naming them is part of the measurement.

Construction space. Building a suffix array by prefix doubling needs rank arrays alongside the array itself, and at the moment of peak use that is several times the finished structure. Every index has a build-time footprint larger than its resting one, they differ between construction algorithms by large factors, and none of it survives into the structure that gets kept. What is weighed here is what a query needs, which is what has to be resident.

The queries’ own working space. A binary search needs a few integers; a backward search needs a few more. Both are constant and neither is interesting.

Any decoration. No structure here carries an auxiliary array it does not need for the queries in this collection. A suffix array in practice is usually accompanied by its longest-common-prefix array, which is another $n\lceil\log_2 n\rceil$ bits and would nearly double the first bar — and it is not counted, because the searches measured here do not use it. A plate that included it would be weighing a structure nobody on this page built.

The third of those is the one worth being careful about in both directions. Leaving it out understates what a deployed suffix array costs; putting it in would overstate what the search measured here needs. The honest position is to weigh exactly what answers the question being asked and to say which question that is, which is what the captions do.

Two break-evens, and only one of them arrives #

The case for an index is usually made as a break-even: preprocessing costs something once, each query saves something, and after enough queries the saving has covered the cost.

That argument is about time and it is sound. On the text above, a scan costs 1,472 character comparisons a query and the array costs 91, so the build pays for itself after a handful of searches, and every search after that is free profit.

The same argument about space does not exist. There is no number of queries after which the index stops taking 229,376 bits. The cost is paid once and kept forever, it grows superlinearly, and the only thing that can change it is a different structure.

What a better answer would have to do #

Reading the plate at the top from the right, the requirements assemble themselves.

It has to hold no text, which means it must be able to reproduce any part of the text on demand — otherwise the text has to be kept and the whole comparison is a fiction.

It has to hold no positions, or almost none, since $n\lceil\log_2 n\rceil$ bits of positions is the suffix array’s whole problem.

And it still has to find the occurrences, which the positions were there for.

Those three sound incompatible, and the structure that satisfies all three exists. It is built out of a transform that emits nothing and compresses nothing, searched by a procedure that runs the pattern backwards and never compares two characters, and it is smaller than the text it indexes on any text that has any structure at all.

The unit is the bit, and that is a decision too #

One more thing to settle before the field can proceed, because it decides how every comparison here reads.

An index could be measured in objects — states, nodes, entries — and the suffix automaton essay does exactly that, because its bound is a theorem about states. That is the right unit when the question is whether a structure is within its own theoretical bound, and it is the wrong unit the moment two different kinds of structure are compared: an automaton state and a counter array entry are not the same thing, and a table with one column per symbol has no objects in it at all.

Bits are the only unit all of them share. A state that stores three transitions over an alphabet of twenty-one is some number of bits; a counter that must reach sixteen thousand is fifteen; a bit vector is its bits. Once everything is in bits, structures that have nothing in common structurally can be put on one axis honestly, and the axis is the one a machine actually has a fixed amount of.

The price of that choice is that a bit count depends on details a state count does not: how a transition is stored, whether an entry is addressed absolutely or relatively, what the alphabet is. So every plate here names the text and the alphabet it was measured on, in the same slot where the summary plates name their state and the table plates name their model. A bit count without those is a number belonging to a structure nobody described.

An index contains no information #

There is a way of stating the plate at the top that makes the factor of a hundred and forty-seven less surprising and the whole field’s project sharper, and it takes one observation.

Every structure here is a function of the text. The suffix array is determined by the text; so is the counter table; so is the transform and everything built on it. Hand two people the same text and they compute the same index, with no choices to make and nothing to record. So the pair (text, index) carries exactly as much information as the text alone, and every bit of the index is redundant by construction.

That is not a criticism and it is not an argument that the bits are wasted. It settles what kind of quantity an index’s size is. It is not a cost of representing anything; it is a cost of arranging something. The 229,376 bits of a suffix array say nothing the 81,920 bits of text do not already say, and they are there so that a question can be answered by looking rather than by computing.

Read the plate again with that in mind and the ordering means something new. The counter table is sixty-six times the text in pure redundancy, and it buys a rank in one array read. The suffix array is 2.8 times the text in redundancy, and it buys a search in a logarithmic number of comparisons — but it cannot stand alone, so its bar carries the text as well. The compressed index is under the text and needs no text beside it, which means it has crossed a line the other two have not: it is not the text plus an arrangement, it is an arrangement that is also the text.

That is the entire ambition of a self-index stated in one sentence, and it explains why the phrase is worth a category of its own rather than being one more compressed structure. The interesting question stops being how much overhead does the index add and becomes how far below the text can a structure go while still answering, and the second question has a floor made of the text’s entropy rather than of anything about indexing.

What the redundancy is buying #

If none of an index’s bits carry information, the honest way to price them is against what they save, and the saving is in a different currency every time.

The counter table’s bits buy one read instead of a walk. The suffix array’s buy a logarithm instead of a scan — 91 character comparisons against 1,472. The compressed index’s buy the same thing at a different exchange rate, in ranks rather than comparisons, and buy it while occupying less than the text.

None of those exchange rates is comparable with the others, which is why this field weighs structures in bits and counts queries in each structure’s own primitive rather than trying to produce a single figure of merit. A ratio of bits to operations saved would be a number in units of bits per comparison-avoided, and there is no such quantity.

What can be said, and is worth saying because it is the shape of every decision in this field: an index’s size is a choice about how much redundancy to keep, and its speed is what the redundancy was arranged into. A structure that keeps none is the text itself, answering by scanning. A structure that keeps sixty-six times the text answers by looking once. Everything anybody builds is between those two, and the plate at the top of this page is four points on that line with their prices attached.

The measurement this field is for #

One sentence, and it is the reason the field exists rather than a summary of the essay.

Four structures on this page answer the same question about the same text and return the same occurrences, and they differ in size by a factor of a hundred and forty-seven. Nothing in the description of any of them — “a sorted array of positions”, “a running count per symbol”, “a transform with a rank structure” — carries that number, and none of the descriptions is wrong. The number is a property of the structure that only appears when somebody weighs it, and until this field opened nobody here had.

It is worth saying what follows from that, because it is not “indexes are bad”. Every structure on the plate is a reasonable answer to a question somebody has: the counter table is what to build when the alphabet is tiny and the queries are relentless, the suffix array is what to build when the text has to be there anyway and the code has to be simple. What does not survive is the habit of choosing between them on the strength of a description. Two of these descriptions differ by four words and the structures they describe differ by two orders of magnitude, and the only way to know that is to put both on a scale.