The thread: An index has a size
An index larger than what it indexes
A suffix array over 16,384 characters is 229,376 bits, and it cannot answer a single question without the 81,920 bits of text beside it. Nearly four times the text, to search the text. Every index on this site had been weighed at zero until somebody put one on a scale.
The index that replaces the textA search that runs backwards
Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.
The index that replaces the textThe index that is smaller than the text
The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.
The floorsA floor under a run count
A structure whose size is a function of the number of runs in a transform must give a different bit string to every text with that many runs, so it needs at least the logarithm of how many such texts there are. That count is walked rather than estimated — all four thousand and ninety-six of them — and the representation everybody uses turns out to have five bits of slack.
The data that is not a numberThe filter that feeds the table
A self-index answers exact queries and nothing else. Approximate matching needs a table with twenty thousand columns in it. The pigeonhole joins them — cut the pattern into k+1 pieces and at least one occurs exactly, and the index that cannot answer the question decides where to ask it.
The index that replaces the textThe sampling that goes the other way
An FM-index hands the text back, and the way it does it is to walk from the last character to the first. So thirty-two characters from the end cost thirty-three steps and thirty-two characters from the beginning cost eight thousand one hundred and ninety-two. The repair is a second array the same size as the first, indexed the other way round.
The index that replaces the textThe index that stores the runs
A compressed self-index over thirty-two copies of a text is 30,557 bits, because its size follows an entropy that cannot see a copy. An index that stores the transform as its runs is 11,900 — and at a single copy it is the larger of the two, which is what makes the comparison a claim about repetition rather than about size.
What the machine doesRank is the only thing it does
Constant time and o(n) extra space — a phrase true of a rank directory costing 163% overhead and reading three words, and equally true of one costing 3% and reading eighteen. Both numbers are decided by two integers somebody typed into a header, and the phrase names neither.
What the machine doesSelect is not rank backwards
Rank counts the ones before a position and select finds the position of the k-th one, and only the first has an obvious structure. The constant-time answer costs 1.56 bits per one, is bounded in a unit the machine does not charge for, and on a vector with one bit in fifty it inspects more positions than the binary search it replaced.
The other axisThe text that does not have to be kept
The index reproduces its text character for character, in 1,024 mapping steps and zero reads of anything. That is the whole justification for weighing it against the text rather than beside it — and the price is a dial that moves the structure by 3.3 times and the cost of locating one match by 72.
The index that replaces the textThe sampling that follows the runs
A run-length index over thirty-two copies of one text spends 11,286 bits on its suffix-array sampling and 5,605 on the transform it was built to compress. Sample at the run boundaries instead and the sampling is 10,942 bits that stop moving — two values per run, and a function that fills in everything between them.
One pass, and no roomThe bits that say when
A windowed cardinality estimator holds 4,592 bits and 2,392 of them are clocks. Every summary in this collection has reported its size from the shape of its own structure, and not one of those numbers has ever been asked what the bits were for — so the resource that half of these structures spend most of their state on has been invisible while being counted.
What the machine doesA function with r pieces
Computed at every one of eight thousand positions across four texts, a function defined on the whole suffix array agrees exactly with r−1 anchors and one addition. Anchor it at the successor instead of the predecessor — one character of code — and it disagrees at 506 of 800 positions while still returning plausible numbers.
The index that replaces the textThe occurrence carried through the search
Backward search returns how many and not where, and every index on this site pays for the second question separately. Carrying one occurrence along with the interval costs a lookup on 75% of the steps for a two-character pattern and on 18% of them for a sixteen-character one, and it is what makes a run-boundary sampling usable at all.
The other axisWhat is still proportional to n
An index whose size is a function of the run count still has an n in it, and at thirty-two copies of a text the n is half of it. Everything that stores the transform grew by 45 per cent; the two arrays that answer "where" grew by eighteen times, and neither of them has anything to do with repetition.
The index that replaces the textAn index with z in its size
Over thirty-two copies of one text, an index built on the parse is 8,892 bits, the r-index is 17,047 and the entropy-bounded index is 34,615. Over eight thousand characters of four-symbol text the same three are 7,844, 25,177 and 20,413, and the smallest of the three has changed places twice.
The index that replaces the textThe search that spends a budget
A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.
The index that replaces the textThe collection decides which index is small
Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.
The other axisEvery occurrence at the same price
A regular sampling has one dial and it moves two costs together — 1,495 bits at 63 LF steps an occurrence, 131,088 bits at none. A sampling at the run boundaries sits at 10,244 bits and one predecessor query, which is a point the curve reaches only at 69,649.
The index that replaces the textThe candidates a filter cannot avoid
A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.
The index that replaces the textWhat a ceiling costs in phrases
A cap of sixteen costs one phrase of a hundred and fifty-six and halves the worst chain. A cap of four costs six times the phrases. The curve between them is flat at one end and vertical at the other, and the elbow is where a structure should be built.
The other axisThe structure paid for before the first query
The two grids that make a phrase index's search proportional to its answer are 3,240 bits on an 8,892-bit index — twenty-seven per cent of the whole structure, answering nothing on their own, and 38% of them is rank directory rather than payload — the lower-order term of the published bound, measured.
The index that replaces the textA list of documents is not a list of occurrences
A pattern occurring 790 times in eight documents has an answer of size eight. Reading every occurrence to find out costs 790 array reads; the question a collection has that a text does not is the one its index does not answer.
The other axisThe term that came back
A phrase index is worth building because 8,192 characters parse into 156 phrases. Cap the copy depth at one and the same text parses into 7,351 — ninety per cent of the characters — and the structure is proportional to the text again.
The index that replaces the textAn interval that grows at both ends
A backward search step is two ranks. A bidirectional step is two ranks and the width of the interval for every symbol that sorts before the one being added — 16.5 ranks on four symbols and 138.6 on twenty-six, which is a cost no account of the structure mentions.
The other axisA bound that has to be paid for
The pruning removes seventy per cent of a search tree for seventy-two rank operations. It also needs an FM-index of the reversed text — 17,033 bits against the forward index's 17,032 — which doubles the structure whose small size was the entire argument for walking an index.
The index that replaces the textA block, a class and an offset
Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.
The other axisOne separator, or one for each
A shared separator costs one alphabet symbol and is free. Fifteen distinct ones take the alphabet from twenty-two to thirty-five, which crosses a power of two, so every character of every document costs a sixth bit — 1.2 times the packed collection, to tell the boundaries apart.
The data that is not a numberA corpus that was not generated
Every collection in five strands has been copies of a generated text with a fraction of its characters replaced — three numbers, one dial. Here is one that was not — twelve essays, eight source modules, ten revisions of one file — measured beside the model of it.
The index that replaces the textDocuments that are not the same length
A separator per document costs a whole bit per character — on a generated collection whose alphabet is 21 symbols, where adding a few crosses 32. Real prose has 87 symbols and sits 41 short of the next power of two, so the same separators cost 0.04%.