Information compression with and without losses. Lossless format - what is it? High quality music in Lossless format

Lossless compression(English: Lossless data compression) - a method of information compression, using which encoded information can be restored with bit accuracy. In this case, the original data is completely restored from its compressed state. This type of compression is fundamentally different from lossy data compression. For each type digital information, as a rule, there are their own optimal lossless compression algorithms.

Lossless data compression is used in many applications. For example, it is used in the popular ZIP file format and the Unix utility Gzip. It is also used as a component in lossy compression.

Lossless compression is used when it is important that the compressed data is identical to the original. Common example - executable files and source code. Some graphic file formats, such as PNG or GIF, use only lossless compression; while others (TIFF, MNG) can use both lossy and lossless compression.

Lossless compression technique

From combinatorics it follows that there is no lossless compression algorithm that can reduce any file by at least one byte. However, this is not a sign of the quality of a compression algorithm - the algorithm must work effectively on the data for which it is designed.

Multi-purpose compression algorithms are distinguished by the fact that they are capable of reducing a wide range of data - executable files, data files, texts, graphics, etc., and are used in archivers. Specialized algorithms are designed for a certain type of file (text, graphics, sound, etc.), but they compress such files much more strongly. For example: archivers compress audio by about a third (1.5 times), while FLAC compresses it by 2.5 times. Most specialized algorithms are of little use for “foreign” file types: for example, audio data is poorly compressed by an algorithm designed for texts.

Most lossless compression algorithms operate in two stages: the first generates a statistical model for the incoming data, the second maps the incoming data to a bitwise representation, using the model to produce "probabilistic" (that is, frequently occurring) data, which is used more often than "non-probabilistic" data. .

Statistical models of algorithms for text (or text binary data such as executable files) include:

Burrows-Wheeler transform (block-sorting preprocessing that makes compression more efficient)

LZ77 and LZ78 (DEFLATE is used)

Coding algorithms through generating bit sequences:

· Huffman algorithm (DEFLATE is also used)
Arithmetic coding

Lossless compression methods

· Multi-purpose
· Coding of run lengths - simple circuit, which gives good compression for data that contains many duplicate values
· LZW - used in gif and many others.
· Deflate - used in gzip, an advanced version of zip, and as part of the PNG compression process.
· LZMA - used in 7-zip.
v Audio compression:
- · Apple Lossless - ALAC (Apple Lossless Audio Codec);
- · Audio Lossless Coding - also known as MPEG-4 ALS;
- · Direct Stream Transfer - DST;
- · Free Lossless Audio Codec - FLAC;
v Graphics compression
· ABO - Adaptive Binary Optimization;
· GIF - (lossless only for images containing less than 256 colors);
· JBIG2 - (with or without lossy B/W images);
· JPEG-LS - (lossless / almost lossless compression standard);
· JPEG 2000 - (includes lossless compression; also tested by Sunil Kumar, professor at San Diego State University);
· PGF - Progressive Graphics File (lossless/lossless compression);
· PNG - Portable Network Graphics;
· TIFF;
· WMPhoto - (including lossless compression method);
v Video compression
· Animation codec;
· CamStudio Video Codec;
· CorePNG;
· FFV1.

It is often said that RAW photo format provides maximum image quality. On the one hand, RAW is raw data from the camera sensor, on the other hand, RAW has its own special settings.

RAW - thoughts from Radozhiva

I will only write about the Nikon system, since I work with it, and over the years I have gained some experience with RAW files.

Nikon digital SLR cameras have some features of working with RAW. Sami RAW files have an extension NEF (Nikon Electronic Format - electronic format Nikon). In the camera menu, in order not to confuse a person who has read and heard a lot about RAW, marketers carefully write NEF (RAW).

In the menu of some cameras there is only one item, which is responsible for setting RAW. This " Recording images NEF (RAW)" Depending on the camera type, in this menu you can select color depth and compression type. And some cameras don't even allow you to select the RAW setting.

For example, in advanced cameras like , and even in, you can select the color depth for RAW.

Also, in some advanced cameras, for example in the same ones, you can select the compression level for RAW format files, the “TYPE” setting is responsible for this:

Lossless compression
Normal compression
Without compression

So we can use a combination of 6 RAW recording options

12 bit lossless compression
12 bit normal compression
12 bit uncompressed
14 bit lossless compression
14 bit normal compression
14 bit uncompressed

Attention: RAW with 14-bit color depth reduces speed burst shooting in some cameras, for example, in RAW 14-bit mode, the burst shooting speed drops to 2.5 fps. with a color depth of 14 bits cannot shoot at 7 fps in 1.3x mode. and with 14-bit color depth they cannot shoot at 5 fps.

The main question is how much does compression affect image quality?

It is logical to think that with “Lossless Compression” the camera simply compresses the source material using algorithms that do not lose data after decompression. For example, this is how an archiver works on a computer, which can be used to archive or compress files, and then unzip them back without losing data. In practice, “Lossless Compression” practically does not ‘trim’ the source data. “Normal compression” implies compression using unknown algorithms, and, most likely, with a severe loss of quality. “No compression” - this option allows you to get real original data obtained from the camera sensor without any compression or trimming.

Attention: The frame counter correctly shows the number of frames that can fit on the camera card only in the “NO COMPRESSION” mode, since in this mode all files have the same weight and the camera knows exactly how many pictures it can fit. In the “Lossless Compression” and “Normal Compression” modes, the frame counter on Nikon cameras is very wrong, since the camera does not know exactly how much it will be possible to “compress” the resulting image, so it takes the maximum possible volume and calculates based on it quantity. It's sometimes unnerving.

What compression type should you choose?

Lossless compression– the best option, small compression losses, significant space savings and preservation of almost the entire potential of the RAW file
Normal compression– this option is suitable for those who, on the one hand, want to shoot in RAW, and on the other hand, save a lot on disk space
Without compression- most the best option, no loss in quality, the absolute maximum that the camera can produce. A serious disadvantage of the format is the enormous file size.

For example, so as not to talk about abstract things, mine is in RAW 14 bit mode and produces 25MB files without compression. When switching to RAW 14 bit with lossless compression, files weigh on average 15MB. We get saving 10MB in one picture, you must agree, the gain is simply colossal. Well, if you use RAW 14 bit with normal compression, the file weighs from 10 to 15MB.

What color depth should I choose? 12 bit or 14 bit?

14 bit is better than 12 bit. True, the psychological aspect can play a huge role here: when shooting at 14-bit color depth, you can rest assured that you are using the maximum that the camera is capable of. Personally, from my experience, 14 bits seem more flexible for processing.

Personal experience:

On the Internet you can find many battles on the topic 12 or 14 bit, but I'm sure that if you show two pictures with different color depths, even professionals will have a very difficult time distinguishing from each other. I use RAW 14 bit + lossless compression on cameras by type,

Compressed using special lossless audio codecs, it can be restored with absolute accuracy if desired.

If you take an ordinary Audio CD with analog audio, record it in WAV format for sound without compression, then compress the WAV using the lossless codec, then decompress the resulting audio file into WAV and burn the result to a blank CD, you can get two completely identical Audio CD.

The advantage of lossless for storing an audio collection is that the quality of the recordings is much higher than that of lossy codecs, and they take up less space than uncompressed audio. True, lossy files are smaller in size than lossless music files. Most modern player programs understand the lossless format. Those programs that are not able to play it can easily learn it using the lossless plugin. What are lossless audio formats?

Audio formats without loss of quality

A true music lover is unlikely to be satisfied with the sound of music recorded in Ogg Vorbis or MP3 compression formats. Of course, if you listen to audio recordings on household audio equipment, sound defects cannot be detected by ear, but if you try to play a compressed file on high-quality Hi-Fi equipment, sound defects will immediately become apparent. Of course, creating a collection of quality music on CD or vinyl records is not easy. There is a reasonable alternative to this path for lovers of high-quality sound - lossless music. It can be stored on a PC in a form that makes it possible to save unchanged initial parameters music, even if compression is applied. This path solves problems at the same time High Quality music and its compact storage, because audio equipment for listening (headphones, speakers, amplifiers) has a very affordable price.

Uncompressed audio formats without loss of quality:

CDDA is an audio CD standard;
WAV - Microsoft Wave;
IFF-8SVX;
IFF-16SV;
AIFF;

Compressed formats:

FLAC;
APE - Monkey's Audio;
M4A - Apple Lossless - high-quality music format from Apple;
WV - WavPack;
WMA - Windows Media Audio 9;
TTA - True Audio.
LPAC;
OFR - OptimFROG;
RKA - RKAU;
SHN - Shorten.

FLAC format

The most common format is the format What distinguishes it from lossy audio codecs is that no data is removed from the audio stream when used. This makes it possible to successfully use it to play music on Hi-Fi and Hi-End equipment, as well as to create an archive of a collection of audio recordings.

The great advantage of the format is its free distribution. This is important for musicians who record their own music. The format has recently gained great popularity, thanks to which its support is included in the vast majority of media players.

APE format

Unlike FLAC, the APE format only has codecs and plugins designed for the Windows platform. For other platforms, there are expensive solutions from third-party software manufacturers. The algorithm is capable of achieving lossless compression of audio information by approximately 1.5-2 times. It includes three main encoding stages, of which only one is based on the use of properties inherent in sound for compression. The rest are similar to regular archivers. Despite the fact that the compression algorithm is distributed free of charge, the license restrictions are such that it is practically inaccessible to amateur musicians.

Apple Lossless Format

High quality lossless music can be listened to using Apple's audio compression codec without sacrificing quality. This format was developed by Apple for use on its own devices. The format is compatible with iPod players that have special dock connectors and latest firmware. The format does not use specific rights management (DRM) tools, but the container format contains such capabilities. It is also supported by QuickTime and is included as a feature in iTunes.

The format is part of freely available libraries, which makes it possible to organize listening to files in Windows applications. In 2011, Apple published the source codes of the format, which opens up broad prospects for the codec. In the future, it can seriously compete with other formats. The tests showed good results. Compressed files range in size from 40-60% of the size of the originals. The decoding speed is also impressive, which justifies its use for mobile devices, whose productivity is low.

One of the disadvantages of the codec is the extension match sound files with audio codec This leads to confusion, because AAC is not a high-quality music format. Therefore, it was decided to store the data in an MP4 container with the .m4a extension.

Among other formats, it is worth mentioning Windows Media Audio 9 Lossless, included in Windows applications Media. It works with Windows and Mac OS X. However, users do not respond very favorably to it. There are often problems with codec compatibility, and the number of supported channels is limited to six.

WavPack format

WavPack is another freely distributed audio codec that compresses audio information without loss of quality. WavPack integrates an exclusive combined mode that allows you to create two files. One of the files in this mode is created with a relatively low quality loss.wv, which can be played independently. The second “.wvc” file corrects the previous “.wv” and, in combination with it, makes it possible to fully restore the original. Some users may find this approach promising, since there is no need to choose between two types of compression - both will always be implemented.

Also worthy of attention is a video codec with high-quality sound - lagarith lossless codec. It works quickly and efficiently.

Software for listening to lossless audio

Software players did not immediately learn to work with specific lossless codecs that can reproduce sound without loss.

WinAmp Player

Capable of handling almost all music playback formats without lossless quality. What a good lossless player is can be understood by its example. It is able to correctly handle the processing of individual tracks in lossless format. This typical problem FLAC or APE codecs. It consists of digitizing the entire audio disc at once and recording it in one file without dividing it into tracks. An additional file with the extension .cue is designed to solve the problem of dividing into tracks. It contains a description of the access parameters for each album track. An ordinary player plays the entire lossless file. The player for lossless AIMP perfectly reproduces most of the sound formats and recognizes tracks in a lossless format file.

Digital players with lossless support

Users respond well to the digital players jetAudio, Foobar2000, Spider Player. There are no fundamental differences between them. The choice of any device is based on the subjective opinion of a music lover about the convenience of the interface for lossless playback. You can find out what a lossless format is by testing these players.

Apple Lossless format plays with using iTunes. In addition, this codec is supported by the popular video player VLC.

Owners of Apple-compatible computers can use two interesting programs: Vox and Cog.

They support the following lossless formats:

Apple Lossless;
FLAC;
Monkeys Audio;
Wavpack.

In addition to this, there are many useful features, for example, Last.fm services are supported.

Owners of computers with Windows system can use any application that is compatible with lossless music codecs: Foobar2000 or WinAmp. Winamp requires special plugins. Lossless music plays well on iTunes and KMPlayer. An advantage of iTunes that other players do not have is the ability to support tags.

Lossless compatible devices

It is unlikely that the owner of a music library will want to spend time converting files from FLAC format to MP3 in order to be able to listen to recordings on his gadget. A smartphone or tablet has limited capabilities that are incomparable to a computer, but nevertheless, many mobile devices play lossless formats.

For example, device owners Android control can use the andLess player. It is capable of playing FLAC, APE, uncompressed WAV and other formats supported by Android.

The situation is worse for owners of devices on the Blackberry platform. Only owners of Bold 9000 and 8900 or more models later versions can listen to lossless format.

Holders Apple devices can use the ALAC codec without any problems. It is supported iPod player(except shuffle), iPhone And iPad tablet. For FLAC format, you can download FLAC Player from the App Store.

FLAC codec supported Samsung devices Galaxy, some smartphones Sony Ericsson and iriver players.

Stationary devices from many manufacturers also received support for FLAC. Media players and media centers allow you to do without personal computer when listening to songs without loss of quality.

It is still far from full support for absolutely all formats, but it is enough that the media player understands the FLAC codec - the most common codec for high-quality lossless music. What is lossless playback equipment?

Listening equipment

To truly enjoy the sound quality, you need special equipment: headphones, amplifiers, speakers. The easiest way, of course, is with headphones. If you intend to enjoy music while sitting at your computer, these are best suited. Users respond well to products from Koss and Sennheiser. Particular attention should be paid to the size of the membrane. The larger it is, the better the sound. It is important not to be deceived. Some manufacturers put a small membrane in large ear pads - such headphones look solid, but the sound is only suitable for listening to mp3s.

It is difficult to recommend anything to fans of high-quality sound equipment (Hi-Fi or Hi-End). The choice in this area is limited only by budget and tastes. Equalizer, amplifier, acoustics - the choice of these devices has many options. PC owners who are choosing a high-quality one are better off choosing budget monitor speakers from any famous brand. Users respond well to the Microlab SOLO series acoustics. To make lossless music sound good, it is important to purchase acoustics with a subwoofer. unable to cope with the reproduction of the lower frequency band.

Results

New digital sound formats have made it possible for lovers of high-quality music to acquire their own libraries on large-capacity storage media and listen to their favorite compositions in high quality, saving quite a lot of money and quite a lot of space. The ideal option, of course, is a full set of Hi-End equipment, but budget options will also bring great pleasure to music lovers. After all, the experience of listening to music is incomparable to MP3 on plastic speakers.

Modern users quite often face the problem of lack of free space on their hard drive. Many, in an attempt to free up at least a little free space, try to delete hard drive all unnecessary information. More advanced users use special compression algorithms to reduce the amount of data. Despite the effectiveness of this process, many users have never even heard of it. Let's try to understand what is meant by data compression and what algorithms can be used for this.

Today, information compression is a fairly important procedure that is necessary for every PC user. Today, any user can afford to purchase a modern data storage device, which provides the ability to use a large amount of memory. Such devices are usually equipped with high-speed channels for broadcasting information. However, it is worth noting that every year the volume of information required by users becomes more and more. Just $10$ years ago, the size of a standard video film did not exceed $700$ MB. Currently, the volume of films in HD quality can reach several tens of gigabytes.

When is data compression necessary?

You shouldn't expect much from the information compression process. But there are still situations in which information compression is simply necessary and extremely useful. Let's look at some of these cases.

Transfer by e-mail.

Very often there are situations when you need to send a large amount of data by email. Thanks to compression, you can significantly reduce the size of transferred files. Those users who use mobile devices to send information will especially appreciate the benefits of this procedure.

Publication of data on Internet sites and portals.

The compression procedure is often used to reduce the volume of documents used for publication on various Internet resources. This allows you to significantly save on traffic.

Saving free disk space.

When it is not possible to add new means for storing information to the system, you can use the compression procedure to save free disk space. It happens that the user’s budget is extremely limited, and there is not enough free space on the hard drive. This is where the compression procedure comes to the rescue.

In addition to the situations listed above, there are still a huge number of cases in which the data compression process can be very useful. We have listed only the most common ones.

Information compression methods

All existing methods Information compression can be divided into two main categories. These are lossless compression and lossless compression. The first category is relevant only when there is a need to restore data with high accuracy without losing a single bit of the original information. The only case in which it is necessary to use this approach is compression text documents.

In the event that there is no particular need for the most accurate restoration of compressed information, it is necessary to provide for the possibility of using algorithms with certain compression losses.

Compression without loss of information

These methods of information compression are of primary interest, since they are used when transmitting large volumes of information by e-mail, when issuing completed work to a customer, or when creating backup copies information stored on a computer. These methods of information compression do not allow the loss of information, since they are based only on the elimination of its redundancy, and information almost always has redundancy, if the latter did not exist, there would be nothing to compress.

Example 1

Let's give a simple example. The Russian language includes $33$ letters, $10$ numbers and about $15$ punctuation marks and others special characters. For text written only in capital Russian letters (for example, as in telegrams), $60$ of different meanings would be enough. However, each character is usually encoded in a byte containing, as we know, 8 bits, and can be expressed in different codes. This is one of the first factors characterizing redundancy. For telegraph text, $6$ bits per character would be enough.

Example 2

Let's look at another example. In the international ASCII character encoding, the same number of bits ($8$) are allocated for encoding any character, while everyone has long and well known that it makes sense to encode the most frequently occurring characters with fewer characters. So, for example, in Morse code the letters “E” and “T”, which are very common, are encoded with a $1$ sign (respectively, a dot and a dash). And such rare letters as “Yu” ($ - -$) and “C” ($- - $) are encoded with $4$ characters.

Note 1

Inefficient encoding is the second factor that characterizes redundancy. Programs that compress information can enter their own encoding, which can be different for different files, and assign it to compressed file in the form of a table (dictionary), from which the unpacking program will read information about how to this file certain characters or their groups are encoded.

Algorithms based on information recoding are called Huffman algorithms.

Huffman algorithm

In this algorithm, information compression is carried out by statistical coding or based on a dictionary that was previously created. According to the Huffman statistical algorithm, each input symbol is assigned a specific code. In this case, the most frequently used symbol is given the shortest code, and the most rarely used symbol is given a longer code. As an example, the diagram shows the distribution of the frequency of use of individual letters of the English alphabet (Fig. 1). Such a distribution can also be constructed for the Russian language. Coding tables are created in advance and have a limited size. This algorithm provides the highest performance and the lowest delays. To obtain high compression ratios, the statistical method requires large amounts of memory.

Figure 1. Distribution of English letters by their frequency of use

The amount of compression is determined by the redundancy of the bit array being processed. Each of the natural languages has a certain redundancy. Among European languages, Russian has the most high levels redundancy. This can be judged by the size of the Russian translation of the English text. Usually it is about $30\%$ more. If we are talking about a poetic text, the redundancy can be up to $2$ times higher.

Note 2

The biggest challenge with the codes is the need to have probability tables for each type of data being compressed. This is not a problem if you know that you are compressing English or Russian text. In this case, we simply provide the encoder and decoder with a code tree suitable for the English or Russian text. In general, when the probability of symbols for the input data is unknown, static Huffman codes work inefficiently.

The solution to this problem is a statistical analysis of the encoded data, performed during the first pass through the data, and compiling a code tree based on it. The actual encoding is performed in the second pass.

Another disadvantage of codes is that the minimum length of a code word for them cannot be less than one, while the entropy of a message can easily be either $0.1$ or $0.01$ bits/letter. In this case, the code becomes significantly redundant. The problem is solved by applying the algorithm to blocks of characters, but then the encoding/decoding procedure becomes more complicated and the code tree is significantly expanded, which must ultimately be saved along with the code.

These codes do not take into account the relationships between characters, which are present in almost any text.

Note 3

Today, in the information age, despite the fact that almost every user has access to high-speed data transmission channels and large-volume media, the issue of data compression remains relevant. There are situations in which data compression is simply a necessary operation. In particular, this applies to sending data by email and posting information on the Internet.

Lecture No. 4. Information compression

Principles of information compression

The purpose of data compression is to provide a compact representation of the data generated by the source so that it can be more economically stored and transmitted over communication channels.

Let us have a file of 1 (one) megabyte in size. We need to get a smaller file from it. Nothing complicated - we launch an archiver, for example, WinZip, and as a result we get, say, a file of 600 kilobytes in size. Where did the remaining 424 kilobytes go?

Compressing information is one of the ways to encode it. In general, codes are divided into three large groups - compression codes (effective codes), noise-resistant codes and cryptographic codes. Codes intended for information compression are divided, in turn, into lossless codes and lossy codes. Lossless encoding implies absolutely accurate data recovery after decoding and can be used to compress any information. Lossy encoding usually has a much higher compression ratio than lossless encoding, but allows some deviation of the decoded data from the original.

Types of compression

All information compression methods can be divided into two large non-overlapping classes: compression with loss information and compression without loss information.

Compression without loss of information.

We are primarily interested in these compression methods because they are used when transferring text documents and programs, when delivering completed work to a customer, or when creating backup copies of information stored on a computer.

Compression methods of this class cannot allow the loss of information, so they are based only on eliminating its redundancy, and information almost always has redundancy (though, unless someone has already compressed it before). If there were no redundancy, there would be nothing to compress.

Here's a simple example. The Russian language has 33 letters, ten numbers, and about a dozen punctuation marks and other special characters. For text that is written only in capital Russian letters(as in telegrams and radiograms) sixty different meanings would be quite enough. However, each character is usually encoded by a byte, which contains 8 bits and can express 256 different codes. This is the first reason for redundancy. For our “telegraph” text, six bits per character would be enough.

Here's another example. In international character encoding ASCII The same number of bits (8) are allocated for encoding any character, while everyone has long and well known that it makes sense to encode the most frequently occurring characters with fewer characters. So, for example, in Morse code, the letters “E” and “T,” which occur frequently, are encoded with one character (a dot and a dash, respectively). And such rare letters as “Yu” (- -) and “C” (- -) are coded with four characters. Inefficient encoding is the second reason for redundancy. Programs that perform information compression can enter their own encoding (different for different files) and attach a certain table (dictionary) to the compressed file, from which the decompressing program learns how certain characters or their groups are encoded in this file. Algorithms based on information recoding are called Huffman algorithms.

The presence of repeating fragments is the third basis for redundancy. This is rare in texts, but in tables and graphics repetition of codes is common. So, for example, if the number 0 is repeated twenty times in a row, then there is no point in putting twenty zero bytes. Instead, they put one zero and a coefficient of 20. Such algorithms based on identifying repetitions are called methodsRLE (Run Length Encoding).

Graphic illustrations are especially distinguished by large repeating sequences of identical bytes, but not photographic ones (there is a lot of noise and neighboring points differ significantly in parameters), but those that artists draw in “smooth” color, as in animated films.

Compression with loss of information.

Lossy compression means that after unpacking the compressed archive, we will receive a document that is slightly different from the one we had at the very beginning. It is clear that the higher the compression ratio, the greater the loss and vice versa.

Of course, such algorithms are not applicable for text documents, database tables, and especially for programs. Minor distortions in simple unformatted text can still be survived somehow, but distortion of even one bit in the program will make it completely inoperable.

At the same time, there are materials in which it is worth sacrificing a few percent of the information in order to obtain compression tens of times. These include photographic illustrations, videos and musical compositions. The loss of information during compression and subsequent decompression in such materials is perceived as the appearance of some additional “noise”. But since a certain “noise” is still present when creating these materials, its slight increase does not always look critical, and the gain in file sizes is huge (10-15 times for music, 20-30 times for photo and video materials).

Lossy compression algorithms include such well-known algorithms as JPEG and MPEG. The JPEG algorithm is used to compress photographic images. Graphic files compressed using this method have a JPG extension. MPEG algorithms are used to compress video and music. These files can have different extensions, depending on the specific program, but the most well-known are .MPG for video and .MPG for music.

Lossy compression algorithms are used only for consumer tasks. This means, for example, that if a photograph is transmitted for viewing, and music is transmitted for playback, then similar algorithms can be used. If they are transferred for further processing, for example for editing, then no loss of information in the source material is acceptable.

The amount of acceptable compression loss can usually be controlled. This allows you to experiment and achieve the optimal size/quality ratio. In photographic illustrations intended to be reproduced on screen, the loss of 5% of information is usually not critical, and in some cases 20-25% can be tolerated.

Compression algorithms without loss of information

Shannon-Fano code

For further discussion it will be convenient to present our original file with text as the source of characters that appear one at a time at its output. We don't know in advance which character will be next, but we know that with probability p1 the letter "a" will appear, with probability p2 - the letter "b", etc.

In the simplest case, we will consider all text characters independent of each other, i.e. the probability of the next symbol appearing does not depend on the value of the previous symbol. Of course, this is not true for a meaningful text, but now we are considering a very simplified situation. In this case, the statement “a symbol carries more information, the lower the probability of its appearance,” is true.

Let's imagine a text whose alphabet consists of only 16 letters: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Each of these characters can be encode with just 4 bits: from 0000 to 1111. Now imagine that the probabilities of the appearance of these characters are distributed as follows:

The sum of these probabilities is, naturally, unity. Let's divide these symbols into two groups so that the total probability of symbols in each group is ~0.5 (Figure). In our example these will be groups characters A-B and G-R. The circles in the figure denoting groups of characters are called vertices or nodes, and the structure of these nodes itself is called a binary tree (B-tree). Let's assign each node its own code, designating one node with the number 0, and the other with the number 1.

Let us again divide the first group (A-B) into two subgroups so that their total probabilities are as close to each other as possible. Let's add the number 0 to the code of the first subgroup, and the number 1 to the code of the second.

We will repeat this operation until there is only one symbol left at each vertex of our “tree”. The complete tree for our alphabet will have 31 nodes.

The character codes (the rightmost nodes of the tree) have codes of unequal length. Thus, the letter A, which has a probability of p=0.2 for our imaginary text, is encoded with only two bits, and the letter P (not shown in the figure), which has a probability of p=0.013, is encoded with as many as a six-bit combination.

So, the principle is obvious - frequently occurring characters are encoded with a smaller number of bits, and rarely occurring ones with a larger number. As a result, the average number of bits per symbol will be equal to

where ni is the number of bits encoding the i-th character, pi is the probability of the i-th character appearing.

Huffman code.

The Huffman algorithm elegantly implements the general idea of statistical encoding using prefix sets and works as follows:

1. We write down all the characters of the alphabet in order of increasing or decreasing probability of their appearance in the text.

2. We sequentially combine two symbols with the lowest probabilities of occurrence into a new composite symbol, the probability of which we assume to be equal to the sum of the probabilities of its constituent symbols. In the end, we will build a tree, each node of which has the total probability of all nodes below it.

3. We trace the path to each leaf of the tree, marking the direction to each node (for example, to the right - 1, to the left - 0). The resulting sequence gives a code word corresponding to each symbol (Fig.).

Let's build a code tree for a message with the following alphabet:

Disadvantages of methods

The biggest challenge with the codes, as the previous discussion suggests, is the need to have probability tables for each type of data being compressed. This is not a problem if you know that you are compressing English or Russian text; we simply provide the encoder and decoder with a suitable code tree for the English or Russian text. In general, when the probability of symbols for the input data is unknown, static Huffman codes work inefficiently.

Another disadvantage of codes is that the minimum length of a code word for them cannot be less than one, while the entropy of a message may well be 0.1 or 0.01 bits/letter. In this case, the code becomes significantly redundant. The problem is solved by applying the algorithm to blocks of characters, but then the encoding/decoding procedure becomes more complicated and the code tree is significantly expanded, which must ultimately be saved along with the code.

These codes do not take into account the relationships between characters, which are present in almost any text. For example, if in the text on English language we encounter the letter q, then we can confidently say that the letter u will come after it.

Run Length Encoding (RLE) is one of the oldest and simplest archiving algorithms. Compression in RLE occurs by replacing chains of identical bytes with “counter, value” pairs. (“red, red, ..., red” is written as “N reds”).

One of the implementations of the algorithm is as follows: they look for the least frequently occurring byte, call it a prefix, and replace chains of identical characters with triples “prefix, counter, value.” If this byte appears in the source file one or two times in a row, then it is replaced with the pair “prefix, 1” or “prefix, 2”. There remains one unused "prefix, 0" pair, which can be used to indicate the end of the packed data.

When encoding exe files, you can search for and pack sequences like AxAyAzAwAt..., which are often found in resources (Unicode strings)

The positive aspects of the algorithm include the fact that it does not require additional memory during operation and is quickly executed. The algorithm is used in PCX, TIFF, BMP formats. An interesting feature of PCX batch encoding is that the degree of archiving for some images can be significantly improved simply by changing the order of the colors in the image palette.

The LZW code (Lempel-Ziv & Welch) is one of the most common lossless compression codes today. It is with the help of the LZW code that compression is carried out in such graphic formats as TIFF and GIF; with the help of LZW modifications, many universal archivers perform their functions. The operation of the algorithm is based on searching in the input file for repeating sequences of characters that are encoded in combinations of 8 to 12 bits in length. Thus, this algorithm is most effective on text files and on graphics files that have large areas of solid color or repeating sequences of pixels.

The absence of information loss during LZW coding has led to the widespread use of systems based on it. TIFF format. This format does not impose any restrictions on the size and color depth of the image and is widely used, for example, in printing. Another LZW-based format, GIF, is more primitive - it allows you to store images with a color depth of no more than 8 bits/pixel. At the beginning of the GIF file there is a palette - a table that establishes a correspondence between the color index - a number in the range from 0 to 255 and the true, 24-bit color value.

Lossy compression algorithms

The JPEG algorithm was developed by a group of firms called the Joint Photographic Experts Group. The goal of the project was to create a highly efficient compression standard for both black-and-white and color images, and this goal was achieved by the developers. Currently, JPEG is widely used where a high degree of compression is required - for example, on the Internet.

Unlike the LZW algorithm, JPEG encoding is lossy encoding. The encoding algorithm itself is based on very complex mathematics, but in general terms it can be described as follows: the image is divided into squares of 8 * 8 pixels, and then each square is converted into a sequential chain of 64 pixels. Next, each such chain is subjected to the so-called DCT transform, which is one of the varieties of the discrete Fourier transform. It lies in the fact that the input sequence of pixels can be represented as a sum of sinusoidal and cosine components with multiple frequencies (the so-called harmonics). In this case, we only need to know the amplitudes of these components in order to reconstruct the input sequence with a sufficient degree of accuracy. The more harmonic components we know, the smaller the discrepancy between the original and the compressed image will be. Most JPEG encoders allow you to adjust the compression level. This is achieved in a very simple way: the higher the compression ratio is set, the fewer harmonics will be represented by each 64-pixel block.

Of course, the strength of this type of encoding is the high compression ratio while maintaining the original color depth. It is this property that has led to its widespread use on the Internet, where reducing file size is of paramount importance, in multimedia encyclopedias, where storing the largest possible number of graphics in a limited volume is required.

A negative property of this format is the inherent deterioration in image quality that cannot be eliminated by any means. It is this sad fact that does not allow it to be used in printing, where quality is of paramount importance.

However, the JPEG format is not the limit of perfection in the quest to reduce the size of the final file. Recently, intensive research has been carried out in the field of the so-called wavelet transform (or wavelet transform). Wavelet encoders, based on sophisticated mathematical principles, allow for greater compression than JPEG with less information loss. Despite the complexity of the mathematics of the wavelet transform, its software implementation is simpler than JPEG. Although wavelet compression algorithms are still in their early stages of development, they have a great future ahead of them.

Fractal compression

Fractal image compression is a lossy image compression algorithm based on the application of iterated function systems (IFS, which are typically affine transformations) to images. This algorithm is known for the fact that in some cases it allows one to obtain very high compression ratios ( best examples- up to 1000 times with acceptable visual quality) for real photographs of natural objects, which is inaccessible to other image compression algorithms in principle. Due to the difficult situation with patenting, the algorithm was not widely used.

Fractal archiving is based on the fact that using the coefficients of a system of iterated functions, the image is presented in a more compact form. Before looking at the archiving process, let's look at how IFS builds an image.

Strictly speaking, IFS is a set of 3D affine transformations that transform one image into another. Points in three-dimensional space (x coordinate, y coordinate, brightness) undergo transformation.

The basis of the fractal coding method is the detection of self-similar areas in the image. The possibility of applying iterated function systems (IFS) theory to the problem of image compression was first explored by Michael Barnsley and Alan Sloan. They patented their idea in 1990 and 1991. Jacquin presented a fractal coding method that uses systems of domain and range subimage blocks, square-shaped blocks that cover the entire image. This approach became the basis for most fractal coding methods used today. It was improved by Yuval Fisher and a number of other researchers.

In accordance with this method, the image is divided into a set of non-overlapping rank subimages (range subimages) and a set of overlapping domain subimages is determined. For each rank block, the encoding algorithm finds the most suitable domain block and an affine transformation that translates this domain block into a given rank block. The image structure is mapped into a system of rank blocks, domain blocks and transformations.

The idea is as follows: suppose that the original image is a fixed point of some compression mapping. Then, instead of the image itself, you can somehow remember this mapping, and to restore it, it is enough to repeatedly apply this mapping to any starting image.

According to Banach's theorem, such iterations always lead to a fixed point, that is, to the original image. In practice, the whole difficulty lies in finding the most suitable compression mapping from the image and storing it compactly. Typically, mapping search algorithms (i.e., compression algorithms) are highly brute force and computationally expensive. At the same time, recovery algorithms are quite effective and fast.

Briefly, the method proposed by Barnsley can be described as follows. The image is encoded by several simple transformations (in our case, affine), that is, it is determined by the coefficients of these transformations (in our case, A, B, C, D, E, F).

For example, the image of the Koch curve can be encoded with four affine transformations, we will uniquely define it using only 24 coefficients.

As a result, the point will definitely go somewhere inside the black area in the original image. Having done this operation many times, we will fill all the black space, thereby restoring the picture.

The two most famous images obtained with IFS are Sierpinski's triangle and Barnsley fern. The first is given by three, and the second by five affine transformations (or, in our terminology, lenses). Each transformation is specified in literally a few bytes, while the image constructed with their help can occupy several megabytes.

It becomes clear how the archiver works and why it takes so much time. In fact, fractal compression is a search for self-similar areas in an image and determination of affine transformation parameters for them.

In the worst case, if no optimizing algorithm is used, it will be necessary to enumerate and compare all possible image fragments of different sizes. Even for small images, taking discreteness into account, we get an astronomical number of options to be sorted out. Even sharply narrowing the classes of transformations, for example, by scaling only a certain number of times, will not allow achieving an acceptable time. In addition, image quality is lost. The vast majority of research in the field of fractal compression is now aimed at reducing the archiving time required to obtain a high-quality image.

For the fractal compression algorithm, as for other lossy compression algorithms, the mechanisms by which the degree of compression and the degree of loss can be adjusted are very important. To date, a fairly large set of such methods has been developed. Firstly, you can limit the number of transformations, knowingly ensuring the compression ratio is not lower than a fixed value. Secondly, you can demand that in a situation where the difference between the processed fragment and its best approximation is above a certain threshold value, this fragment must be crushed (several lenses must be installed for it). Thirdly, you can prohibit splitting fragments smaller than, say, four points. By changing the threshold values and priority of these conditions, you can very flexibly control the image compression ratio: from bitwise matching to any compression level.

Comparison with JPEG

Today, the most common graphics archiving algorithm is JPEG. Let's compare it with fractal compression.

First, note that both algorithms operate on 8-bit (grayscale) and 24-bit full-color images. Both are lossy compression algorithms and provide similar archiving rates. Both the fractal algorithm and JPEG have the opportunity to increase the compression ratio by increasing losses. In addition, both algorithms are very well parallelized.

The differences start when we consider the time it takes for the algorithms to archive/unarchive. Thus, the fractal algorithm compresses hundreds and even thousands of times longer than JPEG. Unpacking an image, on the contrary, will happen 5-10 times faster. Therefore, if the image will be compressed only once, but transmitted over the network and decompressed many times, then it is more profitable to use a fractal algorithm.

JPEG uses cosine function decomposition of the image, so losses in it (even at specified minimum losses) appear in waves and halos at the border of sharp color transitions. It is precisely for this effect that people do not like to use it when compressing images that are prepared for high-quality printing: there this effect can become very noticeable.

The fractal algorithm is free from this drawback. Moreover, when printing an image, you have to perform a scaling operation each time, since the raster (or line) of the printing device does not match the raster of the image. During conversion, several unpleasant effects may also arise, which can be dealt with either by scaling the image programmatically (for cheap printing devices such as conventional laser and inkjet printers), or by equipping the printing device with its own processor, hard drive and a set of image processing programs (for expensive phototypesetting machines). As you might guess, when using a fractal algorithm, such problems practically do not arise.

The replacement of JPEG by the fractal algorithm in widespread use will not happen soon (if only due to the low archiving speed of the latter), however, in the field of multimedia applications, in computer games its use is completely justified.