R-index — where it appears
Named by 16 essays across 5 fields — each of them below, with the objects they name alongside it.
The 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.
A 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 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 phrases a text copies from itself
Four thousand characters of English-like text hold 604 phrases in the greedy parse and 1,219 runs in the transform. Thirty-two copies of one text hold 156 phrases and 233 runs. Two measures of repetition, neither of them an entropy, and they do not agree about which text is the more repetitive.
An 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 occurrences that cross a boundary
One pattern, thirty-two copies of a text, thirty-two occurrences. The search finds one of them and produces the other thirty-one by arithmetic, and the count it finds is the same one at two copies, at eight and at thirty-two — the searching does not grow when the answer does.
The 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.
Every 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 character that costs a chain
The index over thirty-two copies is 8,892 bits and does not grow. Producing one character of the text it indexes costs 17.89 phrase-follows on average and 38 in the worst case, against 2.38 and 7 at one copy — the size stopped growing and the price of reading it did not.
A sampling that costs more than the array
On four-symbol text the transform has 0.75 runs a character, so a sampling of two suffix-array values per run is one and a half values per position — 271,565 bits against the 131,088 that keeping every value costs. The structure built to remove a term proportional to the text is twice the thing it replaced.
The measure that cannot see the alphabet
Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.
Sparse on average, dense where it gathers
The r-index keeps one suffix-array value for every run of its transform and prices the set as Elias–Fano: on 32 exact copies of 2,048 characters that is 666 values among 65,537 positions at 9.04 bits a value, as though they were spread evenly. They are not — 663 sit in one copy. Cut into chunks of 32 values, each held by whichever of a bitmap, its own Elias–Fano or a run is cheapest, the same set costs 4.48 bits a value, under the 8.05 that any representation of an arbitrary set of that size must spend on some set. At a divergence of 0.0005 the saving is a fifth, and from one character in five hundred it is nothing but the select directory, which the chunks replace with reading. On the scattered marks of an ordinary index the partition saves only that directory too.
Cuts that follow the gathering
Cutting an r-index's run-start values into chunks of a fixed count left chunk edges inside the places the values gather. Choosing the cuts as a shortest path through the sorted values was predicted to save a further tenth on exact copies by cutting once at each edge of the gathering. It cuts there, and saves more than a quarter: two chunks, one of them a bitmap of 664 values that a select must scan from its start. Capped at the chunk's old size, the optimum keeps the reads and saves 9% on exact copies and 15% at a divergence of 0.0005. On moderately drifted copies the uncapped optimum is smaller and cheap to read at once.
A select that starts near its answer
The cheapest partition of an r-index's run-start values held exact copies in two chunks, one a bitmap of 664 values that every select scanned from its start: 1,065 bits read a select. Capping the chunks bought the reads back by giving up the saving. A select sample every 64 values inside each chunk, its bits charged in the same shortest path, was predicted to bring the uncapped optimum under 150 bits a select for under 3.5 bits a value. It reads 111 for 3.45, where the cap that reads as little costs 3.68. And the middle divergences, predicted to be untouched because their chunks were short, lose two fifths of their reads to the same samples.
A sample that has to be found
A select sample every 64 values inside the cheapest partition of an r-index's run-start values cut a select's reads from 1,065 bits to 111 on exact copies. Samples by count bound how many values a select passes, not how many bits it reads, so samples every 128 bits of a chunk's vector were predicted to read a third less on the sparse, drifted sets at the same cost. They bound the scan as promised, but a rank sample does not say which sample a select needs, and finding it by binary search costs a select up to a third of what it reads. The two kinds of sample end up on one frontier, and the rank samples' advantage is that they come in finer steps.
A second level that pays in one band
A select on a chunked bit vector can be helped two ways: a select sample every t values says where to start but not how far to scan, and a rank sample every s bits bounds the scan but must be searched for. A directory with both — select samples that name a rank block, rank samples that bound the scan — was predicted to reach under 70 bits read a select for under 3.6 bits a value on an r-index's run starts over exact copies, a point neither kind reaches. It reaches 62 bits read for 3.76 bits a value, which neither kind reaches, and costs 3.73 within 70 bits where the better single kind costs 3.93; but under 3.6 bits a value it reads 84. The select sample names a block two rank samples away, not one. Across eight sets the second level saves more than a twentieth of a bit a value on three, and only between about 65 and 100 bits read a select: outside that band either single kind is as good.
Named alongside it
The objects these essays reach for when they reach for this one.
Index sizeMeasurementSelf-indexLocateRepetitionRun-lengthFM-indexTrade offBurrows-wheeler transformCompressibilityLempel ziv parsePhrase