Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Bit vector — where it appears

A sequence of bits with a directory over it, answering rank in constant time at an overhead that ranges from 3% to 163% according to two chosen block lengths. Its overhead is decided by two chosen block lengths, and reporting the payload without the directory is how a compressed structure is made to look smaller than it is.

Named by 17 essays across 6 fields — each of them below, with the objects they name alongside it.

a text that repeats itselfH0 4.01 · H3 0.236.291.48an order-1 sourceH0 3.00 · H3 0.895.151.67English-likeH0 3.89 · H3 0.976.162.25four symbols, uniformH0 2.00 · H3 1.994.102.59eight symbols, uniformH0 3.00 · H3 2.835.143.65bits per character of textupper bar: plain bit vectors · lower bar: compressed16,384 characters each · sample rate 64sigma 21, 8, 21, 4, 8

The 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.

indexes · Index balanced, bits49,2616.01 b/chHuffman-shaped, bits39,0614.77 b/chranks per access5.003.95entropy = 3.90 bitsEnglish-like, sigma = 22 · upper bar balanced, lower Huffman-shapedH0 = 3.90 bits/symbol

Rank 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.

machine · Index 1,00010,00010³bits of select supportpositions inspected, worst casebinary search, no extra bits: 510L=8L=256L=8L=256one position per L onesdense and sparse6,554 ones in 65,536 positions · sub-blocks of 8worst cases, every k

Select 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.

machine · Index phrase table5,148 bitsboundary orders3,744 bitsintersection grid1,696 bitspropagation grid1,544 bitsz = 156 · ⌈log₂ z⌉ = 8 levels16,384 characters · 12,132 bitsgrids 26.7% · 20.8 bits a point

The 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.

space · Grid 2·0·1·20101206·7·3·25·012012201012102rowsdocumentfirstpattern " was t" · 30 occurrences · 7 documentsA filled row is the first of its document. Reporting one costs a range minimum;reading every row costs one visit per occurrence.English-like · 8 documents30 rows · 7 documents

A 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.

indexes · Document rank among the boundaries, sorted by the text before themsorted by the text after0 in the rectanglepattern "ss is un"split after 40 end with the left half0 begin with the rightEnglish-like · 2 copies of 512z = 156 · 0 crossing

A rectangle over a permutation

Two orderings of one set of boundaries are two permutations, so a phrase index's intersection is a rectangle over a permutation grid — the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.

structures · Grid 00.2500.5000.750101234567891011level of the wavelet treebits a bitthe parse's grida uniform permutation3,612 points · 12 levels0.997 bits a bit

A bit for every bit

A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.

space · Grid 024601234567891011level of the wavelet treemean runthe parse's grida uniform permutationbreak-even3,612 points · 12 levels1.23x chance

The runs a permutation does not leave

A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.

structures · Grid candidates, filtering4,355candidates, grid33rank and select, grid2,471occurrences32one query · same collection · same answer16,384 characters · 32 occurrencescandidates 132x · operations 1.76x

The operations a candidate count leaves out

The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.

wrong · Grid 0102030255075100125one sampled position in every …of both halves saved, per cent"about a sixth"the marks alone: 14.0%8,192 characters16.7% at one in 32

A sixth of what, exactly

The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.

wrong · Distance level 0 · left335 keptlevel 1 · right+207 smallerlevel 2 · left61 keptlevel 3 · right+33 smallerlevel 4 · left8 keptpositions still in play, and the half the code leaves behindsmaller symbols before position 400: 240rank of "m": 8 — from the same 5 operationsσ 21 · code 010105 ranks, not 105

Every child at once

A bidirectional extension counts the occurrences of every symbol smaller than the one being added, and this collection did it with one rank per symbol — 139.7 operations an extension on a twenty-six-letter alphabet. One walk down the tree gives the same number.

indexes · Symbol level 0 · left585 keptlevel 1 · right+351 smallerlevel 2 · right+113 smallerlevel 3 · right+39 smallerlevel 4 · right+40 smallerpositions still in play, and the half the code leaves behindsmaller symbols before position 700: 543rank of "s": 42 — from the same 5 operationsσ 21 · code 011115 ranks, not 105

The count that was already there

A bit vector's rank of one is the position minus its rank of zero. Every walk down a wavelet tree computes one of them at every level, and this collection asked for the other separately for years.

machine · Symbol acdefghijklmnopqrstuvwyzroot24 of 26 symbols present54 ranks · 51 nodes

A node costs two ranks

The left child's interval is the position minus the right child's. A descent that calls rank on both children returns exactly the same symbols at twice the cost, and nothing about the answer can see it.

machine · Symbol 05e+31e+41.5e+40246bits kept in the low partbits⌊log₂(n/m)⌋ = 2low partshigh vector2,049 marks in 16,385 positions1 bits between the two roundings

The flat bottom of a shallow curve

The low width is chosen as the floor of log of the universe over the count. Rounding it up instead costs one bit on five thousand, because the total is m·w plus n over two to the w and the minimum is where those two are equal.

bounds · Space 4,097 rows · one in 32 marked3.1% of the rows

The array that says where is twice the samples

An index keeps one suffix-array value in every thirty-two, and a bit vector over all n rows saying which. The vector is sixteen thousand bits and the values it points at are seven thousand — the index of the samples is twice the samples.

space · Space plain bit vector19,475compressed blocks4,55723.4%Elias–Fano3,90520.1%positions, priced as Elias–Fano3,59118.4%16,385 rows · one in 32 markedElias-Fano at 20.1%

A position split in two

Write each sorted position as a high part and a low part. Store the low parts packed and the high parts as a bit vector in which the k-th one sits at position (p >> w) + k. A select on that vector and a low read recover any position.

structures · Space 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4

Where the sparse representation loses

At every row marked, Elias–Fano costs twice the plain vector. The crossing is at one row in four, which is a sampling rate a real index uses — so the choice between the two is a choice, not an improvement.

wrong · Space

Named alongside it

The objects these essays reach for when they reach for this one.

Index sizeWavelet treeMeasurementSelf-indexRankTrade offGridPermutationRank querySpace overheadOutput-sensitiveSample marks

All concepts