Data compression: lossless and lossy
In computer science and telecommunications, the term data compression (data compression) will indicate the data processing techniques that allow the reduction of the quantity of bits necessary for the representation of the information in digital form. In practice, for example, data compression makes it possible to reduce the number of bits required for the transmission of a video transmission, allowing it to be viewed on the Internet even in the presence of a connection that is not fast enough.
For files, data compression allows you to reduce the size (number of bits) of the file – this is advantageous because it reduces the space occupied by the file on disk and allows you to transfer the file more quickly (for example, by email).
Compression techniques fall into two main categories:
lossless compression (lossless):
in this case it is possible to rebuild the file from the compressed without loss of information;
lossy compression (loss)
compression occurs to the detriment of information quality, for example, through loss of image definition or sound quality of an audio file; in this case it is not possible to rebuild the file from the compressed file before compression.
The two techniques are used in different areas. As already mentioned, lossy compression is often applied to images, sounds and videos as it enables significant reductions to be made from the original data, at the price of an often negligible loss in quality. In addition, lossy techniques can be applied during data transmission (runtime), that is, it is not necessary to know all the data to be compressed to apply them: this is obviously an advantage in the transmission of transmissions over the Internet . Among the best known lossless algorithms, we mention jpeg for images and mp3 for audio and mpeg for videos.
In contrast, lossless compression is used when you want to compress text documents, programs, databases, circuit diagrams, etc. and in any case where the loss of the original data is not accepted. The lossless compression category includes .zip and .rar formats, often used to compress files and file folders.
Later we will discuss lossy compression techniques, talking about multimedia formats. Here, instead, we want to deepen the understanding of lossless compression.
Lossless compression algorithms
Lossless compression techniques (algorithms) can be divided into two main categories:
statistical compression;
replacement compression
.
Statistical compression is based on the input study to be compressed. Statistical studies are carried out on the input format to obtain a good compression. For example, in a text file to compress, the relative frequency of each character is studied and then the shortest code is associated with the character present several times in the text; vice versa, characters present with low frequency are associated with a longer code. Codes like Huffman’s are part of this class, which we will discuss in the next lesson.
As for substitution compression, this is based on the idea of replacing, in a file, all occurrences of repeated strings with pointers to previous copies of the same string. Compression is due to the fact that the length of a pointer is usually less than the length of the string being replaced. As a result, the higher the repetitions of string occurrences in the file to be compressed, the greater the degree of compression achieved.
