Good morning everybody.
I will show you how I program a visit to data compression encoder in Ada from scratch during
two rainy weekends.
So, my motivation was fun, first of all, a challenge, a bit of a warm-up for advent of code,
the latest.
On the more serious notes, I wanted to fill a gap in the zip-aid library, which is a visit to encoder
was missing.
There was a decoder right to the yellow cell, but there was no encoder.
It was absolutely this gap needed to be filled.
And my expectations were quite low because this visit to a skin from experience compresses
not a lot of kind of files better than for instance at the DMA.
The algorithm is mostly mechanical.
So, on most steps, you have only one way to encode the data.
But not all steps.
And the visit to is a week in version of first visit, so it's very older.
At the time, there were patterns about arithmetic encoding.
And the older had to change to human trees.
But the results of my programming exercise were absolutely surprising.
So, I got two very good surprises.
Of course, I keep them from the end.
So, I will explain you the visit to compressing skin in 15 minutes.
Some people are skeptical.
Now, actually, the visit to is completely unusual as a compressing skin.
It's super simple.
I promise you, it's simple.
First of all, it's not a streaming and adaptive skin.
It doesn't use sophisticated technique.
You have twice run length encoding, which is the most trivial way of compressing data.
Just repeated sequence of exactly the same symbols.
And a few of the techniques.
So, once you have treated your block on step 2, you output everything in one go.
So, it's basically a offline algorithm.
You see, in the green box, the ADA code, of course, is missing in the red ellipse.
A few hundred offline.
But basically, you have all the steps with these codes.
It's super simple.
For instance, the one of the run lengths encoding, you don't even have a very smart.
You don't even have a special symbol to say, ah, now they are run.
Automatically, after four symbols, you have a extra bite, saying ah, you have a run,
and with the length, the extra length.
So, it's very smart, and you have a game from the sixth symbol.
Now, the core of the visibility to algorithm is a mysterious transform called Burroughs Wheeler,
which is a bit, yeah, the history is also funny.
I don't go into details, but basically, you take the blue,
message on the top left, you shift it as you see in the left box.
You sort all the lines, the red box contains the results of the sorting,
and you output the red column, the rightmost column.
That's the output of this transform.
That's as simple as it is.
The fascinating thing is that you can reverse this transform.
So, this letter soup on the right can be reversed.
If you know the index of the original sentence.
So, basically, you don't compress anything, and you just,
you also have an extra information, which is an integer.
And you wonder, what does it have to do?
With data compression, the data on the right, the red thing.
It doesn't look, in this example, more compressed or compressible or whatever,
than the blue message.
But let's have a look on a larger example.
So, here I take the source code of the encoder itself, as a test data,
and you see there are lots of repetition, which this transform.
And that's, of course, the reason you can do compression with that.
You have lots of repetition, so you can do again run length encoding.
And before the run length encoding, you do move to front transform,
which is again super simple.
Imagine you have a card deck, which is sorted at the beginning.
And if you take the card number six, you have the index number six,
because the original sorting.
And after it becomes a bit more complicated,
because the card are progressively shuffled,
but the interesting feature, the cards that appear more often,
have a lower index, and that's very prone to compression.
For instance, card number six appears,
after the third time the index is lower.
And the final step, here it's a bit smarter,
and it's more difficult.
It's the entropy coding, so it's compression with Huffman trees.
So, the author of this scheme had the bright idea to not have a single entropy
code, you can choose between two to six Huffman trees,
which are completely, freely defined, of course,
try to do it efficiently.
And also for each group of 50 symbol,
you can allocate one of these two to six trees.
So here, you have lots of room for optimization.
It's where the lemons are squeezed properly.
So the results of my exercise,
after the last rainy Sunday,
to say it's polarity, I would say,
what the, okay, but there's a camera, so, like,
Holy cow, so on the third bar, you see,
the compression of the original visit to scheme,
the one that you find everywhere, especially on Linux.
So here, to the zip utility, it's using this algorithm,
if you take the right switch.
In the middle, you have seven zip.
You know, everybody use seven zip,
so if you tell it,
ah, take a zip tube, encoding, here you go,
and on the left, here is the compression
with the new encoder and I just vote.
So it was totally surprised that it's compressed better
than these tools that are developed for decades.
Yeah.
To be mentioned, again,
this is too, it's very good for human written text,
like ebooks and also source code,
of course not automatically generated source code,
but human written source code.
And less good for other things,
but for these things,
it's very good in general,
and surprisingly, my implementation is better.
And the second surprise,
what happens if you have a mix of different data types?
So you have many benchmark data,
test data, called corpus,
like the classic cuntorberry,
where you have images on other kind of things,
or also source code on ebooks.
And the second surprise was that even in this context,
by using the zip aider pre-selection option,
which picks the right algorithm depending on the data type,
the overall archive size is smaller
than not only seven zip with the maximum compression
for zip archive,
but also the second bar on the bottom box,
with the seven Z archive,
which combines all the files together.
So it was also a super rejoicing surprise there.
And so, what are the things we are in the Edda Devroom?
What are the benefits of Edda,
except that you can make a winning encoder
in two days, in three days, so quickly.
And I would say, regarding data compression,
it's very difficult to debug.
If you have a bug, you almost have to start from scratch,
because the output is random,
so a wrong random doesn't look like better
than a worse than the good random data.
And really Edda does its best to do the things right the first time.
It finds tons of dumb mistakes, programming mistakes.
And if you use the customizable,
you can create as many custom types as you want,
so I've listed range types in the box here.
And also, if you use these types,
you cannot mix two easily and index with an element
and this takes you sometimes to.
Plus, you can define certain types with range types,
which are very tailored, made range.
And in compression, you always have very strictly
delimited ranges, so it's perfect for that.
And the two of the types listed there are data dependent,
so it depends on the data you are compressing.
So it's kind of, you actually have dynamic types in Edda,
so they are, they depend on some data features.
So that's it. Questions?
So I was, so yeah, runtime and memory usage.
I was not too, I didn't try to save too much in memory.
So you have a few megabytes of memory usage.
You could squeeze it to perhaps one megabytes by reusing things.
But nowadays a few megabytes, it's not so, yeah.
So how does it scale?
This format is by design limited to 900 kilobytes.
Because there is a reason because you remember
the strings that were sorted, the sorting of these strings
explodes with the size.
So you have to slice your data into maximum 900 kilobytes.
So it's very easy with memory.
You can allocate as you want.
You don't need to spare too much.
But runtime, there's some improvements to do.
I'm using the standard Adda sorting,
and I should use more specialized sorting for that.
But it's for later.
It runs conveniently fast on most data I would say.
Similar to 70.
When you say 900 kilobytes, it's the window.
No, it's not that you take the first 900 kilobytes.
You process it.
You take the next and so on.
It's very special.
It's not a streaming compression scheme.
It's really you take a block.
You process it offline.
You output it and so on and so on.
Yeah, question?
The white?
The first one.
The white.
The size.
The just on the.
So this one, it just bites.
Compress bites.
Of course, it doesn't go from zero, but you cannot compress two zero as well.
So up, one minute left.
So I have to wait when we're in it.
So I can start with the next one.