The simplest compression algorithms: RLE and LZ77

Once upon a time, when I was still a naive schoolboy, I suddenly became terribly curious: and how magically the data in the archives take up less space? Riding my faithful dialup, I began surfing the Internet for an answer, and I found many articles with a fairly detailed account of the information I was interested in. But then none of them seemed to me simple to understand - the code listings seemed to be Chinese, and attempts to understand unusual terminology and various formulas were unsuccessful.

Therefore, the purpose of this article is to give an idea of ​​the simplest compression algorithms to those for whom knowledge and experience do not yet allow them to immediately understand more professional literature, or whose profile is completely far from such topics. Those. I will “on fingers” talk about some of the simplest algorithms and give examples of their implementation without kilometer code listings.

I’ll warn you right away that I won’t consider the details of the implementation of the encoding process and such nuances as the efficient search for string entries. The article deals only with the algorithms themselves and how to present the result of their work.

RLE - compact uniformity

The RLE algorithm is probably the simplest of all: its essence is to encode the repetitions. In other words, we take sequences of identical elements and “collapse” them into quantity / value pairs. For example, a string like “AAAAAAAABCCCC” can be converted to a record like “8 × A, B, 4 × C”. That, in general, is all you need to know about the algorithm.

Implementation example

Suppose we have a set of some integer coefficients that can take values ​​from 0 to 255. In a logical way, we came to the conclusion that it is reasonable to store this set as an array of bytes:

unsignedchar data[] = {
	0,   0,   0,   0,   0,   0,   4,   2,   0,   4,   4,   4,   4,   4,   4,   4,
	80,  80,  80,  80,  0,   2,   2,   2,   2,   255, 255, 255, 255, 255, 0,   0
};

For many, it will be much more familiar to see this data in the form of a hex dump:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

After thinking, we decided that it would be nice to compress such sets in order to save space. To do this, we analyzed them and revealed a pattern: very often come across subsequences consisting of the same elements. Of course, RLE is just the right fit for this!

We encode our data using freshly obtained knowledge: 6 × 0, 4, 2, 0, 7 × 4, 4 × 80, 0, 4 × 2, 5 × 255, 2 × 0.

It's time to somehow present our result in a computer-friendly way. To do this, in the data stream, we must somehow separate the single bytes from the encoded chains. Since the entire range of byte values ​​is used by our data, it will simply not be possible to select any ranges of values ​​for our purposes.

There are at least two ways out of this situation:

1. As an indicator of a compressed chain, select one byte value, and in case of a conflict with real data, screen them. For example, if we use the value 255 for “official” purposes, then when this value is met in the input we will be forced to write “255, 255” and use a maximum of 254 after the indicator.
   
2. To structure the encoded data, indicating the number of not only repeated, but also subsequent single elements. Then we will know in advance where what data is.
   

The first method in our case does not seem effective, so, perhaps, we will resort to the second.

So, now we have two types of sequences: chains of single elements (like “4, 2, 0”) and chains of identical elements (like “0, 0, 0, 0, 0, 0”). In the “service” bytes, select one bit for the sequence type: 0 — single elements, 1 — identical. Take for this, say, the most significant bit of a byte.

In the remaining 7 bits, we will store the lengths of the sequences, i.e. the maximum length of the encoded sequence is 127 bytes. We could allocate, for official needs, two bytes, but in our case such long sequences are extremely rare, therefore it is easier and more economical to simply break them into shorter ones.

It turns out that in the output stream we will first write the length of the sequence, and then either one repeated value or a chain of non-repeating elements of the specified length.

The first thing that should catch your eye - in this situation, we have a couple of unused values. There can be no sequences with zero length, so we can increase the maximum length to 128 bytes, subtracting one from the length during encoding and adding during decoding. Thus, we can encode lengths from 1 to 128 instead of lengths from 0 to 127.

The second thing to notice is that there are no sequences of identical elements of unit length. Therefore, we will subtract one more unit from the value of the length of such sequences during encoding, thereby increasing their maximum length to 129 (the maximum length of a chain of single elements is still equal to 128). Those. chains of identical elements with us can have a length of 2 to 129.

We encode our data again, but now in a form that is understandable for a computer. We will write overhead bytes as [T | L], where T is the type of sequence and L is the length. We will immediately take into account that we write the lengths in an altered form: at T = 0 we subtract one from L, at T = 1 we take two.

[1 | 4] , 0, [0 | 2] , 4, 2, 0, [1 | 5] , 4, [1 | 2] , 80,[0 | 0] , 0, [1 | 2] , 2, [1 | 3] , 255, [1 | 0] , 0

Let's try to decode our result:

• [1 | 4] . T = 1, then the next byte will be repeated L + 2 (4 + 2) times: 0, 0, 0, 0, 0, 0.
• [0 | 2] . T = 0, so just read L + 1 (2 + 1) bytes: 4, 2, 0.
• [1 | 5] . T = 1, repeat the next byte 5 + 2 times: 4, 4, 4, 4, 4, 4, 4, 4.
• [1 | 2] . T = 1, repeat the next byte 2 + 2 times: 80, 80, 80, 80.
• [0 | 0] . T = 0, read 0 + 1 bytes: 0.
• [1 | 2] . T = 1, repeat the byte 2 + 2 times: 2, 2, 2, 2.
• [1 | 3] . T = 1, repeat the byte 3 + 2 times: 255, 255, 255, 255, 255.
• [1 | 0] . T = 1, repeat the byte 0 + 2 times: 0, 0.

And now the last step: save the result as an array of bytes. For example, a pair [1 | 4] , packed in bytes, will look like this:


As a result, we get the following:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

So in a simple way on In this example of input data, we got 18 from 32 bytes. A good result, especially when you consider that on longer chains it can turn out to be much better.

Possible improvements

The effectiveness of the algorithm depends not only on the algorithm itself, but also on how it is implemented. Therefore, for different data, different coding variations and representations of the encoded data can be developed. For example, when encoding images, you can make chains of variable length: select one bit for the indication of a long chain, and if it is set to one, then store the length in the next byte too. So we sacrifice the length of short chains (65 elements instead of 129), but then we give the opportunity to encode chains up to 16385 elements in length with only 3 bytes (2 ¹⁴ + 2)!

Additional efficiency can be achieved by using heuristic coding methods. For example, we code the following chain in our way: "ABBA". We get " [0 | 0] , A,[1 | 0] , B, [0 | 0] , A ”- ie We turned 4 bytes into 6, inflated the source data as much as 1.5 times! And the more such short alternating heterogeneous sequences, the more redundant data. If we take this into account, we could encode the result as “ [0 | 3] , A, B, B, A” - we would spend only one extra byte.

LZ77 - brevity in repetition

LZ77 is one of the simplest and most well-known algorithms in the LZ family. Named in honor of its creators: Abraham Lempel (Abraham L empel) and Jacob Ziva (Jacob Z iv). The numbers 77 in the title mean the year 1977, in which an article was published describing this algorithm.

The basic idea is to encode the same sequence of elements. That is, if in the input some chain of elements occurs more than once, then all subsequent occurrences of it can be replaced with “links” to its first instance.

Like the rest of the algorithms in this family of the family, the LZ77 uses a dictionary that stores previously encountered sequences. To do this, he applies the principle of so-called “Sliding window”: an area always in front of the current coding position, within which we can address links. This window is a dynamic dictionary for this algorithm - each element in it has two attributes: position in the window and length. Although in the physical sense it is just a piece of memory that we have already encoded.

Implementation example

Now let's try to encode something. We will generate some suitable string for this (I apologize in advance for its absurdity):

“The compression and the decompression leave an impression. Hahahahaha! ”

Here is how it will look in memory (ANSI encoding):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20   The compression
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65   and the decompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69   ssion leave an i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68   mpression. Hahah
0040: 61 68 61 68 61 21                                 ahaha!

We have not yet decided on the size of the window, but we will agree that it is larger than the size of the encoded string. Let's try to find all duplicate character strings. A chain is a sequence of characters longer than one. If a chain is part of a longer repeating chain, we will ignore it.

“The compression and t [he] de [compression] leave [an] i [mpression] . Hah [ahahaha] ! ”

For the sake of clarity, let's look at a diagram where the correspondence of repeated sequences and their first occurrences is visible:



Perhaps the only unclear moment here is the sequence “Hahahahaha!”, Because the string of characters “ahahaha” corresponds to the short chain “ah”. But there is nothing unusual here, we used some technique that allows the algorithm to sometimes work as described earlier by RLE.

The fact is that when unpacking we will read the specified number of characters from the dictionary. And since the whole sequence is periodic, i.e. the data in it is repeated with a certain period, and the symbols of the first period will be directly in front of the unpacking position, then we can recreate the whole chain from them, simply copying the symbols of the previous period to the next.


We figured it out. Now we replace the found repetitions with references to the dictionary. We will record the link in the format [P | L], where P is the position of the first occurrence of the chain in the string, L is its length.

“The compression and t [22 | 3] de [5 | 12] leave [16 | 3] i [8 | 7] . Hah [61 | 7] ! ”

But do not forget that we are dealing with a sliding window. For a better understanding, so that the links do not depend on the size of the window, we will replace the absolute positions with the difference between them and the current coding position.

“The compression and t [20 | 3] de [22 | 12] leave [28 | 3] i [42 | 7] . Hah [2 | 7] ! ”

Now we just need to subtract P from the current encoding position to get the absolute position in the string.

It's time to determine the size of the window and the maximum length of the encoded phrase. Since we are dealing with text, it is rare when there will be particularly long repeating sequences in it. So, let's select 4 bits for their length - a limit of 15 characters at a time is quite enough for us.

But it depends on the size of the window how deeply we will look for the same chains. Since we are dealing with small texts, it will be just right to supplement the number of bits we use with up to two bytes: we will address links in the range of 4096 bytes, using 12 bits for this.

From our experience with RLE, we know that not all values ​​can be used. Obviously, the link can have a minimum value of 1, therefore, in order to address backward in the range 1..4096, we must subtract one from the link when encoding, and add back when decoding. The same with sequence lengths: instead of 0..15 we will use range 2..17, since we do not work with zero lengths, and individual characters are not sequences.

So, imagine our encoded text with these amendments:

“The compression and t [19 | 1] de [21 | 10] leave [27 | 1] i [41 | 5] . Hah [1 | 5] ! ”

Now, again, we need to somehow separate the compressed chains from the rest of the data. The most common way is to use the structure again and directly indicate where the data is compressed and where not. To do this, we will divide the encoded data into groups of eight elements (characters or links), and before each of these groups we will insert a byte, where each bit corresponds to the type of element: 0 for the character and 1 for the link.

We divide into groups:

• "The comp"
• "Ression"
• "And t [19 | 1] de"
• " [21 | 10] leave [27 | 1] "
• "I [41 | 5] . Hah [2 | 5] »
• "!"

We compose the groups:

" {0,0,0,0,0,0,0,0,0} The comp {0,0,0,0,0,0,0,0,0} ression {0,0,0,0, 0,1,0,0} and t [19 | 1] de {1,0,0,0,0,0,0,1,0} [21 | 10] leave [27 | 1] {0,1,0 , 0,0,0,0,1,1} i [41 | 5] . Hah [1 | 5] {0} ! ”

Thus, if during unpacking we encounter bit 0, then we just read the character into the output stream, if bit 1, we read the link, and from the link we read the sequence from the dictionary.

Now we just have to group the result into an array of bytes. Let us agree that we use bits and bytes in order from highest to lowest. Let's see how links are packed in bytes using an example[19 | 1] :



As a result, our compressed stream will look like this:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #The comp # ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t ## de ### l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave ## # i ##. Hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 00   ###!

Possible improvements

Basically, everything that was described for RLE will be true here. In particular, to demonstrate the usefulness of the heuristic approach in coding, consider the following example:

“The long goooooong. The loooooower bound. "

We find sequences only for the word" loooooower ":

" The long goooooong. The [lo] [ooooo] wer bound. ”

To encode such a result, we need four bytes per link. However, it would be more economical to do so:

“The long goooooong. The l [oooooo] wer bound. ”

Then we would spend one byte less.

Instead of a conclusion

Despite its simplicity and, it would seem, not too much efficiency, these algorithms are still widely used in various areas of the IT sphere.

Their plus is simplicity and speed, and more complex and efficient algorithms can be based on their principles and their combinations.

I hope that the essence of these algorithms described in this way will help someone understand the basics and start looking in the direction of more serious things.