Generator

Every rotation of "measured-not-asserted", sorted

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Every rotation of "measured-not-asserted", sortedThe transform is the last column of this table. It is a permutation of the input — the same characters in a different order — so its zeroth-order entropy is exactly the input's, 3.899 bits per symbol, and by that measure nothing has happened. What has happened is that characters sharing a following context now sit together: on a 8,192-symbol stream the mean run goes from 1.01 to 3.38, and a move-to-front pass turns that into a floor of 1.80 bits per symbol against 4.16.each row is one rotation · the table is sorted · the transform is the last columnfirstlast◇measured-not-asserted-asserted◇measured-not-not-asserted◇measuredasserted◇measured-not-asured-not-asserted◇med◇measured-not-asserted-not-asserted◇measureeasured-not-asserted◇med◇measured-not-asserted-not-asserted◇measurerted◇measured-not-assmeasured-not-asserted◇not-asserted◇measured-ot-asserted◇measured-n… 8 further rotationsmeasured on 8,192 symbols of the same source:H₀ of the text3.899 bitsH₀ of the last column3.899 bitsH₀ after move-to-front, before4.156 bitsH₀ after move-to-front, after1.802 bitsmodel: order 0, before and after a permutationmean run 1.01 → 3.38

Every rotation of "measured-not-asserted", sorted

The transform is the last column of this table. It is a permutation of the input — the same characters in a different order — so its zeroth-order entropy is exactly the input's, 3.899 bits per symbol, and by that measure nothing has happened. What has happened is that characters sharing a following context now sit together: on a 8,192-symbol stream the mean run goes from 1.01 to 3.38, and a move-to-front pass turns that into a floor of 1.80 bits per symbol against 4.16.

Drawn at 700 × 548, wide on the page. Everything above is what bwt-columns returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

9 essays call bwt-columns. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

each row is one rotation · the table is sorted · the transform is the last columnfirstlast◇the-order-is-the-message-is-the-message◇the-order-message◇the-order-is-the-order-is-the-message◇the-the-message◇the-order-isage◇the-order-is-the-messder-is-the-message◇the-ore◇the-order-is-the-message-message◇the-order-is-the-order-is-the-message◇ther-is-the-message◇the-ordessage◇the-order-is-the-mge◇the-order-is-the-messahe-message◇the-order-is-t… 11 further rotationsmeasured on 8,192 symbols of the same source:H₀ of the text3.899 bitsH₀ of the last column3.899 bitsH₀ after move-to-front, before4.156 bitsH₀ after move-to-front, after1.802 bitsmodel: order 0, before and after a permutationmean run 1.01 → 3.38 The data that is not a number

The transform that emits nothing

thousands of bits · the floor is 31.9kthe text as it is34.0k streamto undo itnothinga shuffle agreed in advance34.4k streamto undo itnothingthe characters sorted0.3k streamto undo it31.8kthe Burrows–Wheeler transform14.8k streamto undo itnothingmodel: order 0 after move-to-front · Words from a fixed vocabularydashed: coding the text as it stands The floors

What a reordering costs to undo

11010010⁴10⁵queries answeredcharacter comparisons, cumulative5 queriesScan each timeIndex, then queryone unit = one character comparison · 4 doubling roundsbreak-even at 5 queries Structures

The index that is the text

01234characters of context the sort reads, kbits a symbol after move-to-front012481632the full transform, 1.802ties kept in text orderties sorted by symbol: the stream alonethe text's own floormodel: order 0 after move-to-front · Words from a fixed vocabularyexactly the transform from k = 24 The floors

The order inside a tie

words drawn independentlymean +0.0038 ± 0.011ahead on 10 of 16next word set by the last lettermean +0.0064 ± 0.011ahead on 12 of 16no difference−0.0176+0.0000+0.0251bits a symbol the short context savesthe stream reported beforek = 4 · 16 streams a source · bands: ±1 standard deviationone draw, not a result The floors

A result the size of its own noise

123456810121624context length k, characterswords drawn independentlynext word set by the last letterwords from the whole vocabularythe corpus of essaysthe corpus of technical writingthe sweep flattensopen ambiguity under 1%all ambiguity under 5%eight streams a sourcethresholds: 0.01 bits, 1%, 5% The floors

Where a context stops naming the letter before

00.0200.04000.1000.200positions in a repeated 16-character stringexcess at 8 characters, bits a symbolthe corpus of technicalwriting, r = 0.98the corpus of essays, r = −0.37one point a streamcontext of 8 characters The floors

The repeats a context cannot see past

2.802.9033.1040506070characters read a symbolbits a symbol after move-to-frontsorted by 2sorted by 4sorted by 8by 2, deepenedby 4, deepenedby 8, deepenedthe full transformeight streams of 8,192 charactersthe corpus of technical writing The floors

The deepening the sort was already doing

the corpus of technical writing0.000.010.020.0355606570the corpus of essays0.000.010.020.03556065characters read a symbolbits a symbol above the transformolive: longest first · dark: most different · green: transformeight streams of 8,192 characters eachrotations first sorted by four characters The floors

The order the column cannot see

The library, page 1 of 5 — where bwt-columns sits