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

Run boundary sampling — where it appears

Keeping the suffix-array value at the first and last row of every run in the transform, rather than one value in every s text positions. It is 2r values with no marking vector and no rate to choose, and it is enough to locate every occurrence only because a function with r pieces fills in everything between the samples.

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

sampled positions6,99041%phi predecessor3,95223%run starts2,09712%run lengths per symbol1,97012%run heads1,5389%C table5003%English-like · n = 16,385 · r = 233the sampling is the two shaded rowsone unit = one bit17,047 bits · 1.04 bits/char

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.

indexes · Repeat text position iphi(i)anchor: a run start25 of thema text that repeats itself · 4 copies of 32r = 26 · pieces 24

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.

machine · Index patterns of 225%60 selectspatterns of 441%94 selectspatterns of 863%118 selectspatterns of 1682%117 selectsEnglish-like · 8 copies of 512share of steps needing no lookup40 patterns a row

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.

indexes · Index 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 "

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.

space · Repeat English-like, 32 copies0.05x0.017 runs/charEnglish-like, 8 copies0.12x0.045 runs/chara text that repeats itself0.08x0.029 runs/charEnglish-like0.80x0.292 runs/charfour symbols, uniform2.07x0.753 runs/charthe whole suffix arraysampling bits, run boundaries / every valuen = 8,192

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.

wrong · Repeat

Named alongside it

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

FM-indexMeasurementR-indexRun-lengthSelf-indexBurrows-wheeler transformIndex sizeLocateSamplingPhi functionSpace overheadToehold

All concepts