Today, files transmitted by communication channels most often contain data of one of four main types: texts, images, video or sound. And if 4 KB is enough to store one page of unformatted text, then a photo-realistic raster image of 1015 cm size without compression can take several MB, song recordings -tens of MB, and movie recordings -several GB. Fortunately, most of these files have a high level of redundancy. It is the reduction of redundancy that allows you to compress files and thereby increase the speed of information exchange over the network and reduce the amount of disk space used.

Most of the well-known algorithms that allow you to compress images dozens of times (JPEG [1][2], fractal and wavelet transforms [3]) lead to slight loss of image quality. Such losses are invisible for photorealistic high-resolution images, but affect the quality of low-resolution images with fragments of business graphics or discrete-tone transitions. In addition, there are classes of images for which distortions are unacceptable (for example, X-rays). Algorithms for image compression without loss [4], although they compress images much weaker, do not lead to deterioration of their quality. Currently, lossy image compression algorithms are developing most dynamically, although lossless image compression algorithms are also gradually increasing their compression rates. Therefore, in the era of information civilization, when most information is stored electronically, the problem of lossless image compression by reducing redundancy remains relevant now and will be relevant in the future.

As it is known, any data compression is possible precisely due to the reduction or elimination of redundancies [5]. Three main types of redundancies are distinguished in images [6]: visual (consisting in the presence of information that is not perceived by the human visual system), inter-element or spatial (manifested in the correlation of brightness of adjacent pixels or components of the color model) and code (revealed when using codes of the same length for items with different probabilities). The more types of redundancies of each type are processed in a graphic format, the more effective the compression is. In the process of lossless compression, no information is lost, so the first type of redundancy is not reduced.

To reduce redundancies of the second and third types in archivers and graphic formats lossless compression of images most often occurs in a maximum of four stages:

1. At the first stage, context-dependent coding reduces redundancies between the same fragments or fragments with the same structure (reduces inter-element redundancy, can be also used before the fourth stage). For example, the popular context-dependent algorithm LZ77 [7] is based on the replacement in the output stream of the sequence of consecutive literals of the buffer with a reference to a similar pre-encoded sequence of dictionary literals in the form of a pair of numbers <length, offset from the end of the dictionary> in the process of coding. If there is no similar sequence of literals in the dictionary longer than two literals, the first literal of the buffer is transferred to the output stream without changes. After that, the encoded literals are transferred from the beginning of the buffer to the end of the dictionary and the encoding continues similarly until the end of the literals of the input stream. An example of the step-by-step results of the LZ77 algorithm scheme formation for flow 3, 4, 6, 3, 4, 6, 3, 2, 6, 3, 4, 4 from [8] is given in Table 1. This stream in algorithm-encoded form will be written as 3, 4, 6, <4, 3>, 2, <3, 6>, 4; 2. At the second stage, the transition to an alternative color model is performed. For example, in a popular archiver WinRAR [9] before lossless image compression, the transition from the RGB color model to the R-G, G, B-G color model is performed; 3. On the third, the brightness of the pixel components is transformed using predictors [10], which during image traversal predict the brightness value of each component of the next pixel (for example, for the most common 24-bit images, these are the brightness of the red, green, and blue components, written as integers in separate bytes), using the brightness values of the same components of previously processed adjacent pixels. In the process of using this approach, deviations ij  of the value of the brightness of the next pixel component ij brightness from the value predicted by the selected predictor ij predict are calculated and further coded, i.e.

(1) (i and j run respectively through all the rows and columns of the pixel components of the image). Adjacent image pixels most commonly have similar colors, which means that they also have close value brightness of relevant components, therefore value forecast often matches with value brightness of the regular components, most often it is close to this value and rarely -much differs from him (Figure 1 from [10]). That is, most of the values ij  are close to zero. The use of predictors is similar to delta coding [2]; a) b) Figure 1: A division of frequencies of values of green components of image Lena.bmp: a) before the use of predictor (H =7.59 of bpb); b) after the use of Left-predictor (H =5.34 of bpb) with [10] 4. At the fourth stage, context-independent coding forms element codes with lengths that dependent on their probabilities (processes code redundancy). Identical fragments or fragments of the same structure targeted by context-sensitive coding rarely occur in photorealistic images, so the only universal step of lossless image compression is contextindependent coding itself. It can even be used instead of context-sensitive luminance codes of individual pixels, if this further reduces the compression ratio (the ratio of the size of compressed to uncompressed image files, expressed in bpb, hereafter CR). According to our calculations, the application of a context-independent algorithm reduces the CR of images by 33% on average. Therefore, let's consider the ideas of this coding in more detail. The main principle of context-independent coding is formulated as follows: the length of the code of an arbitrary element with a higher probability should not exceed the length of the code of any element with a lower probability. This principle is based on the fundamental position of information theory, according to which, in order to minimize the length of the sequence code, an element i s with a probability of occurrence   i s p should be coded with

bits [6]. Then the average code length of the block element after applying any context-independent algorithm according to the formula of Shannon [11] cannot be less than the entropy of the source

In practice today, two alternative context-independent methods are most often used: Huffman coding and arithmetic coding.

Huffman coding (HUFF) matches each element depending on its probability (frequency of occurrence) with a fixed prefix code [12] [13] [14][15]. This coding is most often performed in the following sequence: the probabilities (frequencies) of individual elements are calculated; elements in descending order of probabilities are arranged; the two elements with the lowest probabilities (most often the last ones in the created list) are iteratively combined in order to obtain one element, the code 0 to the first one, and 1 to the second one are added; the probabilities of the selected elements to calculate the probability of the formed element and insert this element into the sorted list of probabilities are summed; HUFF codes are formed, the formed codes in reverse order -from the top to each element are written. The average length of the HUFF code coincides with the entropy of the source only when for all elements s i the lengths of their optimal codes -log2 p(s i) are integers. In addition, the length of the HUFF code of even the most probable element cannot be less than one bit. Arithmetic compression (ARIC), in contrast to HUFF coding, matches each successive element with an interval with a length proportional to its probability (frequency) [16] [17][18] [19]. At the same time, a subinterval corresponding to the first element of the flow is selected from the initial interval (most often [0; 1)) and further considered. This subinterval is again divided in proportion to the frequencies of individual elements, and the subinterval corresponding to the second element of the flow is selected from it (see, for example, Figure 2 from [20], on which the subintervals are ordered by the increasing values of the elements). The selection of subintervals continues in the same way until the end of the flow elements. Thus, the final length of the selected subinterval is equal to the product of the probabilities of all elements, and its beginning depends on the sequence of these elements in the stream. The result of ARIC is any number from the last subinterval received. Taking into account the finiteness of the numbers, to record the resulting number, the first significant digits of the intervals are monitored each time, and if they match, these digits are recorded in the output stream and excluded from further consideration. Decoding of the next ARIC element is performed by determining the corresponding next subinterval to which the read number belongs. with [20] From the description of the ARIC principles, it follows that in order to perform such arithmetic compression, the coder and, even more so, the decoder, must know the probabilities (frequencies) of individual elements. Today, two strategies for forming these frequencies are widely used: static and adaptive. In the case of a static strategy, the frequencies of individual elements are transmitted to the decoder in compressed data explicitly. When using an adaptive strategy, the intervals of the elements are formed synchronously by the encoder and decoder in the process of data processing. The adaptive strategy provides, as a rule, better CR (since it does not need to store the frequencies of individual elements in the compressed data and takes into account the unevenness of the distribution of the current sequence of elements, and not the flow in general), but it significantly slows down the work of the decompressor, because it requires recalculation of the probabilities of the elements in the decoding process. Graphics file formats should, first of all, provide fast decoding, so they often use a static strategy for forming element intervals.

To speed up the development of graphic formats, data compression formats are created, improved and used, which combine proven context-dependent and context-independent algorithms. One of the successful examples of such a combination is the DEFLATE dictionary compression format [21], which for processing of incoming flow uses context-dependent LZ77 algorithm [7], a the results of his work is compressed by Huffman's dynamic codes [12]. This format is used in many popular archivers (for example, GZIP [22]) and graphic formats (for example, PNG [23]) and does not need the acquisition licenses for use in applied software. We use this compressed data format to develop a lossless progressive hierarchical image compression format [8][10] [20].

It is clear that implementations of the decoding algorithm of LZ77 codes must distinguish between individual literals and groups <length; displacement>. In the DEFLATE format, for this purpose, the lengths of the substitutions and the individual literals of the LZ77 algorithm are encoded together as numbers in the range [0; 285]. At the same time, in each compressed block numbers from the range [0; 255] correspond to the codes of individual literals, 256 marks the end of the block, and numbers from the range [257; 285] indicate the basic values of lengths. After the basic length values, there is a number of bits defined by the format, which, together with the basic value, uniquely determines the replacement length [21]. The offset is stored after the corresponding replacement length similarly -in the form of the base value and additional bits. The basic displacement value is within [0; 29]. In the DEFLATE format, the maximum encoded sequence length can be 258, the offset can be 32768, and different dynamic codes HUFF are used to encode the base literals/lengths and offsets.

The purpose of this article is to describe and justify the algorithm for redistribution of compressed data between modified DEFLATE blocks to improve the compression performance of this format.

Let's first emphasize the reasons for improving compression by context-independent algorithms of the fourth stage in cases of applying the algorithms of the second and third stages. Let's investigate the dependence of entropy for the case of two elements (Figure 3 and [24]). Let the probability of the appearance of the first element be equal to 1 p . Then the probability of the second element will be

, and the entropy will be equal to

. We see that the entropy is maximal when

. The greater the probabilities of the elements differ among themselves, that is, the greater the unevenness of the distribution is, the lower the entropy is [24]. For M the entropy of different elements is also maximal when the probabilities of these elements are the same and is calculated by Hartley's formula [24]: Difference color models of the second and predictors of the third stage of lossless image compression do not compress the image, but increase the unevenness of the brightness distribution around zero (Figure 1b) and therefore reduce the entropy (1), i.e. increase the code redundancy by reducing the inter-element one.

Taking into account the fact that arithmetic coding more accurately encodes elements whose occurrence of probabilities are not equal to powers of two [5], we modified the DEFLATE compressed data format by applying E. Shelvin's range coder in it, the code of which can be found, for example, in [25]. This encoder reads/writes bytes instead of bits of data and thus significantly speeds up encoding/decoding. For each element, it uses an interval with an integer length proportional to its probability. In order to store the length of the interval for each element in the header of the modified DEFLATE-block of compressed data, instead of the length of the HUFF code, we write the number of bits for storing the corresponding length of the interval in the general interval [0; 32768), and after the header -a binary record of this length without the first bit (which is always equal to one) [20]. The DEFLATE format uses a maximum of 285 different elements to encode literals/lengths replacement. If there are M different elements in the next modified DEFLATE block, then, taking into account (2), the number of additional bits for recording their interval lengths in the block header will be

, if these elements are equally likely. In general, the header size of the modified DEFLATE block will not exceed 2635 bits.

The size of the most compressed data in each block by its length entropy code [20]    , log log At first glance, it seems that combining all the compressed data into one modified DEFLATE block should reduce CR, because then only one header of the compressed data block needs to be stored instead of many. But it was shown in work [20] that the combination of blocks of compressed data does not reduce (most often -increases) the length of their entropy code. The greater the difference between the relative frequencies of each element in the two input blocks is, the greater the additional increase in the length of the entropy code (Figure 4 from [20]) will be. This gain is zero only when the relative frequencies of the element in the two input blocks match.

The dependence of the increase in the length of the entropy code of the combination of two input sequences on the frequencies of the element s i in these input sequences [20] Taking into account (3), the increase in the length of the entropy code due to the combination of two adjacent blocks will be calculated using the formula (4)