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

Deferral — where it appears

A piece of work named and not done, written down so that it can be taken up later. Its value is that a structure named and not built is a structure whose constants are unknown, and naming one is what makes the difference between an expectation and a measurement.

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

one index35,3354.31 bits/charthe forward half35,3354.31 bits/charthe reverse half35,3354.31 bits/charboth, which is the structure70,6708.63 bits/charbits8,192 characters · sample 322.00x one index

The structure that was supposed to halve

A bidirectional index holds the transform of the text and the transform of its reversal — 35,335 bits each, 70,670 together, exactly twice one index. The deferral that named it hoped it would stop the index doubling. It does not remove the doubling; it reuses it.

space · Distance 02e+34e+36e+301234567891011level of the wavelet treebitsplainblock-codedrun-coded3,612 points · 12 levels24 copies of 2048 characters

The level where compression stops paying

Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.

wrong · Grid

Named alongside it

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

Index sizeMeasurementTrade offBackward searchBidirectional indexBreak-evenCompressionConstant factorControlError boundFM-indexGrid

All concepts