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

Toehold — where it appears

One occurrence of the pattern, carried along by a backward search rather than found afterwards. It costs a lookup on the steps where the character being searched for is not already at the end of the interval, and it is what a run-boundary sampling needs before it can enumerate anything.

Named by 3 essays across 2 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 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

Named alongside it

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

FM-indexIndex sizeLocateMeasurementR-indexRun boundary samplingRun-lengthSamplingSelf-indexBurrows-wheeler transformPhi functionSpace overhead

All concepts