Generator

Four ways to index 16,384 characters, weighed

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Four ways to index 16,384 characters, weighedEach bar is what the structure retains, computed from its own shape rather than from a serialisation, on English-like of 16,384 characters. The dashed rule is the packed text at 81,920 bits. All four return the same occurrences for the same pattern; they differ in size by 147 times. One of them cannot answer at all unless the text is kept beside it, and its bar includes that text.suffix array + text311,29619.00 b/chcounter array per symbol5,407,710330.06 b/chFM-index, plain100,9476.16 b/chFM-index, compressed36,8042.25 b/chthe packed textone bar shaded darker needs the text · English-likesigma 21, sample 64

Four ways to index 16,384 characters, weighed

Each bar is what the structure retains, computed from its own shape rather than from a serialisation, on English-like of 16,384 characters. The dashed rule is the packed text at 81,920 bits. All four return the same occurrences for the same pattern; they differ in size by 147 times. One of them cannot answer at all unless the text is kept beside it, and its bar includes that text.

Drawn at 700 × 204, wide on the page. Everything above is what index-size returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

14 essays call index-size. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

suffix array + text311,29619.00 b/chcounter array per symbol5,407,710330.06 b/chFM-index, plain100,9476.16 b/chFM-index, compressed36,8042.25 b/chthe packed textone bar shaded darker needs the text · English-likesigma 21, sample 64 The index that replaces the text

An index larger than what it indexes

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 replaces the text

The index that is smaller than the text

1101001,00010010³position in the textLF stepsspan + sample = 64row sampling onlywith the secondsampling8,192 characters · sample one in 32 · span 32second sampling 3,598 bits The index that replaces the text

The sampling that goes the other way

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 What the machine does

Rank is the only thing it does

100,000110bits held by the whole indexLF steps per located occurrence1 in 11 in 21 in 41 in 81 in 161 in 321 in 641 in 128one point per sampling rate · 66 occurrences located each timeEnglish-like The other axis

The text that does not have to be kept

sampled positions3,855grows with nsample marks2,056grows with nrun starts2,016grows with rrun lengths per symbol1,885grows with rrun heads1,563grows with rC table525grows with r11,900 bits in total16,384 characters · r = 224 · sample one in 6450% is the sampling The other axis

What is still proportional to n

10,000110sampling, bitssteps per occurrence1 in 21 in 41 in 81 in 161 in 321 in 641 in 128r-indexEnglish-like · 16 copies · r = 233pattern " time " The other axis

Every occurrence at the same price

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 The index that replaces the text

A list of documents is not a list of occurrences

ranks to compute D72extensions removed27,906extensions remaining12,051one search · k = 3 · 4,000 charactersand one more index: 17,033 bits4,000 characters · m = 16388 extensions a rank The other axis

A bound that has to be paid for

10⁴10⁵10⁶characters in the collectionshuffled ÷ real, phraseswhat the order is wortha million characters of prose · phrases per characterx1.37 over the sweep What is taught wrongly

The half of a fall that is the logarithm

the whole table60,00060,000r · 0rkcounting filter24,84315,369r · 0rkseed filter17,7452,415r · 1,377rkindex walk00r · 177,046rkn = 3,000 · m = 20 · q = 4cells drawn · r = characters read, rk = index rankscells computed6 occurrences What is taught wrongly

Three savings in three currencies

forward · wavelet tree18,377forward · rank directories5,037forward · C table100forward · sample marks8,193forward · sampled positions3,598reverse · wavelet tree18,377reverse · rank directories5,037reverse · C table100reverse · sample marks8,193droppedreverse · sampled positions3,598dropped8,192 characters · sampling every 3216.7% of both halves The other axis

An index that cannot locate

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 What is taught wrongly

A sixth of what, exactly

both halves, one in 3215.0 steps100.0% the sizeforward sampled one in 3215.0 steps83.3% the sizeforward sampled one in 167.0 steps88.4% the sizeforward sampled one in 83.0 steps98.5% the sizeforward sampled one in 41.7 steps118.8% the size8,192 characters · 6 occurrences5.0x faster, 98.5% the size What the libraries do

The saving, spent

The library, page 2 of 5 — where index-size sits