» About     » Archive     » Submit     » Authors     » Search     » Random     » Specials     » Statistics     » Forum     » Facebook     » RSS Feed     Updates Daily

No. 671: Burrows-Wheeler transformed Garfield

First | Previous | 2011-03-21 | Next | Latest

Burrows-Wheeler transformed Garfield

First | Previous | 2011-03-21 | Next | Latest

Strip by: Henning Makholm

Garfield: Geamditn bch s avfeh n sh
Jon: Wleiaitobeu 'otras

The author writes:

The Burrows-Wheeler transform is the core of a family of file compression programs such as bzip2. It takes a string of characters (or bytes) and produces a string consisting of the same characters in a different order. That does not, in itself, compress the string, but the new string will tend to have long sequences of identical characters, which can be efficiently represented by subsequent compression steps. When the file is uncompressed, one can easily undo the Burrows-Wheeler transform and recover the original text (provided that one knows the clever tricks that make this possible).

Here, the dialogue of the 2010-05-27 Garfield strip has been Burrows-Wheeler transformed. The result is a little uncommon in that there are no repeated letters at all, which suggests that the original text is not very compressible. Indeed, the original dialogue contains no recurring words, or even parts of words, which makes it difficult for any compression algorithm to get a handle on it.

For the same reason, however, the scrambled text contains no repeated spaces, which would have made it more difficult to read it accurately off the image. If you want to try your hand at unscrambling it, you must know that (a) the particular BWT variant I used is the "bijective" BWT invented by David A. Scott (which does not need a designated end-of-text character or a stored index to undo), and (b) characters are compared in ASCII order, with a single implied newline character separating the two balloons.