
Lossless Compression – How It Works
When the copy is not different from the original.

Lossless Compression – How It Works
We have already discovered how sound is digitized. One of the problems: if we digitize it with high quality, then we need a large amount of data, which means large files, a large consumption of disk space, expensive flash drives, a lot of Internet traffic. I would like the files to be smaller.

For this, compression is used – various algorithms that do their magic with the data and the output is data from a smaller volume.
Lossy and lossless compression
There are two main types of compression: lossy and lossless.
Lossy compression means that we lost some information in the process. Lossy compression algorithms try to make sure that we only lose data that is not too important to us.
Imagine that lossy compression is a short retelling of a school curriculum work: the student is not so important about the description of the author’s nature and style, the main thing is the plot. The short count kept only what was important, but conveyed it much faster.
Lossless compression is when we reduce the size of the file, without losing quality. Interesting mathematical and coding techniques are used for this. The main idea is that during decoding all the data remains in place.
Lossless compression algorithms
There are two main options: the Huffman algorithm or the LZW. LZW is used everywhere, but it is quite difficult to explain, not intuitive, and requires a full lecture. It is much better to explain the Huffman algorithm.
Huffman’s algorithm takes the file, breaks it into pieces, making it convenient to operate, and then looks at how common each fragment is. The algorithm designates the most frequent words with a short code and the rarest with a longer code. Since the most frequent words now take up much less space, the finished file becomes smaller.
But there is also a downside: sometimes you need to store this word and code mapping table directly in the same file, but it can turn out large on its own. Most often, the Huffman algorithm is used for lossless compression of text and video files.
Here’s an example: Take the song Beyonce – All The Single Ladies. There are two such passages there:
All the single women
All the single women
All the single women
Now put your hands up
…
If you like it then you should put a ring on it
If you like it then you should put a ring on it
Don’t be mad once you see that he wants it
If you like it then you should put a ring on it
Here are 281 signs. We see that some lines are repeated. Let’s code them:
COMPRESSION TABLE
\ a \ All single women
\ b \ Now put your hands up
\ c \ If you like it then you should have put a ring on it
\ d \ Don’t be mad once you see that he wants it
SONG TEXT
\ a \ \ a \ \ a \ \ b \
…
\ c \ \ c \ \ d \ \ c \
Along with the compression table, this text now occupies 187 characters; we have compressed the text by almost a third due to the fact that it is quite monotonous.
Lossless compression using audio as an example
On average, one minute of uncompressed audio takes up 10 megabytes. This is quite a lot: if, for example, you have a one-hour recording of a concert, it will be half a gigabyte. On the other hand, this recording captures all the nuances of the sound, there are many high frequencies and beauty in general.
For such situations, lossless compression is used: it shrinks the file by 2 to 3 times without distorting the sound. The algorithms that compress the audio are called codecs. FLAC and Apple Lossless are two popular lossless audio compression codecs.
Compare the size and quality of the two-minute audio yourself:
Original: uncompressed WAV format, 23 megabytes
Lossless compression: FLAC format with the same parameters as WAV, 10 megabytes
Where else is lossless compression used?
In filing cabinets. The job of archiving programs is to package selected files so that the file takes up as little space as possible, without damaging what’s inside. For example, the text version of “War and Peace” might be 4 megabytes and the archived version 100 kilobytes 40 times less.
In programming. There are special wrappers that take a ready-to-use program and optimize the code so that it takes up less space, but retains its functionality. For example:
Delete comments
Minimize function and variable names
Remove characters required for human readability











