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

Directory — where it appears

The precomputed block and superblock counts that turn a rank on a bit vector into a lookup and a short scan. It is the part of a succinct structure that is not the payload, and on every structure measured here it is several times larger than the payload it supports.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

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

Named alongside it

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

Bit vectorRankSelectAlphabetCompound operationConstant timeCounterDensityIndex sizeMachineMachine wordMeasurement

All concepts