Burrows-wheeler transform — where it appears
Named by 20 essays across 7 fields — each of them below, with the objects they name alongside it.
A search that runs backwards
Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.
The index that is smaller than the text
The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.
The transform that emits nothing
The Burrows–Wheeler transform outputs exactly the characters it was given, in a different order. Its zeroth-order entropy is therefore identical to its input's, to fifteen decimal places, and by that measure it has done nothing at all. A Huffman coder handed the result spends 1.935 bits per symbol where the same coder on the same data spends 4.209, and the difference is entirely in the order.
What a reordering costs to undo
Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.
The text that does not have to be kept
The index reproduces its text character for character, in 1,024 mapping steps and zero reads of anything. That is the whole justification for weighing it against the text rather than beside it — and the price is a dial that moves the structure by 3.3 times and the cost of locating one match by 72.
The sampling that follows the runs
A run-length index over thirty-two copies of one text spends 11,286 bits on its suffix-array sampling and 5,605 on the transform it was built to compress. Sample at the run boundaries instead and the sampling is 10,942 bits that stop moving — two values per run, and a function that fills in everything between them.
A function with r pieces
Computed at every one of eight thousand positions across four texts, a function defined on the whole suffix array agrees exactly with r−1 anchors and one addition. Anchor it at the successor instead of the predecessor — one character of code — and it disagrees at 506 of 800 positions while still returning plausible numbers.
The occurrence carried through the search
Backward search returns how many and not where, and every index on this site pays for the second question separately. Carrying one occurrence along with the interval costs a lookup on 75% of the steps for a two-character pattern and on 18% of them for a sixteen-character one, and it is what makes a run-boundary sampling usable at all.
The phrases a text copies from itself
Four thousand characters of English-like text hold 604 phrases in the greedy parse and 1,219 runs in the transform. Thirty-two copies of one text hold 156 phrases and 233 runs. Two measures of repetition, neither of them an entropy, and they do not agree about which text is the more repetitive.
The order inside a tie
Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.
A result the size of its own noise
Sorting rotations by their first four characters beat the full Burrows–Wheeler transform by 0.022 bits a symbol. On sixteen streams of the same source the mean difference is 0.004 with a standard deviation of 0.011, and the short context is ahead on ten of them. The 1.2% was one draw. What survives is sharper than the result it replaces: from four characters upwards, every run break either rule makes is at a word boundary, and nothing above four characters decides anything at all.
Where a context stops naming the letter before
A sort of rotations by their first k characters matters only where those k characters fail to decide the character before them, and that share of positions can be counted in one pass with no sorting. It was proposed as a replacement for sweeping k. Counted as proposed, it misses by a factor of four: on a stream of independent words 37% of positions are still ambiguous at four characters, where the sweep has already gone flat. Counted only where the context sits inside a word that goes on past it — the one place more context can still help — it lands within a step of the sweep on four sources of five.
The repeats a context cannot see past
Sorting rotations by their first k characters stops losing to the full Burrows–Wheeler transform at four or five characters on four sources and at about ten on a corpus of technical writing. The count proposed to explain the exception — how much a context spanning a word boundary says about the letter before it — cannot be read off its own estimate, which falls on words drawn independently where there is nothing to find. Measured against each text's own shuffled twin, the information the word order carries is real, but it has all arrived by four or five characters, and at eight, twelve and sixteen the two corpora are indistinguishable. What does separate them is repetition. Stream by stream, the share of positions inside a repeated sixteen-character string predicts the technical corpus's loss with a correlation of 0.98.
A sampling that costs more than the array
On four-symbol text the transform has 0.75 runs a character, so a sampling of two suffix-array values per run is one and a half values per position — 271,565 bits against the 131,088 that keeping every value costs. The structure built to remove a term proportional to the text is twice the thing it replaced.
The deepening the sort was already doing
A sort of rotations by their first k characters loses to the full Burrows–Wheeler transform where a longer string repeats, and a sort deepened only inside the ranges where contexts repeat was proposed to recover those bits at a fraction of the transform's reading. It recovers the bits: on sixteen streams every one lands within 0.006 bits a symbol of the transform, and the most repetitive goes from 0.129 bits worse to 0.001. It reads more characters than the transform, not fewer — 74.5 a symbol against 69.4 on technical writing — because a comparison sort of rotations already reads deep only where rotations agree. The transform was the adaptive sort. The characters a sort by k characters saves are exactly the ones the repeats needed.
The measure that cannot see the alphabet
Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.
The order the column cannot see
A sort of rotations by their first four characters leaves ranges that agree on those four, and the full Burrows–Wheeler transform reads deeper to order them. Given a budget of characters below the transform's, spending it on the ranges whose rotations are preceded by the most different characters was predicted to reach within a hundredth of a bit at two thirds of the transform's reading — and spending it on the longest agreements, as the transform does, to waste it. The price was impossible: the four-character sort alone reads 76% of what the transform reads. The ranking was right on average, and right for a reason that makes the budget unnecessary: a range whose rotations are all preceded by one character writes the same run into the output in any order. Skipping every such range writes the transform's column exactly, on all sixteen streams, and reads 11% less on technical writing — up to 19% on the stream with the longest repeats.
The question asked at every split
A range of rotations preceded throughout by one character writes the same run into the Burrows–Wheeler column in any order, and a sort that asked that once, of the ranges four characters leave, read 11% less than the transform. Asked at every split of a sort that partitions on one character at a time, it was predicted to read a fifth less on technical writing and an eighth less on the essays. It reads four fifths less — and nearly all of that is the change of sort, which the prediction expected to cost reading rather than save it. The question's own share, measured against the same sort without it, is 29% on technical writing and 14% on the essays.
A sort that infers the order
A radix quicksort that stops at every group of rotations preceded by one character reads about fourteen characters of a text for every symbol of its Burrows–Wheeler transform. Induced sorting, which reads the order of a third of the suffixes and derives the rest, was predicted to read three. It reads 6.1 on all sixteen streams, within 0.14 of each other, and the same at every length from a thousand characters to thirty-two thousand. The question the quicksort asks saves it nothing, as predicted, for a reason the prediction did not give: its last two passes read the transform's column itself, one character for every rotation, in order to sort.
The price of a boundary is what precedes it
A separator sorts before everything, so its rows sit at the top of the suffix array and hold the documents' last characters. What a document boundary costs the transform is the entropy of the character in front of it, and nothing else.
Named alongside it
The objects these essays reach for when they reach for this one.
EntropyHonest limitMeasurement designBits per symbolContext modelMeasurementMove to frontSelf-indexIndex sizeRun-lengthCorpusR-index