[MUSIC PLAYING]
JOANNA SMITH: See?
It doesn't work.
COLT MCANLIS: That's weird.
Well, wait a minute.
No, those numbers aren't exactly accurate.
JOANNA SMITH: No, that is exactly accurate.
The bald guy in the Compressor Head videos
told me that that would be accurate
when he told me to use variable length
codes for my compression, that that
would give me close to entropy, but what
I have here is nonsense.
COLT MCANLIS: OK.
Hold on.
OK.
So the algorithm's fine.
JOANNA SMITH: No, the algorithm's not fine.
COLT MCANLIS: The date is set.
JOANNA SMITH: Your job is to teach algorithms
and how are you still employed here because this is bad.
This is a ignorant.
David Huffman would be turning in his grave right now.
COLT MCANLIS: Ah, but you do know who David Huffman is.
See, my job--
JOANNA SMITH: Oh, so that's point?
The point is to learn names and not to learn compression?
You're just name dropping now?
I thought you were going to teach people algorithms.
I don't have time for bad ones.
COLT MCANLIS: OK.
We're competing with cats on the internet.
We don't have the full amount of time
to go through the algorithm--
JOANNA SMITH: To tell the story?
The punchline?
The thing that works?
COLT MCANLIS: We need to get everything in one little--
JOANNA SMITH: Everything into one video that be a complete
and teach people how to do things because that's
your job, to teach.
Is it not?
COLT MCANLIS: OK.
So there's other parts of the algorithm
that we didn't get a chance to do last time.
JOANNA SMITH: The people in the camera
need to know the whole algorithm.
You need to tell them.
Tell them.
COLT MCANLIS: OK.
So what do you want me to do?
JOANNA SMITH: Tell them.
I want you to go and do your job and tell them
exactly how to succeed with compression.
COLT MCANLIS: Fair enough.
So--
JOANNA SMITH: Oh, wait.
No.
Your intro.
Sorry, one little thing.
The fear not, young programmers thing, that's insulting.
Young programmers aren't afraid.
COLT MCANLIS: But that's my bit.
JOANNA SMITH: It's your bit?
It's wrong.
It's insulting.
It's mean.
COLT MCANLIS: Fine.
My name Colt McAnlis and this is Compressor Head.
[MUSIC PLAYING]
You know, by now I think that we've all
understood that variable length codes aren't exactly optimal.
Consider if you wanted to compress
all of the books in English Dictionary, all 26 volumes.
Sure, we could just run through, create
a VLC for the whole thing, and then compress it,
but that's just not optimal.
See, the single tome for words that start with Q
would have generally more Q's in it than any
of the other tomes combined.
As such, the efficiency of codes used for the other books of A
and Z would be offset by the abundance of Q's in the tome
of Q's.
Sounds like my new band.
Anyhow, sure you could, with the right foreknowledge,
simply compress 26 separate streams,
but we can't assume that all data streams
will be so well behaved.
What we really need is a way to encode our data that
takes locality into account, but it's almost impossible for us
to pick those dividing points given the fact that we're
taking the whole stream from a high level view.
The trick is this, we don't pick a split point ahead of time.
Now instead we use a dynamic method
of encoding that let's us know when
we should be splitting our stream appropriately.
And this, my friends, is the definition
of adaptive statistical compression.
It's a crazy algorithm that lets your coding stream reset itself
if things get too out of hand.
So let's take a look.
Break.
Go.
Now typically there are three stages
to a statistical compressor.
Number one, walk through the stream
and calculate probabilities.
Number two, assign variable length codes
to symbols based on their probability.
And then number three, walk back through the stream and output
the appropriate code word for each symbol.
It basically means you have to do
two passes through the stream and have one VLC table
for the entire set of data.
Now the adaptive version of this collapses all three steps
into a single one.
The key to that functionality lies
in the symbol to code word table not being
set in stone as we're encoding.
Instead it updates itself as we encounter symbols.
Basically it works like this.
Read in a symbol, output it's variable lengths code,
and then update the VLC table.
But this is a little complex.
Let's try to look at an example.
Let's say we've got a VLC table that looks just like this.
Now let's say we read in the next symbol
from our input stream, which is a B,
so we would then output the 1 0 value to our output stream.
And we would need to then go and update our probabilities.
The next symbol, again, is a B. So we once again
output a 1 0 to the output stream.
And we're going to go ahead and update our probabilities
one more time.
So let's see this goes to 40% here and this goes to 50% here,
and one doesn't need to be used.
Now notice what happened here though.
Since B suddenly became the dominant symbol
it now should have the shortest code word.
So this should go to 1 0.
This should go to 0.
And this should stay at 1 1, well,
we got an extra sticky out of it.
So if the next symbol we read off the line was actually
a B 0 would be output to our output stream,
rather than the 1 0 before.
This allows our stream to dynamically update and reassign
the shortest symbols to the most probable code words,
even as the frequencies change in our encoding process.
Now the decoder will work in the opposite form.
It reads the variable length code,
checking each step against its current table.
Once it finds what it's looking for it emits a symbol,
updates the VLC table, and then continues on.
Now let's look at that in action.
So we say we've got this updated VLC table here.
Let's get of these.
We don't need those anymore.
Let's say we've got this VLC table and we read in a 1 0
from our stream to decode.
Of course, this then translates to emitting a B to our output
stream.
And we need to, of course, update our probability
since we've seen a new symbol.
This goes to 40%.
This goes to 50% and this goes to 10% once again.
And once again B actually has become the most dominant symbol
and we need to change our code words accordingly.
So this should go here.
This should go here.
And this should go here.
And look at that.
As long as our decoder is updating its symbol table
in the same fashion that the encoder is
the two will always be in sync.
This is the basic process of how adaptive statistical coding
works.
The encoder and decoder are both dynamically
updating their probability tables for symbols,
which affects compression.
This is a very simple idea in theory,
but you need two other items to make it work right.
[LAUGHTER]
JOANNA SMITH: That was unfair.
[LAUGHTER]
COLT MCANLIS: But one caveat here
is what happens when we encounter a symbol that we
haven't seen before.
There's effectively no entry in the VLC table
for us reference so we can't directly admit a symbol.
I mean, we could hypothetically update our table first,
so then we could output a 1 1 to the output stream,
but this actually creates another whole problem
too because the decoder itself would get super confused.
I mean, it would see the 1 1 on the output stream
and think it's two B symbols in a row,
since it hasn't been told to update the VLC tables.
So we'd need some way to signal the decoder
to add a new symbol to the stream
before updating its table so we can
stay in sync with the encoder.
This can be done with the help of a new code that
can be admitted to our stream.
Anytime we encounter a new symbol
we output a literal code to the output,
followed by the 8-bit ASCII of our input symbol.
Only after this point do we update the stats in our VLC
table, but the lingering question is what should we
use for the value of literal?
I mean we can't just choose a random set of bits or anything
that violates the prefix rule.
Instead what we have to do is initialize out VLC table
with a fake symbol that represents literal.
When we encounter a symbol from the token stream
that we haven't seen before we first output
a VLC for the literal token followed by the eight bits
for the new symbol.
And then just like normal we have to go through and update
our table and probabilities accordingly,
reducing the probability of the literal symbol.
The decoder, when it sees the literal token,
will first read in the next eight bits
and add the symbol to the table and update the probabilities
accordingly.
Effectively this allows our encoder and decoder
to handle adapting to new symbols
that they haven't seen before.
That's good.
Ow. [BLEEP] dude.
Now as we've talked about before,
as your adaptive stream adjusts to new symbols that
are being added to it the code word lengths will change
and you'll eventually hit a point
where the output stream is diverging
from the suggested entropy by a specific amount.
For example, let's take this phrase here.
As we're encoding it we can track the suggested entropy
against the results of an adaptive VLC implementation.
Now in order to allow our stream to effectively split itself
for better compression we need to allow
it to define a point in which you can reset itself
so that future sections can get better encoding.
Now you can see that for this example string
we end up with the encoded output where each symbol is
about 1.1 bits larger than the suggested entropy,
resulting in a stream that's 26 bits larger than it should be.
But the truth is that if we split the string in half
and encode each one separately, we'd
end up with a lower entropy and smaller encoded output, which
yields a stream that's only 22 bits larger than the suggested
entropy stream.
To do this we employ the same tactic
that we had with the literals and create a reset token
in our variable table.
Any time this symbol exists in the stream
it signals the encoder or decoder
to reset its current VLC tables and start fresh,
which is pretty straightforward.
However, the real trick then is knowing
when to emit a reset token.
See, as we're outputting code words
we can keep track of the suggested entropy of the input
stream and the actual bits per symbol of the output stream.
If the output size starts diverging
from entropy by a significant amount
we can use this cue to emit a reset token, at which point
the stream resets and starts fresh just like normal.
Applying this technique for large streams
is critical to ensure that you're
staying as close as possible to entropy even
though the probability of the symbols
will change as you process more symbols on the stream.
JOANNA SMITH: I mean, this--
Well, that works.
COLT MCANLIS: See?
I told you.
Listen, it was never a the algorithm.
It was all about the data set.
By taking advantage of the locality of our data
we're able to optimize the tables more efficiently, which
means that we're going to get better compression.
This is the whole point of a dynamic statistical-- wait.
Where are you going?
I mean, we've got to talk about the dynamic Huffman
and dynamic arithmetic--
JOANNA SMITH: Some of us have real work to do.
COLT MCANLIS: Oh.
Well, thanks for stopping by.
JOANNA SMITH: Grow some hair.
COLT MCANLIS: My name is Colt McAnlis.
Thanks for watching.
[MUSIC PLAYING]