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

Trade — where it appears

Two quantities that move in opposite directions under one parameter, drawn together rather than one at a time. Reporting either alone turns a decision into a result: bits against operations, size against a guarantee, a phrase count against a bounded extraction.

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

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

A sixth of what, exactly

The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.

wrong · Distance 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

The saving, spent

A bidirectional index whose reverse half cannot locate is a sixth smaller. Give that sixth back to the half that does locate, and the same total size answers a locate five times faster.

practice · Distance a fixed-length code97,718 bits5.00 ranks · in orderthe best ordered tree77,890 bits3.98 ranks · in orderthe best tree of any shape76,789 bits3.92 ranks · unorderedσ 21 · the ordered tree is 1.43% above the unordered optimum16,384 characters of englishorder costs 1.43%

The tree the operation insists on

The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small.

structures · Symbol 051015510152025symbols in the alphabetfactor saved, and per cent paidranks saved, as a factorbits paid, per cent8,192 characters · 2 errorsx14.0 for 0.04%

A factor of fourteen, for four per cent

The compound walk removes a factor of σ from every interval extension. It requires a tree whose leaves are in order, which costs between nothing and five per cent of the wavelet tree. Both numbers on one plate, and the trade is not close.

bounds · Symbol a segment tree over the chain2.70x8,142,274 bitsa succinct range minimum over the chain1.62x4,898,356 bitsno chain at all0.84x2,534,726 bitsthe dashed rule is the index itself: a suffix array and the text131,327 characters · 256 documents2.70x → 0.84x

The apparatus that is smaller than its index

Answering "which documents hold this" at a price proportional to the answer used to cost 2.70 times the index it sits beside. Two changes later it costs 0.84, and the largest thing left is an array that says which document each row belongs to.

practice · Index 020406080255075100125one sampled position in every …of the plain index, per centsize: 84.7%67.5 steps16,384 characters · 8-character patternssize falls, the walk lengthens

Bits and steps on one frame

The size falls from ninety-nine per cent to eighty-six as the sampling thins, and the walk to a sampled position rises from two and a half steps to sixty-four. Neither line is the answer; the answer is a point on the pair.

structures · Distance

Named alongside it

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

Index sizeBidirectional indexPracticeRankSpaceAlphabetAlphabetic codeCompound operationFM-indexHuffman codeLocateParameter

All concepts