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

Information content — where it appears

The number of bits needed to tell one object apart from every other the setting allows, which is the logarithm of how many there are. It is the floor a structure's size is measured against: a run count or a phrase count bounds the information in a collection of copies, and an entropy that cannot see a copy overstates it.

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

10110100runs in the transform, rbitsthe structurelog₂ N(r)12 characters · 2 symbols · all 4,096 texts walkedgap 14.1x–92.0x

A floor under a run count

A structure whose size is a function of the number of runs in a transform must give a different bit string to every text with that many runs, so it needs at least the logarithm of how many such texts there are. That count is walked rather than estimated — all four thousand and ninety-six of them — and the representation everybody uses turns out to have five bits of slack.

floors · Repeat 0.2%0.5%1%2%5%10%0.020.050.10.2share of the copies' characters changed (log scale)runs a character, r/n (log scale)scattered substitutionsblocks of 4blocks of 16blocks of 64blocks of 256r-index smaller belowidentical copies32 copies of 512 characters4 collections a point

A paragraph rewritten, not a letter changed

Every collection of copies measured so far drifted by flipping single characters at random, and a real repetitive collection changes a paragraph at a time. At the same share of characters changed, the shape matters by an order of magnitude: across thirty-two copies of one text a scattered substitution adds 4.6 runs to the transform and 1.9 phrases to the parse, and a rewritten block of 64 characters adds 24 runs and 12 phrases — 0.38 runs a changed character against 4.6. With 2% of the copies changed, scattered edits put the run count at a tenth of a character and hand the smallest index to the entropy-bounded one; the same 2% in blocks of 16 leaves both repetition indexes far under it. A block's phrases follow two plus its length over 7.5, the mean phrase of fresh text, and phrases over runs never comes near the 1.28 at which the r-index would become the smaller.

text · Repeat

Named alongside it

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

CompressibilityBurrows-wheelerBurrows-wheeler transformCounterexampleCounting argumentExhaustive searchFalsificationFM-indexHonest limitIndex sizeLempel zivLower bound

All concepts