The packing contest

The last chapter ended with an experiment: War and Peace shrinks almost threefold, the archive from Chapter 45 by a factor of two and a half, and three megabytes of random bytes not by a single byte. So text and tables hold something superfluous that can be thrown away and later restored without a flaw. What is it? And is it true that ZIP can turn three gigabytes into one? We start with the extremes.

A million zero bytes are packed with the same method that ZIP uses. How many times smaller does the file get?

half the size a hundred times about a thousand times a million times: a couple of bytes are left

About a thousand: 991 bytes. A million is far out of reach because the method has a ceiling. Where it comes from will become clear in the round about DEFLATE.

A million zeros turned into 991 bytes. The tongue twister repeated twenty thousand times, three quarters of a megabyte, shrank more than three hundred times. The third line is the most curious: the same bytes, shuffled, shrink only about twofold. The letters and their frequencies haven’t changed, yet the packed file is now a hundred and fifty times larger. So the superfluous part lives in the order, in the fact that the next character can be guessed from the ones before it. Zeros can be guessed completely, repeats almost completely, shuffled letters only by their frequencies, and random bytes not at all.

The same goes for three gigabytes: it all depends on what is inside them. Texts, tables, programs and server logs sometimes shrink tenfold. A film or an archive of photos will hardly shrink at all: they are compressed already, and there is nothing left in them to guess. All a packer can do is find what is predictable in the data and not store it.

The chapter is a contest. Five files are the lots, the packers are on stage, and a scoreboard counts the bytes. Your own ideas compete first. Then the professionals come out one by one, and each brings an idea worth stealing. In the last round the rules change: you may lose data, as long as the eye can’t tell.

The rules of the contest

Compression is a pair of programs: a packer turns bytes into other bytes, usually fewer of them, and an unpacker gives back the original ones. The first four rounds follow the rule of lossless compression: what comes out of the unpacker must match the original bit for bit. A program with one comma changed by packing may refuse to run, and a missing digit in a bank statement is somebody’s money. The scoreboard checks every contestant: it packs, unpacks and compares. A contestant whose bytes don’t match is disqualified.

There are five lots, and they differ on purpose:

• Tolstoy: the first forty thousand characters of War and Peace in the Maudes’ translation, in UTF-8, 40,840 bytes;
• DNA: the genome of phage lambda in FASTA format from Chapter 27, the letters A, C, G, T, seventy to a line, 49,254 bytes;
• code: the source of the random module from Python’s standard library, 37,299 bytes;
• picture: a drawing of 240 × 160 pixels in sixteen colors, one byte per pixel holding the number of its color, row after row, 38,400 bytes;
• noise: 30,000 random bytes.

The score is the total size of the five packed files: the smaller, the better. Everything lives in the module cs.packing: lots() hands out the lots, and contest(pack, unpack) holds the contest and prints a table. Inside the module are the packers this chapter builds, gathered in one place.

Milwaukee, 1988. The archive war

Almost forty years later ZIP is on every computer, and .docx, .xlsx and .jar files are ZIP archives inside. The compression method it uses today came later: Katz invented it for PKZIP 2.0 in 1993, and the contest will reach it halfway through.

Round 1. Your own ideas

Before watching how the professionals compress, try it yourself. Anyone who has read Chapter 28 will think of this first: ASCII has no use for the eighth bit. An English text in UTF-8 spends a whole byte on each letter, and the letter needs only seven of its bits. Eight characters fit into seven bytes, and Tolstoy will lose an eighth of his weight. If some byte needs all eight bits (say, a file of random bytes has come in), we keep the bytes as they are. To tell the unpacker what to do, we put a marker letter in front: T for packed text, B for bytes as they are. Packed text also carries its length, so that the zeros padding out the last byte aren’t taken for one more character.

The table is sobering. The idea took an eighth off the DNA, and by accident off the picture as well: its bytes are color numbers from 1 to 9, which fit into seven bits too. The other three lots each grew by a byte, and that byte is the marker. From noise we expected nothing. The code was let down by one letter in a comment: the “ö” in the name of Wolfgang Hörmann, whose method the module borrows. Tolstoy, the lot the idea was invented for, was let down by the first line of the novel. It is a line of dialogue, and it opens with a curly quotation mark; ASCII has only straight ones. One character was enough to make the idea give up on the whole file.

That is the first lesson of the contest: a packer is built for some kind of data, and whatever looks different must pass through it without breaking and without swelling. Repair the idea. You can pack character by character and give the rare characters outside ASCII an escape: a seven-bit code that never occurs in text, followed by the character’s bytes. You can go further and replace the most frequent words, “the,” “and,” “Prince,” with one-byte numbers. Edit the cell, run it and watch your place on the scoreboard.

Each professional on the board has its own strength. RLE shrinks the picture twenty-six times and nearly doubles the text, Huffman beats everyone on DNA, and on noise nobody wins. Each of them will get a round.

Round 2. Runs

The first professional is the simplest. When identical bytes come in a row, we write them as one pair: “how many times, and which byte.” The string AAAABBBC becomes “4A 3B 1C.” This is run-length encoding, or RLE. Our version stores each run in two bytes: the length (up to 255) and the byte itself.

Row 100 of the picture, 240 pixels, fits into six runs: sky, hill, house, hill, sky, hill. The whole picture takes 725 runs, that is, 1,450 bytes instead of 38,400. Tolstoy, on the other hand, has almost as many runs as bytes. In ordinary text a letter seldom comes twice in a row (the “ll” in “Well,” the “ss” in “princess”), and the first twelve bytes are twelve runs of one. A pair for every byte, and the text doubles.

RLE is good where there are large flat areas: diagrams, icons, drawings, scanned documents. Fax machines live on it. A line of the page alternates white and black runs, and the machine sends the lengths of the runs, coded with a Huffman code. For photographs RLE is useless, since neighboring pixels of a photo almost never match to the last bit. But it will come back in the last round: JPEG first turns a photo into data with many zeros in a row, and only then counts the runs.

The judges’ room: how much can be squeezed at all

Time to ask the judges whether compression has a limit. For a single file the question is odd: any file can be “compressed” into one bit if the unpacker knows in advance that this bit means War and Peace. A limit makes sense for a source, whatever produces the files. Claude Shannon found it in 1948, and the chapter on information in “Mathematics, the Queen of the Sciences” tells the story in full. The short version will do for us.

Suppose a source emits characters independently of one another, and character $x$ comes up with probability $p(x)$. A rare character is news; a frequent one is hardly news at all. Shannon measured news in bits: a character with probability $p$ carries $-\log_2 p$ bits. A letter that turns up in every second position is worth one bit, one in every eighth position three bits. The average over all characters is called entropy:

$$H = -\sum_x p(x) \log_2 p(x) \ \text{bits per character}.$$

Shannon’s source coding theorem says that no lossless code can spend fewer than $H$ bits per character on average, and that you can come close to $H$. The Huffman code from Chapter 23 comes within a bit of the entropy: on War and Peace it needs 4.45 bits per character against an entropy of 4.42. The difference between the number of bits stored and the amount of information in them is called redundancy, and redundancy is what compression removes.

The letters of a novel, however, are not independent. After “q” comes “u” almost every time, and after “Prince Andr” comes “ew.” Once we take into account what came before a character, there is less news in it. Below is the entropy of the next character when the previous $k$ are known. To get it, we take the uncertainty of the pair “context plus character” and subtract the uncertainty of the context alone. What remains is whatever the character brings that the context didn’t already tell us.

With each character of context the estimate drops: 4.42, then 3.45, 2.74, 2.12, 1.73. Packers that take context into account do break through the “Huffman ceiling”: DEFLATE spends 2.90 bits per character, bzip2 2.09. Huffman, letter by letter, can’t go below 4.42 on the same novel.

The last numbers in the table cheat, though. With four characters of context there are almost sixty thousand different contexts, and many of them occurred once or twice. Such a “model of the language” has learned the novel by heart: after a rare context it knows the next letter for certain because it has seen that context only once. Push $k$ further and the estimate goes to zero, but the model would have to be stored along with the file, and it would come out bigger than the novel itself. So the size of the model must be added to the size of the archive; we will come back to this thought when we look for an archiver that compresses everything.

Round 3. “See above”

Huffman looks at letters one at a time, but the redundancy of a text lies above all in repetition: words, turns of phrase, names, whole sentences. “Prince Andrew” occurs in the novel more than a thousand times. Instead of writing a repeat out again, you can point to where it appeared before: “copy the 13 characters that stood 1,241 characters back.” In 1977 Abraham Lempel and Jacob Ziv of the Technion in Haifa turned this idea into an algorithm. Their paper was called A Universal Algorithm for Sequential Data Compression, and the algorithm goes by the initials of their surnames and the year: LZ77.

The packer walks along the text and keeps a window in view: the last few thousand characters. At each position it looks in the window for the longest match with what comes next, and outputs a triple: how far back to go, how many characters to copy, and which character follows the copy. If there is no match, the triple $(0, 0, \text{char})$ carries a single character. The unpacker has nothing to figure out: it copies what it is told.

In the tongue twister the first four characters are new; after that, references carry most of the text, and only a letter not seen before (the “l,” the “y,” the “r”) still comes on its own. (13, 3, 'l') means “go back 13 characters, take 3 (that’s ‘she’) and add ‘l’”: the “shel” of “seashells” is borrowed from “she.” The second line is more interesting. Its last triple, (3, 14, '!'), says to go back 3 characters and copy 14, more than had been written after the point of return. The unpacker copies one character at a time, and each copied character at once becomes a source for the next ones: “la-” multiplies on its own. So LZ77 gets for free what RLE did: a run of a thousand zeros is one zero and a reference “back 1, copy 999.”

You have met such a reference before. In Chapter 43 we took apart a DNS answer, and there the byte 0xC0 meant “read the rest of the name from such-and-such a place in the packet above”: the name legost.in is written out once in the answer, and later mentions point back to it. The same “see above,” only for names.

Finding a repeat fast

Our packer has a problem: for every position it tries every start in the window, four thousand comparisons per character. On a tongue twister this costs nothing; on a novel it is agony. The professionals search differently, and you know their tool from Chapter 16: a hash table. A repeat shorter than three characters doesn’t pay anyway, since a reference costs more than two letters. So it makes sense to look only at the places in the window where the same three characters begin as at the current position. We keep a dictionary “three characters → positions where they occurred” and check those positions alone.

Both packers produce the same triples, but at four thousand characters the second is already more than a hundred times faster, and it packs a million characters of the novel in about a second. Brute force would labor over the million for a couple of minutes: it makes thousands of comparisons for every triple.

DEFLATE looks for repeats the same way. Its specification, RFC 1951, describes a chained hash table with a hash computed over three bytes, and a comment in the source of the zlib library admits, “The matching algorithm for small strings is inspired from that of Rabin & Karp,” the algorithm of Chapter 27. For common combinations such as “ th” the chains grow long, so zlib checks only the nearest places: four at compression level 1, 128 at the usual level 6, up to 4,096 at level 9. This chain length is what the “faster or smaller” knob of any archiver controls.

A dictionary that grows by itself: LZW and the patent

A year later Lempel and Ziv proposed a second method, LZ78, and in 1984 Terry Welch of Sperry simplified it into an algorithm named after all three of them, LZW. It has no references back. Instead of a window there is a dictionary of phrases that the packer builds as it goes. At first the dictionary holds only single characters. The packer reads the text for as long as the phrase stays familiar, outputs the number of the longest familiar phrase, and adds to the dictionary that phrase extended by the next character. The unpacker, reading the numbers, builds an identical dictionary, so the dictionary itself never has to be sent.

On a short text the dictionary barely has time to learn anything: by the end of the tongue twister it has picked up “chuc” and “ wood,” and sixty-nine characters have become 44 numbers. On megabytes of text the dictionary grows to thousands of phrases and saves in earnest. LZW was fast and simple, and it went into the Unix program compress and into GIF, the image format CompuServe released in 1987. A few years later GIF was on every web page. And then it turned out that LZW had an owner.

DEFLATE: a team of two

The method under ZIP, PNG, gzip and the compression of web pages is called DEFLATE. Phil Katz invented it for PKZIP 2.0, and in 1996 L. Peter Deutsch described it in RFC 1951. The idea is to yoke two of our contestants together. First LZ77 with a 32 KiB window turns the text into a stream of single characters and “length, distance” references; a repeat can be from 3 to 258 bytes long. Here is the ceiling from the chapter’s first experiment: one reference covers at most 258 bytes and costs at least a couple of bits, so DEFLATE can’t shrink even a million zeros by more than about a thousand times.

Then a Huffman code compresses that stream: frequent characters and frequent lengths get short codes. LZ77 removes the repeats, and Huffman removes the uneven frequencies of what is left. Each loses on its own, but as a team DEFLATE beats both LZ77 and Huffman on the scoreboard, on every lot except DNA.

This shows the asymmetry that compression relies on in everyday life. Level 9 takes several times longer than level 1 and wins a sixth of the size, while unpacking takes milliseconds either way: the unpacker has nothing to search for, it only copies. So a file that is packed once and unpacked millions of times (a library, an update, a page of a website) is worth packing at the maximum. The gzip module gives the same DEFLATE with a different header. That is how this site’s server sends you its pages: in its request the browser writes the header Accept-Encoding, listing the compression methods it understands, and the server answers with a body in gzip marked Content-Encoding: gzip. HTTP headers are the subject of Chapter 43.

On DNA, DEFLATE lost to Huffman. A genome has four letters, and Huffman gives each of them two bits at once, a quarter of a byte. The phage genome has few long repeats, so LZ77’s references hardly help, yet the mere possibility of them has to be paid for. That is why genomes, sound and pictures get packers of their own.

Round 4. Wheeler’s permutation

You remember David Wheeler from Chapter 5: in the early 1950s, on EDSAC, he taught subroutines to return to the place they were called from. More than thirty years later, in 1983, he had an idea from a completely different field: rearrange the letters of a text so that identical ones end up side by side, and do it in a way that can be undone. He published it only in 1994, with his former graduate student Michael Burrows, in a report of DEC’s research center. Since then it has been called the Burrows–Wheeler transform.

The recipe fits in one line. Append to the text a marker that doesn’t occur in it, write out all the cyclic shifts (the text started from each of its letters in turn), sort them alphabetically and read the last column from top to bottom.

“banana” becomes “annb$aa”: the same letters, rearranged. A 1,500-character excerpt of the novel shows what it was all for: “nnnnnnnnnnnn,” “ttttttt,” “rrrrr,” “iiiii.” The letters stick together because the shifts are sorted by what comes after the last column, by the continuation. All the shifts that begin with “g ” stand next to one another in the table, and the last letter of each is the one that precedes that “g ” in the text, which in English is nearly always “n”: “young,” “drawing room,” “something.” The transform gathers into runs the letters that share a continuation. And runs like these, as we have seen, are what RLE and Huffman compress well.

The transform would be useless if it couldn’t be undone. Yet the whole text can be restored from the last column alone. Sort the last column and you get the first: in the table they hold the same letters, only in alphabetical order. The pairs “last, first” are pairs of neighboring letters of the text. Sort the pairs and you get the first two columns, and so on, until the whole table is back; the row with the marker at the end is the original text. That is how inverse_bwt in the cell works, only slowly: $n$ sorts of $n$ rows. There is a way to reverse the transform in linear time, and you will find it yourself in a task at the end of the chapter. Try it by hand first.

bzip2, which Julian Seward released in 1996, is built on this transform. It cuts the data into blocks of up to 900 KB and transforms each of them. Then it recodes the letters so that a recently seen letter becomes a small number (after the transform, often zero), folds up the runs of zeros, and hands what is left to Huffman. On the scoreboard bzip2 is the best on Tolstoy and on code, and on the whole novel it spends 2.09 bits per character against DEFLATE’s 2.90. It pays in speed and memory: sorting hundreds of thousands of shifts costs more than searching a window for repeats. bzip2 doesn’t add a marker. It sorts the cyclic shifts of the block as they are and writes down the number of the row the unpacker should start from. Our cell does add a marker, and then the shifts come in the same order as the suffixes: this is the suffix array from Chapter 27, which is how the transform is built quickly. That chapter promised the transform would come in handy in genetics. Indexes built on it let programs such as Bowtie and BWA align millions of short reads to the human genome while keeping the genome in memory in compressed form.

An archiver that compresses everything

The scoreboard keeps showing one stubborn line: on noise everybody loses. Maybe nobody has found the right method yet?

A company sells an archiver and promises that it will shrink any file one megabyte long by at least one byte, and unpacking will give the file back unchanged. What do you think?

Hard but possible, with a good enough search for patterns Possible, but only for texts Impossible, whatever the method

Impossible, and the proof is a count. See below.

A second compression gains nothing: after the first there is no redundancy left, and each further pass adds its own overhead bytes to the file. Random bytes behave the same way from the start. Every compression is a trade. The packer counts on meeting “typical” files (text with repeats, a picture with flat areas) and shortens them at the expense of atypical ones, which hardly ever occur in practice. Our marker B from the first round is that kind of payment: whatever we can’t compress we lengthen, but by no more than a byte.

The lot “noise” in the module cs.packing is made in one line: random.Random(47).randbytes(30_000). Thirty thousand bytes that defeated every archiver are described by a program a few dozen characters long. The length of the shortest program that prints a given string is called the string’s Kolmogorov complexity; Andrey Kolmogorov proposed the measure in 1965. It is the ideal limit of compression, since nothing can say it more briefly than the shortest program. But the limit is out of reach. No algorithm computes Kolmogorov complexity: it is a relative of the undecidable problems of Chapter 56. Archivers look only for the patterns they were built for: repeats, frequencies, runs. The pattern “this is the output of a random number generator” is beyond them.

Round 5. Losing is allowed

In the last round the rules change. A photograph can be treated more freely than a program or a bank statement: if the color of one pixel in a million shifts slightly, nobody will see it. So instead of the photo you can store a different, very similar picture that is much easier to compress. This is lossy compression. The question of the round is what to throw away so that the eye misses the loss and the file becomes dozens of times smaller.

A picture of 320 × 200 pixels takes 192,000 bytes: three bytes per pixel. JPEG at quality 90 stores it in 17,734 bytes, eleven times less, and the eye sees no difference. At quality 50 it is twenty-seven times smaller and still looks decent. Below that the decay sets in: squares eight pixels across show through, ripples appear around the letters, and the grass turns into green tiles. Where the squares and ripples come from becomes clear once JPEG is taken apart, and you will recognize almost every contestant inside it.

Color is stored more coarsely than brightness. The eye sees fine detail in brightness well and fine detail in color poorly. So JPEG converts each pixel from red, green and blue into brightness and two “color” channels, and usually stores the color channels at half the resolution along each axis: one color value for four pixels. Half the data is gone at once, and almost nobody can see it.

8 × 8 squares are broken into waves. Each channel is cut into squares of 64 pixels, and each square is written as a sum of 64 standard patterns, cosine waves of different frequencies across and down: a flat background, a smooth gradient from left to right, from top to bottom, stripes growing denser, checks growing finer. This is the discrete cosine transform, or DCT. It was proposed by Nasir Ahmed, T. Natarajan and K. R. Rao in 1974, and it is a close relative of the Fourier series in the math course. The DCT by itself loses nothing: the 64 coefficients give back the pixels without a flaw. But in natural pictures nearly all the “energy” sits in the first few slow waves, and the fast ones, which carry the finest details, are small.

Most is lost in rounding. Each coefficient is divided by a step of its own and rounded to a whole number. The steps are small for slow waves and large for fast ones, so most of the fast coefficients turn into zeros. This is quantization. The “quality” slider of libjpeg, the library most programs use, changes the size of these steps by multiplying their whole table by one factor. At quality 90 the steps are small; at quality 2 they are so large that nothing is left of a square but its average color, hence the tiles.

Then comes lossless packing, with our own tools. The 64 rounded coefficients are written out in a zigzag, from slow waves to fast, and at the end of the zigzag long runs of zeros line up. They are coded by run lengths, as in round 2, and the result by a Huffman code, as in Chapter 23. The ripples around the letters are Gibbs ringing. A sharp edge is made of many fast waves, and when some of them are thrown away, the rest ring.

The same approach works for sound. In Chapter 28 we recorded sound as samples: a CD stores 44,100 samples per second at 16 bits for each of two channels, 1,411.2 kilobits per second. A song in MP3 usually takes 128 kilobits per second, eleven times less. MP3 also breaks sound into frequencies and quantizes them, and it stores most coarsely what the ear won’t hear: a quiet sound close in frequency to a loud one goes unheard, masked by the loud one. The better the model of perception, the more can be thrown away unnoticed.

Tasks

Four tasks: runs in a fax, LZ77 there and back, entropy with context, and the inverse Burrows–Wheeler transform. Each has a big test with a stopwatch, and in the last three brute force won’t get through.

A fax sends a page row by row. A row is a string of '0' (a white dot) and '1' (a black one), and what goes down the line is the run lengths: how many whites in a row, then how many blacks, then whites again, and so on. The first run is always white; if a row starts with a black dot, the first run is zero. Write rle_encode(row), which returns the list of run lengths, and rle_decode(runs), which gives the row back. For example, rle_encode('0000011100000000001') is [5, 3, 10, 1], rle_encode('110') is [0, 2, 1], and an empty row has no runs: []. The last test encodes and decodes a whole page within a second: 2,000 rows of 1,728 dots, the number of dots in a row of an A4 page on an ordinary fax machine.

Walk along the row keeping the current color, '0' at first, and a counter. A character of the same color increases the counter. A character of the other color closes the run: the counter goes into the list, the color switches, and the counter becomes 1. Don’t forget the last run after the loop.

With this walk, a black dot at the start closes a white run of length 0 by itself, so no special case is needed. But for an empty row there is nothing to add after the loop.

On the way back, runs with an even index are white and runs with an odd index black: '01'[i % 2] * n. Join the pieces with "".join rather than adding to a string in a loop.

The agreement that “the first run is white” saves sending the color at all: it alternates by itself. The fax standard goes further and codes the lengths themselves with a Huffman code, with ready-made tables for white and black runs: short black runs (letters) and long white ones (margins) get short codes. Two ideas of the chapter in one machine.

Write lz77_encode(text, window=4096), returning a list of triples (back, length, char) as in the chapter, and lz77_decode(triples), returning the text. The rules for a triple: back is at most window and at most the number of characters already written; if length is zero, back is zero too; a copy is always followed by one character, so a repeat can’t stretch all the way to the end of the text. A repeat may (and should) overlap itself: 'a' * 1000 takes two triples. The packing must be no worse than greedy: at each position take the longest repeat in the window, though repeats shorter than three characters may be skipped. The tests unpack your triples with their own unpacker, count them, and pack 60,000 characters of the novel with a window of 4,096 within two seconds.

The unpacker is a few lines: for each triple, copy length characters that stand back positions from the end, then append the character. Copy one character at a time: that way a copy that overlaps itself comes out right.

The packer in the starter is correct, but for each character it tries up to 4,096 starts. On 60,000 characters that adds up to tens of millions of comparisons. Recall the section “Finding a repeat fast”: a dictionary “three characters → positions,” and check only the positions with the same three characters, from the nearest to the farthest.

Remember to add to the dictionary the positions of every character the triple covered, including those after the first. Otherwise the repeats that begin inside a copied piece get lost, and the triples multiply.

The positions in each list are in increasing order, so reversed goes through them from the nearest to the farthest, and the first position outside the window ends the search. In the worst case, a text of one repeated letter, the chain stretches across the whole window, which is why zlib limits its length. The asymmetry is the same as in the cell about DEFLATE levels: the packer needs a hash table and a search, the unpacker four lines, and unpacking is always fast.

Write entropy(text, k=0), the entropy in bits of the next character of a text when the $k$ previous characters are known. Take every position $i$ from $k$ to the end: each has a context text[i - k:i] and a next character text[i]. For each context, compute the entropy of the distribution of the characters that follow it, and average over the contexts with weights equal to the share of positions where each context occurred. With k=0 the context is empty, and you get the ordinary entropy of characters: entropy('abab') is 1.0 bit, and entropy('ab' * 50, 1) is 0, because after a always comes b and the other way round. If the text has no more than $k$ characters, the answer is 0. The last test computes the entropy of the whole of War and Peace with two characters of context and allows ten seconds for it.

Group the positions by context, as in Chapter 8: a dictionary “context → Counter of the next characters.” The entropy of one counter is $-\sum \frac{c}{n} \log_2 \frac{c}{n}$, where $n$ is the sum of its values.

The weight of a context is $n / (\text{len(text)} - k)$: the share of positions where it occurred. The weights add up to one.

You can also do without grouping, with the formula from the chapter: the entropy of the pairs “context + character” minus the entropy of the contexts. It is the same number; check it on a small example.

This is conditional entropy: the average uncertainty of the next character once the context is known. The two formulas, “an average over contexts” and “pairs minus contexts,” agree by a property of the logarithm: $\log \frac{c}{n} = \log c - \log n$. Remember the trap from the judges’ room: as $k$ grows the estimate falls, but for a large $k$ it only shows that the model has learned this particular text by heart.

Write inverse_bwt(last): restore the text from the last column of the Burrows–Wheeler transform. The transform was made as in the chapter: the character $, which occurs nowhere else in the text, was appended to it, and the shifts were sorted by Python’s ordinary string comparison. Return the text without the $: inverse_bwt('annb$aa') is 'banana', and inverse_bwt('$') is the empty string. The chapter’s method, appending a column $n$ times and sorting the table, takes on the order of $n^3$ time (at each of the $n$ steps, $n$ strings up to $n$ characters long are glued together anew) and $n^2$ memory, and the last test gives the transform of a hundred thousand characters of the novel and two seconds.

The first column of the table is sorted(last). Take row number $j$ of the table: its last letter, last[j], stands in the text right before its first letter. So if you know in which row of the table the letter last[j] stands first, you can walk through the text letter by letter.

Everything rests on one observation: equal letters come in the same order in the last column and in the first. The third “a” from the top of the last column is the third “a” from the top of the first: both rows where these a’s stand are sorted by what comes after the “a.” So a stable sort of the row numbers by their letters, sorted(range(n), key=lambda i: last[i]), gives the correspondence at once.

Which row do you start from? The row that ends with the marker is the text itself with a $ at the end. Start with i = last.index("$") and take $n$ steps i = order[i], writing down last[i].

One sort, $O(n \log n)$, and $n$ steps through a ready correspondence; if instead of sorting you count how many of each letter there are, you get $O(n)$. This correspondence is called the LF mapping, for last-to-first: from the last column to the first. The genome indexes of Chapter 27 rest on it too: they keep the last column, compressed, with small helper tables, and with it they can restore the text and search it for patterns as well.

What next

The contest ended without an overall winner. Each professional throws away its own kind of predictability: runs (RLE), uneven frequencies (Huffman), repeats (LZ77, LZW), shared continuations (Wheeler’s transform), and the packer is chosen to suit the data. Entropy tells how much will remain once the predictable is gone, the pigeonhole principle forbids compressing everything, and lossy compression also throws away whatever a person won’t miss.

Compression has a less visible job as well. When Brin and Page described their search engine in 1998, about half of all its data was the archive of downloaded web pages, compressed almost threefold. The indexes through which the engine looks up words are stored compressed too. But storing pages is only half the job; you also have to find what you need in them. There are billions of pages, and the answer to your query arrives in a fraction of a second, before you can lift your finger from the key. Nobody can read the whole web in that time, so the answer must be ready in advance. How can it be ready when the question hasn’t been asked yet? That is the subject of the next chapter, where we build a search engine for this site’s textbooks.