Compression technology is everywhere in our life, hard disk storage data, send TV signals, web transmission, streaming media, video games… There is hardly a significant area of modern computing that does not use compression.

So what exactly is compression technology?

Whether you’ve been using computer compression software for years or never thought about it, this article will try to explain what happens to the data in a file or video when you compress it. We will seek answers to these important questions, and may raise some new ones in the process.

  • What does it mean to compress a compressed object?
  • How can I make the target object smaller than it was before?
  • How to implement compression technology

Let’s answer them all!

via GIPHY

Basic knowledge of

Before looking at compression techniques and digital information, here is an easy-to-understand introduction to compression techniques. Let’s take a look at the letters below:

Look at the characters we use to represent the word (Tree). They add up to four:

It looks ok. What happens if we use Chinese characters?

Oh my god! Only one character! Did we change the meaning or any message? Don’t. However, we reduced the page space by 75% to represent the meaning of “tree”. So what did we do?

There’s nothing magical about it — we’re just saying it in a different way. We chose a different, more efficient way of presenting information. Spoiler: Here is the most important part of this article, please read it carefully.

What about pixel-level images?

You may wonder how the above example can be applied to rigorous digital image data. Let’s take a look at one of the most popular types of data these days — pictures. For now, let’s start with simple pixel-level images, rather than trying to compress a high-resolution Instagram image or other similarly complex images.

Not very pretty, is it? Because I drew it myself. Above is a 10 by 10 grid, where each color can be represented by a character in ‘B’, ‘Y’ and ‘G’.

How do we digitally represent the image above? A file that stores the image in its original form might contain the following:

All we did was write a character for each pixel that represented its color from left to right and top to bottom. As you might expect, there will be 100 characters. Let’s assume that these 100 characters take up 100 bytes on the hard disk. This storage method defines a reasonable upper limit of the storage file size. Any other storage method that is larger than the above is meaningless, or attempts to store information other than image data (such as metadata or other data). I think you can agree with me on that.

Before you look down, use your brain. If I asked you to represent this image in less than 100 characters, what would you do? Have a cup of tea, think it over, I’ll be waiting for you.

Do you have any ideas? Good. I got one of those.

I’m going to name my method Stroke Length Compression Algorithm (RLE). I’m just kidding. I didn’t come up with this method, nor did I name it. It has been a basic compression technique since at least the sixties. I bet some of you just figured it out.

We apply the stroke length compression algorithm to the image above. At the top, we write a series of characters in the same color. Let’s start with the ‘B’ characters. So can we compress these repeated characters?

Of course you can! Get rid of the following:

Instead:

Looks like it might work. By abbreviating a long string of identical characters, we have reduced the 17 characters to three. By the way, we call these repeated strings runs. Therefore, the stroke length compression algorithm is to compress and encode the data by recording the length of runs rather than each character. No information is lost in this compression. The program that was able to parse the previous file, with a little modification, can parse our new file format. The pictures should be the same.

The live demo below shows the raw image and its two storage encodings: the raw version and the stroke-length compression encodings.

By clicking on any pixel, you can change its color, as well as the stored characters below.

Editor’s note: English texts have Demo here, in this paper, not reproduce, at https://unwttng.com/compression-decompressed, please check.

As you change the pixel color of the original image, you’ll see that the scale we can compress depends on the image itself. If the whole image has only one color, or if the contiguous area of color is long, we can get very small output. The minimum memory size that can be obtained using the stroke length compression algorithm is 4 bytes:

Of course, this algorithm can also perform badly in certain scenarios. In fact, files compressed using this algorithm can be larger than the original pixel-by-pixel representation. You’ll notice that it uses 2 characters when you need to represent ‘1B’ or ‘1G’. What happens if the continuous length of each color in your pixel image is only 1?

Surprise you.

It’s time to learn some terminology.

The compression ratio

How do we measure how much our compression algorithm actually shrinks the data? You might have guessed it — calculate the size ratio before and after compression.

For example, if we use the algorithm to compress a pixel image from 100 bytes to 42 bytes, we calculate a compression ratio of (100/42) ≈ 2.38. The best case is the image with only one color, and the compression rate of this algorithm is as high as (100/4) = 25! However, when the algorithm is applied to images with only 1 continuous length of each color, the compression ratio is only (100/200) = 0.5. Protip: Compression of less than 1 sucks.

We can see that the compression rate of this basic RLE algorithm is very sensitive to the data structure of the input. This is common for simple algorithms of this kind. The algorithm makes some assumptions about the structure of the data. In order for the algorithm to output the desired results, the same bytes must exist in the original input data which are repeatedly adjacent. A more intelligent implementation of the RLE algorithm might try to compress and encode the data using repeated substrings.

Even if I describe the image directly in English, the compression rate is greater than 2! Using this method, we can compress and store data in a friendly, concise file format, which is a small step forward from our first attempt.

How small can data be compressed?

That’s a big, broad question. Of course, it is assumed that a properly designed compression algorithm should compress at least a little (both colloquially and academically) of any input data.

Unfortunately, it’s not that simple. Suppose we have an algorithm A that, for any input, keeps the compression rate strictly greater than 1. For some inputs, the compression rate can be 2.5; For other inputs, the compression rate might be 1.000000002.

If such an algorithm exists, we can call it with infinite iterations. For an input, we evaluate A(A(A(data))), calling A() over and over again for each output. Every time we call it, the size of the data gets compressed at least a little bit. And it’s not hard to see that at the end of the day, we can compress the data down to one byte, or even zero bytes, right?

That doesn’t seem realistic. And so it is. We don’t even need to use recursion to prove the algorithm works. Imagine a situation where there are nine different files, and there is no way to compress all nine files to three bytes without losing data.

Three bytes can represent only eight different types of data: 000, 001, 010, 100, 011, 101, 110, 111. Even if we had some very powerful compression algorithm that could compress the first eight files into each of the first eight byte representations, the ninth file would compress only one of them. For this algorithm, no more than 8 uncompressed data fragments can be found to represent more different 3 bytes.

There is an important principle here: there is a strict limit to the compression rate of any algorithm for common data compression. You can compress data with one algorithm over and over again until you can’t compress it any smaller, and then try another algorithm. This may compress the data even smaller (in fact, a lot of software online does this), but eventually, you’ll run into data that you can never compress again. In fact, when you repeatedly call different algorithms, you end up with just another compression algorithm. This rule still applies today.

Coriolis complexity

You may be even more disappointed by what follows. There is not only an algorithmic theoretical limit to the size of the compression rate – the complexity of the data itself can also have a significant impact

Let’s look at the following two strings:

And:

The two are exactly the same length, but you can easily see that the latter is obviously more complicated. More specifically, using the RLE compression algorithm, we can compress the first string to up to 3 characters (” 24A “).

Koch’s complexity (a brilliant invention of Andrey Nikolaevich Kolmogorov, a Soviet mathematician) makes this point perfectly. Of course, there are many ways to measure one thing, and Coriolis complexity is a good way to measure it. The Coriolis complexity of the data is the shortest length that can be output by a computer program to describe the string.

Obviously, for Corleone complexity, the upper bound on the length of any string ‘S’ is itself. That simplifies the algorithm a bit, but the data’s Coriolis complexity also needs to be added to the length of the entire program — including the interpreter or compiled code. But for the scope of this article, that’s not necessary. Just think of it as the shortest length you can generate for that data.

Coriolis complexity is not very sensitive to what programming language you choose. The choice of program language affects only one constant factor of complexity. The following sentence is important: No matter what language you choose to describe the data, the change in length is limited. Some data just needs more space to represent than a million green pixels, and you can’t reduce it.

Data loss

But don’t give up hope. We’ve been talking about lossless compression. Lossless compression means that the original data can be completely restored after compression. That is, if C is our compression algorithm and D is the corresponding decompression algorithm, D(C(x)) = x is always true for any input data x.

Lossless compression is very useful! When compressing text data such as literature or blog posts, tax files, low resolution pixel images, etc., you want to do this lossless. With this data, it is important to ensure the accuracy of the data and the order of each character.

But there are other options. Lossy compression means that the compressed data is not guaranteed to be exactly the same as the data before compression. This compression algorithm is quite common.

Lossy compression is widely used. The human senses are quite tolerant of minor errors or flaws. Data loss occurs when images, audio (or video) files are compressed.

Need an example? Take a look at the following 2 pictures of Barack Obama.


The second image is the result of saving the first image as a JPEG, a lossy compression that loses a lot of data. The size of the second image is about 22 kilobytes, and the compression rate is about 15 compared to the original image. Such a large compression rate does not mean that the data loss is serious.

Can you tell the difference between these two pictures? Maybe a little bit. If you get as close to your screen as possible, squint and turn your head to look around the picture. Then you look at the details of his hair, and you count them one by one, and where there is no hair you see a blur. The key is not whether the second image is a perfect copy, but whether it is good enough. When you’re sending data over the Internet, 15x compression is worth more than a lossless PNG image.

But that’s not to say it works so well in every situation. To achieve this compression, JPEG must lose a lot of data, and while it does its best not to lose too much data, you can try to explore its limits. In the live demo below, you can see how low the JPEG image quality limit can go. Also take a look at the picture quality before the sharpness becomes intolerable. As I said before, human visual tolerance is very high.

Editor’s note: the original English here have a Demo, this article not reproduce, at https://unwttng.com/compression-decompressed, please check

Video streaming services like Netflix and YouTube, as well as audio streaming services like Spotify and Soundcloud, all use lossy compression. Buffering or latency is intolerable for a user, so these services compress data as much as possible while maintaining audio and video quality. You will often see dynamic compression of data, and the video will be blurry at first, but the sharpness of the video will increase when you detect that your network speed can accept a smaller compression rate.

See this GIF from Giphy below? Dynamic compression of data applies here as well. See how they handle loading giFs on slow connections (yes, I made a GIF of this loading process on Giphy and embedded it, see what the problem is?). :

(via GIPHY)

Seems weird, right? First, they loaded the first frame of the GIF in low definition. Then, when the bigger data came in, there were giFs. But not quite, just a few frames. More and more frames are then transferred, until the GIF is fully loaded.

This is modern streaming compression: the hybrid compression strategy is almost entirely about delivering smooth content to the user in as few bytes as possible (the smaller the size, the shorter the time). Lossless compression techniques for files, such as RLE, also have their place, and it remains the core module of many of the best desktop file compression tools. But thanks to lossy compression, you can watch Game of Thrones smoothly on TV.

Data compression is everywhere

That’s all we have to say about compression in this article, but that’s just the tip of the iceberg.

We learned the basic ideas of compression techniques, and from them came an important philosophical lesson:

Images, text, video, music — there is no single correct representation of any data. The difference is just how many valid ways there are to represent data.

Compression technology is always looking for more efficient ways to store your data, and the most powerful compression algorithms can find an efficient way to compress any data.

Thanks for reading, and feel free to share with your friends if you approve of the live demos I made in this article.



1 comment

About the author:nEoYe

Personal home page
My article
11