COLT MCANLIS: Inspirtation's a funny thing.
I mean, there you are idly going about your day,
eating a banana, and boom, some amazing revelation hits you.
How fitting is it that all of the technological advances
we've had over the past 40 years have
been because of these sort of crazy, amazing
inspirational thoughts.
Take Burrows-Wheeler Transform, for example.
It's a very common compression algorithm
for Linux and the web.
But even the authors themselves will
admit that they don't fully understand how they came up
with the algorithm itself.
Huh, that's the trick with inspiration, I suppose.
You get greatness from nothingness.
But it doesn't really help you if you
want to implement the algorithm itself.
But fear not, young programmer.
I'm here to help.
My name is Colt McAnlis, and this is "Compressor Head."
[MUSIC PLAYING]
One of funny things about information theory
is that whole "theory" part.
See, there's some interesting points
about the theory that don't always work out right.
Take entropy, for example, which generally
measures the information content of a data set given in bits.
But one of the issues with entropy
is that it fails to take into account
the order of the symbols.
See, regardless of how I shuffle this data set
of 0 through 9 here, it will always have an entropy of 4.
But if you've been watching the rest of our shows,
you know that order does, in fact, matter.
Take delta coding, for example.
If we have this variation of our data set,
we can see that the delta-encoded version really
doesn't provide us with any lower entropy.
However, if we sort this data set, giving us
the nice linear number range from 0 to 9,
the delta-encoded version produces a much lower entropy
than the source stream.
Now, in an ideal world, we'd be able to just
apply this type of sort to all of our data
and end up with a perfectly compressible stream.
That's not actually how it works.
See, pure sorts are generally one directional.
That is, once you sort it, you can't get it back
in its original order without a whole ton of extra data
to tell you where everything goes.
So we can't purely sort it, but we can get close.
See, the Burrows-Wheeler transform, or BWT,
will shuffle around the data to cluster together
groups of the same symbol as much as it possibly can.
The benefit of this is that once the symbols have been clustered
together, they effectively have an ordering, which
can make it more compressible for other algorithms
that can take advantage of it.
Now, remember, this isn't a perfect sorting algorithm.
It's more of a rough clustering algorithm.
Well, technically, it's a lexographical permutation.
You know what?
Anyhow, the point is that BWT has one amazing characteristic.
We can encode to and decode from BWT
without having to add any significant additional data
to our stream.
Let's take a look.
Go!
MAGNUS HYTTSTEN: Whoa!
COLT MCANLIS: We want him talking?
The Transform part of Burrows-Wheeler Transform
starts by creating a table of shifted permutations
for your input stream.
So let's take the word "banana" as an example
and write that in the first row of our table.
Now, on each row under that, let's do a rotational shift
of that word to the right one character.
That is, all of the letters in our string shift to the right,
and the front-most character gets pushed onto the back.
We do this for each symbol in our stream, rotating one
character to the right, so we end up
with a table whose number of rows
equals the length of the stream.
The next step is to sort the rows of this table
lexographically, giving us a sorted table form.
Now, this is where some of the dark magic happens.
You can see that each row is effectively
a permutation of the word "banana,"
but also, each column is a permutation as well.
The first column, of course, is the sorted permutation
of our word.
But really, what we want is the last column, in general.
This N-N-B-A-A-A has some interesting characteristics.
Notice it's got better symbol clustering
than any of the other columns, especially our input stream
and, thus, is what we output as our encode.
Now, before you run off, there's one other piece of data
that we need to grab as well.
Notice that in our sorted table, the input string
actually sits at index 4.
We'll need this row index during the decode phase
of the Burrows-Wheeler Transform,
because it will allow us to move from our more
compressible permutation back to the source string.
Now, you may ask yourself, why do we choose this last column?
I mean, the one right next to it seems
just as good, seems to have very close clustering.
Why not that one?
Well, this is more BWT magic.
See, this last column has an interesting feature.
If we have only this, N-N-B-A-A-A,
we can recover the rest of our sorted table entirely.
The other columns don't possess the same characteristic,
which is highly important when we're
trying to invert our transform.
Banana.
MAGNUS HYTTSTEN: That's great!
COLT MCANLIS: All right.
The remarkable thing about Burrows-Wheeler Transform
is not that it generates a more compressible output--
any ordinary sort would do that--
but that this particular transform is
reversible with minimal data overhead.
And to help us demonstrate that is my good friend Magnus, who,
turns out, is training for the World Sorting Championship.
MAGNUS HYTTSTEN: Yeah!
Sorting is my thing.
Yeah. [LAUGHS]
COLT MCANLIS: Yeah.
This guy right here, he's going to take it all.
All right.
So at the start of our decode step,
we're given the string N-N-B-A-A-A and the row index
of 4.
If you recall, N-N-B-A-A-A represents the last column
of our table.
So Magnus, can you put an N-N-B-A-A-A up on the board
for us?
MAGNUS HYTTSTEN: Like that?
COLT MCANLIS: Just like that.
MAGNUS HYTTSTEN: Great!
COLT MCANLIS: DO it.
Now, when he's doing this, I want
you to watch his technique.
Watch the way his hand flows through the process.
MAGNUS HYTTSTEN: Yeah!
Finished.
COLT MCANLIS: Fantastic.
Yeah.
Young kids, you're afraid of this guy.
Now, once we have this data in our table,
the next step is to sort it, which is where Magnus comes in
for us.
All right, Magus, you ready?
MAGNUS HYTTSTEN: Absolutely.
COLT MCANLIS: We're going to do a sort.
Nice warm up.
Don't pull anything.
MAGNUS HYTTSTEN: OK.
COLT MCANLIS: All right.
When you're ready, go.
Excellent, good job.
Great form, nice.
Remember, clench those abs.
Yeah, good, stay with it.
Fantastic.
MAGNUS HYTTSTEN: All right!
Ha ha.
COLT MCANLIS: This kid's good.
All right.
Now that we've got a sorted table,
the next step is to prepend the input string again.
So Magnus, another N-N-B-A-A-A, please.
MAGNUS HYTTSTEN: Over there?
COLT MCANLIS: Right there.
MAGNUS HYTTSTEN: Great, man.
COLT MCANLIS: This guy kind gets it, right?
Good.
Nice.
MAGNUS HYTTSTEN: Ah!
COLT MCANLIS: Now-- all right.
Now that it's there, we've got to do another sort.
MAGNUS HYTTSTEN: A sort?
COLT MCANLIS: Another sort.
MAGNUS HYTTSTEN: OK.
COLT MCANLIS: All right.
Now, I'm going to time this one.
MAGNUS HYTTSTEN: OK.
COLT MCANLIS: This is going to be a good warm up round?
MAGNUS HYTTSTEN: Yeah.
COLT MCANLIS: All right.
Ready?
When you're ready, three, two, one, go.
MAGNUS HYTTSTEN: OK.
Let's go.
COLT MCANLIS: Now, remember, you've
got to tighten your abs during the sort.
You're going to be judged on speed and accuracy here.
MAGNUS HYTTSTEN: Boom!
COLT MCANLIS: Fantastic.
Look at that.
11 seconds.
MAGNUS HYTTSTEN: Yeah!
COLT MCANLIS: That's a personal best for this guy.
MAGNUS HYTTSTEN: Wow!
COLT MCANLIS: You're already sorting faster
than Michael Phelps.
MAGNUS HYTTSTEN: That's great to know.
COLT MCANLIS: I agree.
So this is how the BWT decode works.
We append our input string across the rows of our input
table, then sort, and then continue on
until we've recovered our original matrix.
So Magnus, ready for the big one?
MAGNUS HYTTSTEN: Yeah.
Yeah, yeah!
COLT MCANLIS: All right.
So here's what we're going to do.
OK?
We're going to do this four more times--
MAGNUS HYTTSTEN: Four?
COLT MCANLIS: --so we've got six letters in each row.
MAGNUS HYTTSTEN: Wow!
COLT MCANLIS: You think you can do it?
MAGNUS HYTTSTEN: Yeah!
COLT MCANLIS: Are you ready to do it?
MAGNUS HYTTSTEN: I'm ready, ready, ready!
COLT MCANLIS: This is for the World Championship!
MAGNUS HYTTSTEN: Yeah, man!
Let's do it!
COLT MCANLIS: Ready?
MAGNUS HYTTSTEN: Yeah!
COLT MCANLIS: Set, go!
All right.
Good.
Great.
Good job.
N-N-B-A-A-A. We're going to get you so many endorsements.
You're almost there, Magnus.
Finish strong!
Ah!
Oh-oh-oh.
Man.
Great job, kid.
All right, all right, all right.
Calm down.
Why don't you hit the showers, and I'll
walk the people through the rest of the algorithm, all right?
Good job today.
Good job.
I don't think he's got a shot at that one.
Anyhow, thanks to Magnus, we've got a recreated permutation
table alongside a nifty row index
that we output during the encoding phase.
Since this matrix over there is identical
to the post-sorted one from the encoder,
the fourth row actually contains the original input string,
"BANANA."
See?
Pretty easy stuff.
Oh, and to be clear, kids, training
to be a world champion at sorting
requires a lot of practice and dedication.
So eat your vegetables and listen to your parents.
MALE SPEAKER: Take one.
COLT MCANLIS: How do you make your hair do that?
MALE SPEAKER: Lots and lots of gel.
COLT MCANLIS: Really?
I'm gel-ous, and not just because it's a pun.
Nice.
It'll take him a second.
In 1994, Mike Burrows and David Wheeler
were set up to be the title fight at the second annual UFC
championship in Las Vegas, Nevada.
But before the fight, while playing a few rounds
of pai gow, the two ended up creating
the Burrows-Wheeler Transform algorithm.
MIKE BURROWS: That isn't really true.
COLT MCANLIS: No, no.
No, it is not.
Um-- ha.
You know, one of the problems about working at Google
is you can't really throw a stone around here
without hitting the inventor of some amazing algorithm.
Ladies and gentlemen, I want to introduce you
to the co-inventor of the Burrows-Wheeler Transform, Mr.
Mike Burrows.
Mike, it's fantastic to see you.
Maybe if you have a second, can you
sit down and talk to us a little bit about your algorithm?
MIKE BURROWS: Certainly.
I'd like to put you straight about that title fight.
COLT MCANLIS: OK.
So I guess at the beginning, let's start there.
MIKE BURROWS: Well, it really started with David Wheeler.
He was on the faculty of the University of Cambridge,
but on sabbatical at Bell Labs, and working on compression.
And he came up with the algorithm there.
I only learned about it some years
later when I became his graduate student.
COLT MCANLIS: In the world of data compression,
Burrows-Wheeler Transform just stands alone
against everything else.
There's nothing really like it.
How did you all come up with it?
MIKE BURROWS: Well, I asked David
what was going through his mind when he came up with it
originally.
And he didn't know.
He could not explain to me how he came up
with that particular algorithm.
I got the impression that he was playing around
with sorting the contexts of characters
that were to be encoded and using that as a good predictor.
And then he must have realized that it
was possible to invert that sort under certain conditions.
COLT MCANLIS: Did you and Mike kind of co-create the article
together?
Was it more of his idea, and he handed it off to you?
How did that relationship work?
MIKE BURROWS: What happened was that he never
bothered writing it up.
I learned about it from him as a graduate student.
And the years ticked by after that.
And he never wrote it up.
At the time when I was a student,
I thought that it was just one of those things
that grad students learn.
And then eventually, I realized, no, this was really special,
and the world ought to know about it.
When he did it, he did not think of it as a practical algorithm.
He thought of it as an algorithm to use
to calibrate other algorithms.
It wasn't practical for him, because he didn't have
a really fast implementation.
And computers at the time were significantly slower.
And so it didn't really go fast enough.
So I decided that what I should do is write it up myself.
And in order to do that, I had to do something.
And so I worked with him to make it go fast.
And we came up with ways to implement it efficiently.
COLT MCANLIS: So I've got to ask you,
in the 20 years since this algorithm's invention, what
has been the most amazing thing you've seen it applied for?
I mean, it's been everywhere, from the Linux operating system
to a protocol on the internet.
What's impressed you so much about its use so far?
MIKE BURROWS: Well, I suppose the most unexpected thing has
been its use in DNA sequencing.
It puts together the fragments of DNA
that have been sequenced independently very efficiently
into a combined whole.
But there have been many other advances around it,
particularly in ways to do the sorting efficiently, also
variance of the transform, one that sorts only
limited-length contexts.
It turns out that Michael Schindler of the Technical
University of Vienna discovered that if you sort the context up
to any finite length k, it's still
invertible as a transform.
Unfortunately, the inversion takes twice as long,
so it's not popular.
But it still works.
David Scott and Yossi [? Azah ?] managed
to find a bijective variant of the transform, where
the size of the transform string is
exactly the same as the size of the input string.
COLT MCANLIS: So you don't need the row index at the end?
MIKE BURROWS: Yes, that's correct.
It's a bit more involved and a bit slower
to do the compression, but it still works.
And that was another surprise for me.
COLT MCANLIS: Give me a little bit of background here.
Where did you actually publish the paper originally for this?
MIKE BURROWS: There's a funny story about that.
We first of all sent the paper to the Annual Data Compression
Conference.
But they rejected it.
And there were no comments about why they rejected it.
So I wrote to them and asked why they had rejected it.
And they told me that it was their policy not to explain
why they rejected papers.
So we just published it as a technical report.
The next year, people at the same conference
actually asked me to submit the paper again so
that they could publish it.
And I said, no.
And I wasn't really going to explain why,
because it was my policy not to explain that sort of thing.
So the algorithm actually became more well known
when someone else who saw the technical report
published a popular article about it
in "Dr. Dobb's Journal."
So that was the first real publication where
people got to know about it.
COLT MCANLIS: Wow.
So just completely bypassed the academic route,
and go for mainstream media.
That's how we get our algorithms out nowadays, right?
MIKE BURROWS: That's the way it worked.
COLT MCANIS: Listen, Mike, thank you
so much for coming on and talking to us a bit
about this algorithm.
We're really honored to have you here.
MIKE BURROWS: It's a pleasure to be here.
I felt, given the state of the other "Compressor Head"
episodes, that I ought to come along personally and fix
things.
COLT MCANLIS: Huh.
OK.
Well, thank you for that.
You sure did.
MIKE BURROWS: Thank you.
COLT MCANLIS: OK.
Oh, it's on me.
Oh.
I was just texting my boss.
So it's apparent that BWT doesn't actually
compress the data, it just transforms it.
To practically use BWT, we need some way
to apply another transform that's going
to yield a stream which has lower entropy
and, thus, is more compressible.
Good old delta compression doesn't really
help us that much.
Encoding our post-BWT stream of N-N-B-A-A-A yields us
the version of the string, this whole thing,
which has an entropy of 1.77, while the source entropy itself
is only 1.45.
We haven't actually improved anything.
No, for this type of data, we need a different type
of transform which is better suited for the type of symbol
clustering that BWT produces.
We call this move-to-front encoding.
Effectively, start by creating a buffer that
contains all unique symbols that your stream could have
and list them in a sorted order.
For our purposes, we'll just use the English alphabet.
The move-to-front algorithm is pretty simple.
For each symbol we read, we write its output buffer
position and then move it to the front of our buffer.
For example, if we input the letter N,
that sits at position 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14.
So we write that to our output stream.
The next step is how the algorithm gets its name.
Once we've written its out position,
we then move that symbol to the front of the buffer.
Time to read in the next symbol, which is also
N. Since that's already at the front of our stream,
we write a 1 to the output stream.
This is the trick of the transform.
The idea is that since BWT clusters symbols together,
there's a high probability that subsequent copies
of that symbol will appear in the stream
after we've encountered the first one.
So we end up outputting more 1's as a result.
Let's take a look at the rest of the coding.
Let's read B onto the stream.
And as such, we output the index 3,
because that's where it sits in the buffer.
And move it to the front.
We next read A and output the index of 3
again, since here it sits once more.
Just fix that.
Now, the next two A's that we read
from the stream won't adjust any part of the buffer
since A already sits in the first position.
As such, we simply admit 1's to the output stream.
Now, after encoding, the output stream here is 14, 1, 3, 3 1,
1, whose entropy is 1.45, which is identical to our source
input stream.
Eh, pretty good.
From here, you can simply throw the output of move-to-front
to any statistical compressor, like Huffman
or arithmetic compression.
In fact, bzip2, the popular Linux compression application,
couples Burrows-Wheeler Transform plus move-to-front
plus arithmetic compression for its exact algorithm.
You're looking at the inner workings
of science here, folks.
[GIBBERISH]
MIKE BURROWS: That's an interesting thing to say.
COLT MCANLIS: Like, that was just really cool to hear.
MIKE BURROWS: Yeah.
Anyway--
COLT MCANLIS: All right, all right.
Yeah, sorry.
We could do this all day.
What's amazing about Burrows-Wheeler Transform
is that it stands alone as a compression algorithm.
LZ, Huffman, arithmetic-- they all have tons of variance
and have been worked on by tons of different people.
In the last 20 years, Burrows-Wheeler Transform
has gotten much less attention.
But that doesn't mean it's any less useful.
In recent competitions to compress human DNA sequences,
BWT-based compressors were all in the top 10 finalists.
And as far as the compression world goes,
there's still plenty left to improve upon here.
But that's a topic for a different show.
My name is Colt McAnlis.
Thanks for watching.
[MUSIC PLAYING]