COLT MCANLIS: In the mystical world of compression,
there's one algorithm that constantly puzzles developers.
Its ability to compress data so well
is shrouded in ancient secrets of statistical probability.
I'm talking, of course, of arithmetic compression,
the de facto statistical compressor that
has its hands in every part of the modern compression
industry.
Everything you see online, from images to videos, and even
your text data, has been sent through
its enchanted algorithm.
Writing an arithmetic compressor yourself is no easy task.
It requires you to stare into the face of the unknown
and accept what it has to tell you.
But fear not, young programmer, because I'm here to help.
My name is Colt McAnlis, and this is Compressor Head.
Now, if you remember, variable length
codes or, VLCs, take a given symbol from our input stream
and assigns a code word to it that
has a variable number of bits.
That VLC is then pushed to the output stream,
producing a compressed version of our data.
The trick is that variable length codes
produce compression that's close to entropy,
as long as the probability of your symbol distribution
matches the probability table that you've
built your VLC from.
But the trick is that VLCs are generated with a specific set
of probabilities in mind.
For example, here-- aha, there we go.
Let's take a look at Omega codes next to Even Rodeh codes.
You can see that, for these two VLC types,
they're not equal for every given value of n.
This is because of the statistical probabilities
that they've made assumptions towards.
See, Omega codes expect that there's not
going to be lots and lots of most probable symbols.
If we end up with a lot of symbols
that are close in probability or have a shared probability,
then we get into trouble.
Omega codes are weighted towards having a dominant symbol
with the most probability, while everything else trails off
in very small amounts.
Even Rodeh codes, on the other hand,
expect that the top four symbols are actually
pretty close in probability to each other.
But once you hit the eighth most probable symbol,
the code word size increases dramatically.
This expects there to be a grouping
of symbols that are pretty close and a drop off after that.
As such, you run into a problem.
What if the probability distribution
of your data stream doesn't match your chosen VLC set?
Well, in that case, you get bloat.
You'll end up with code words that are not
minimal, and as such, your compressed stream
won't be equal to entropy.
This is the trouble that most folks
have with practical implementations
of variable length codes.
Which VLC do we use for our data that
gives us the best compression?
I mean, it's not like we can iterate through every VLC
and find the best match.
I mean, that would just take way too long.
Instead, we want some way to encode
a stream that optimizes for a probability,
without having to fit some pre-existing statistical table.
And this, my friend, is where arithmetic compression
comes in.
Jorma Rissanen pr-- published--
Most standard literature that discusses
arithmetic compression puts it a little something like this.
[CLEARS THROAT] (IN ELEGANT SPEAKING VOICE)
"In contrast to VLCs, which assign a code word per symbol,
arithmetic compression assigns one code word
to the entire data stream."
Which is elegantly stated, but really
doesn't tell us anything.
I mean, what kind of code should we actually
apply to that stream?
If I'm given AZZ as an input, I can really pick any number.
I mean, if I make it 12626, that's cool, right?
But that ends up bloating the stream.
Or I can make AZZ equals 1, but how would I decompress that
later?
See, the magic of arithmetic compression
is a data transform that is applied to the source data
in order to create a single output number which
uses less bits to represent than the source stream itself.
But let's not get too far ahead of ourselves.
First, let's talk about binary search.
Am I-- am I not toitally-- toitally?
Let's say I search for the value 6 in the number range 0 to 9.
A binary search works by dividing the space in half
repeatedly, until we find our number.
So effectively, we start with low equals 0
and high equals 9, which means the number that we're checking
is the 5.
Now, if 6 is greater than 5, which it is, we erase our low
and move it around so that low is now equal to 5,
and we're checking 7.
Now, we continue doing this process of subdividing space
in half each iteration until we find the number that we're
looking for.
But now the question is, what if, instead of subdividing
our space in half each iteration,
we instead subdivide it in thirds, fourths, or 16ths?
For example, let's subdivide our number space into four parts.
And when we choose what section we're looking for,
we subdivide that into four parts as well.
This concept of subdividing the space each time
we refine our search is the basis
for how arithmetic transforms work.
Effectively, we assign a subspace
to each one of our symbols.
When we encode the symbol C from our input stream,
we subdivide C space further, assigning new symbols
to the space in the proper order.
And this continues on.
Every single input that we grab subdivides the space
into smaller and smaller subsections each step,
but with one simple modification.
Rather than subdividing our search space
into equal portions, we subdivide
it based on probabilities of the symbols in our stream,
kind of like our code word tables.
So if C is the most probable symbol, it gets the most space.
Now, in order for this to work, we need our number range
to be something that makes sense to actually be subdividing,
so I mean we can't use integers.
Instead, we will subdivide our number space
and define it existing on the range, 0 to 1.
And then that allows us to assign each symbol
an area on the word space that's equal to its probability.
And this right here, my friends, is the starting process
of how arithmetic compression works.
But enough chit chat.
Let's encode something.
So let's take an example with three symbols, R, G, and B,
with the probabilities of 0.4, 0.5, and 0.1, respectively.
Now, it's pretty easy, given the probabilities of these values,
to assign them ranges on the interval of 0 to 1.
Or perhaps there's a better way to look at this, in number line
form.
Let's encode a simple string, GGB.
First, we pull the symbol G from the input stream.
And since the interval of G, according to our table,
is 0.4 to 0.9, we then subdivide our space,
giving us the values between 0.4 and 0.9,
respectively, which sets our low and high values, 0.4
to 0.59999.
G actually ends up being 0.6 to 0.84999999.
And B ends up being 0.85 to 0.999999.
It's now time to read the second symbol from our stream.
It's a G, once again.
When we read our B value, we subdivide that interval
once again.
After encoding B, our final interval is now 0.825 and 0.85.
This is the range that we want to output as our encoded value.
Now, congratulations.
You've actually just arithmetically encoded
a stream.
Now, decoding can be viewed as the same process,
but in reverse.
Now, since our final value range is 0.825 to 0.85,
honestly, we can now put any value between those two
to our encoded stream.
So let's just randomly pick a value and say that it's 0.83.
The decoding process can be thought
of as drawing a vertical line through our subdivided ranges,
updating the intervals as we move down.
So if we start with 0.83, the symbol
for that range that it falls in is the letter G,
so we output that as our first symbol.
Then we subdivide that space.
And 0.83 once again falls in the G area,
which is our second symbol.
And finally, 0.83 falls in the B range,
which is our final symbol.
There you go, encoding and decoding
of arithmetic compression all in one nice package.
[MUSIC PLAYING]
I'm good?
Remember this guy?
Besides inventing a plethora of variable length code patterns,
Peter Elias first proposed the concept
behind arithmetic compression in the early 1960s.
It wasn't until a decade later, though,
when Jorma Rissanen published some of the first symbol
research for its implementation, alongside a massive patent.
For the next couple of decades, arithmetic compression
pretty much fell off the map due to an impossibly aggressive
patent strategy enforced by IBM at the time.
The patent problem was so aggressive
and arithmetic compression was so good
that a separate coding algorithm, called range coding,
was invented in 1979, which basically
did the same thing as arithmetic compression,
but was free from patents.
Nothing like a good government system
to stifle creativity, huh?
OK.
You know, I really don't think this is all
really that necessary.
I mean, it's just a comment on a video.
What have we got here?
We've got another signature?
Fine.
I don't even know what this says.
Initial, too.
You guys, of course, need an initial.
So really, I think that--
EULA FRUMPKINS: And here.
COLT MCANLIS: You guys need blood samples and hair
and everything else too?
EULA FRUMPKINS: Just signatures.
COLT MCANLIS: OK, fine.
Listen, I'm very busy.
Can I at least back to all this?
EULA FRUMPKINS: Let me just check.
COLT MCANLIS: You're going to check it all.
OK, thanks.
EULA FRUMPKINS: Thank you.
COLT MCANLIS: In the early 2000s,
though, the patent expired.
And arithmetic compression took off again,
allowing itself to achieve the status
of the gold standard for the current generation
of statistical encoders.
In fact, the majority of modern compression formats
for archives, like LZMA and BZIP,
audio and video, like JPEG, WEBP, WEBM, and H.264
all work with an arithmetic compression system
as its statistical compression step.
So here's the tricky part with arithmetic compression.
Why the hell does it work?
I mean, it's a simple concept, but how does it
get us close to entropy?
Well, it has everything to do with probability, distribution,
and how we subdivide our space.
So let's try to subdivide our space evenly.
If we've got 10 values and we subdivide our space between 0.2
and 0.3, we end up with 10 new ranges, starting at,
0.2, 0.21, 0.22, 0.23, 0.24, 0.25, 0.26,
0.27, 0.28, and 0.29.
Look at what just happened.
By subdividing our space, our range values
have been increased in size by one digit.
If we stopped right now, all of our outputs
would be two digits in length.
So if we subdivided any of them again,
we would end up with three digits per range.
And if we divided those regions, we'd
end up with four digits per range, and so on, and so on.
Can we--- let's move it really quick.
Fantastic.
Thank you, so much.
All right.
Now, let's subdivide that space unevenly
and, just for the sake of argument,
give one range 9/10 of the space.
So we'd end up with the starting spaces of 0.2, 0.291, 0.292,
0.293, 0.294, 0.295, 0.296, 0.297, 0.298, and 0.299.
Now, look at that.
Every time we fall in this first range, going from 0.2 to 0.291,
we're outputting less digits to the output stream.
At best, we could simply use the lower bound
of 0.2, which is less digits than any other starting
value in our range.
And at best, we don't end up outputting any new digits
to our output code at all.
Even if we're 10,024 levels deep into the subdivision tree,
picking this first range will output less digits
to our output, and at best cases,
won't put out any new digits at all.
This skewing of unit space based on the probability
of the symbol is the core idea that
makes arithmetic compression a statistical compressor.
Effectively, the more probable the symbol,
the less digits it outputs to our encoding.
Props.
When all the dust settles, arithmetic compression
can consistently get close to entropy
for arbitrary streams, regardless of the data type
or the probability of its symbol distribution.
It's single minded focus makes it a Swiss army knife
of statistical compression.
But there's a large battle between Huffman
and arithmetic in the minds of compression programmers
out there.
Some claim that the Huffman king is dead, long live arithmetic
compression, while the true believers claim
that the king is alive and well, living
under the alias, dynamic Huffman encoding.
But that's for a different episode.
My name is Colt McAnlis.
Thanks, for watching.
[MUSIC PLAYING]