RU2382492C1 - Method of compressing and retrieving data without loss - Google Patents

Abstract

FIELD: physics; communication.

SUBSTANCE: invention relates to telecommunication and specifically to reducing redundancy of transmitted information and can be used for compressing and retrieving without loss of digital data in information systems and telecommunication systems. Faster compression and retrieval of data is achieved due to that, prefix codes are assigned not to all n bit numbers, but only groups whose number is considerably less, as well as due to that the number of calculation operations is reduced, particularly operations for reading variable-length codes. These calculation operations are replaced with operations for reading records from a table which takes considerably less time.

EFFECT: faster compression and retrieval of data, increased compression ratio of high-entropy data, easy realisation of the compression and retrieval method, reduced number of operations of compressing and retrieving data.

4 tbl

Description

The invention relates to the field of telecommunications, and in particular to the field associated with reducing the redundancy of transmitted information, and can be used to compress and restore without loss of digital data in information systems and telecommunication systems.

The foundations of the theory of information were laid by C. Shannon in 1948 in his pioneering work on the theory of information (D. Salomon "Compression of data, images and sound", Moscow, Technosphere, 2004, p. 25), in which he introduced the concept of source entropy. The fundamental value of this value is that it sets the lower limit of possible compression (D. Salomon “Compressing data, images and sound”, Moscow, Technosphere, 2004, p. 8). This boundary can be approached arbitrarily close using a suitable source coding method. By the entropy of the symbol a, with probability P, is meant the amount of information contained in a, which is equal to -P · log ₂ (P). (D. Salomon “Compression of data, images and sound”, Moscow, Technosphere, 2004, p. 25).

Distinguish between lossless compression, in which it is possible to completely restore the original information, and compression with partial data loss, in which data is restored with a partial loss of information.

A known method of compressing and restoring lossless data using variable-length codes (D. Salomon "Compressing data, images and sound", Moscow, Technosphere, 2004, p. 26), including, the choice of alphabet - a set of characters from a ₁ to a _n , collecting statistics - the probabilities of each character of the alphabet in a compressible data stream, compiling codes of variable length and replacing the original characters with codes of variable length. To restore the original data stream in accordance with the constructed codes of variable length, replace the codes of variable length with the original characters of the alphabet.

The disadvantage of this method is:

- low speed of compression and recovery operations;

- A large number of computational operations necessary for constructing codes of variable length and data recovery.

There is also a known method of compressing and restoring lossless data using the Huffman method (D. Salomon "Compressing data, images and sound", Moscow, Technosphere, 2004, p. 30; M. Werner "Fundamentals of coding", Moscow, Technosphere, 2004 ., p. 29), including for the selected alphabet

- compiling a list of alphabet symbols in descending order of their probabilities;

- combining the two characters with the least probabilities into one composite sign. Reorder the list of characters according to the previous step. Then continue this process until all the characters are combined;

- start with the last association. The symbol 0 is assigned to the first component of the composite symbol, symbol 1 is continued to the second. Continue until all simple symbols are encoded.

For recovery, it is necessary, in accordance with the constructed Huffman codes, to transform the compressed stream to its original form (D. Salomon “Compressing data, images and sound”, Moscow, Technosphere, 2004, p. 38; M. Werner “Fundamentals of coding”, Moscow , Technosphere, 2004, p. 29). To do this, start from the source node of the constructed code tree and move up or down depending on the character read up to the end node.

The disadvantages of this method are:

- low speed of data compression and recovery operations;

- maximum compression is achieved if the probabilities of the characters are equal to the negative powers of 2;

- different codeword lengths lead to uneven delays in data recovery.

The technical result of the claimed invention is to increase the speed of compression and data recovery operations, increase the data compression ratio for data with high entropy, simplify the implementation of the compression and recovery method, reduce the number of compression and data recovery operations.

The specified technical result is achieved in that in a method for compressing and restoring data, including selecting equal lengths of segments into which the stream of compressible data is then divided and denoting this length by n bits, then the probabilities of each number of length n bits in the entire compressible data stream are calculated, According to the invention, numbers are combined into prefix groups and designated by prefix codes. In this case, the numbers with the highest probability are placed in the first group and the shortest prefix is assigned to this prefix group. code, the next group also puts the numbers with the highest probabilities of those numbers that were not placed in the previous group, and assign the next prefix code to the given prefix group, and there should not be more than n prefix groups, after which each prefix to the group, all numbers are numbered in order starting from zero and get the serial number number in the prefix group, while for recording any serial number number in a specific prefix group, the number of bits that are necessary for writing is allocated the maximum serial number number in a given prefix group, while at least the sum of the bit lengths of the shortest prefix code and the bit length allocated to record the sequence numbers of numbers in the prefix group indicated by the shortest prefix code must be less than n, then the numbers from zeros to 2n-1, prefix codes, serial numbers in prefix groups are entered into the table and saved, then the entire stream of compressible data is converted in such a way that instead of the original number of length n bits, the prefix code is written group and the serial number in the prefix group, repeat the entire subsequent sequence for the next number of length n bits, read the group prefix code and serial number in the prefix group to restore the data stream, and replace the group prefix code and serial number in accordance with the table in the prefix group, by the number corresponding to the group prefix code and the serial number number in the prefix group, then the next group prefix code and the serial number number in the prefix are read group and the entire subsequent sequence of actions is repeated.

The method is as follows.

Equal lengths of segments are selected into which the stream of compressible data is then divided and this length is denoted by n bits. Then, the probabilities of each of the numbers of length n bits in the entire compressible data stream are calculated. Numbers are combined into prefix groups and denote these groups by prefix codes; in this case, the numbers with the highest probabilities are placed in the first group and the shortest prefix code is assigned to this prefix group, and the numbers with the highest probabilities from those numbers that were not placed in the next group are also placed the previous group, and assign the next longest prefix code to the given prefix group. Total prefix groups must not be greater than n. After that, in each prefix group, all numbers are numbered in order starting from zero and get the serial number number in the prefix group, and to record any serial number number in a particular prefix group, the number of bits that is necessary to record the maximum serial number number in this prefix group. At a minimum, the sum of the bit length of the shortest prefix code and the bit length allocated to record the sequence numbers of the numbers in the prefix group indicated by the shortest prefix code must be less than n. Then the numbers from zero to 2n-1, prefix codes, serial numbers in the prefix groups are entered into the table and save it. Now directly convert the data stream. To do this, instead of the first number of length n bits, the code of the prefix group and the serial number in the prefix group are written. The entire subsequent sequence of actions is repeated for the next number of length n bits.

To restore the data stream, the group prefix code and the serial number number in the prefix group are read and, in accordance with the table, the group prefix code and the serial number number in the prefix group are replaced by the number corresponding to the group prefix code and the serial number number in the prefix group. Then read the next prefix code of the group and the serial number in the prefix group and repeat the rest of the sequence.

An example of a specific implementation of the method.

Equal lengths of segments are selected into which the stream of compressible data is then divided. This length is denoted by n bits, for example 4 bits (see table 1). Then, the probabilities of each of the 4-bit numbers are calculated in the entire compressible data stream (Table 1, column 3). After this, the numbers are combined into prefix groups and designated by prefix codes for these groups (see Table 2). The first group contains the numbers with the highest probability and assigns the shortest prefix code to this prefix group. So the numbers 0001, 0010, 0100, 1000 are combined in the first prefix group and the prefix code 0 is assigned to this group. The numbers with the highest probabilities from those numbers that were not placed in the previous group are also placed in the next group. These are numbers 0111, 1011, 1101, 1110. A prefix code of 10 is assigned to this group. A total of 4 prefix groups are formed. After that, in each prefix group, all numbers are numbered in order starting from zero and get the serial number in the prefix group (table 2, column four).

Table 1 All numbers from 0 to 2 ⁴ -1 (binary) The number of numbers in a compressible sequence Probabilities of numbers in a compressible data stream one 2 3 0000 one hundred 100/3200 0001 300 300/3200 0010 300 300/3200 0011 one hundred 100/3200 0100 300 300/3200 0101 one hundred 100/3200 0110 one hundred 100/3200 0111 300 300/3200 1000 300 300/3200 1001 one hundred 100/3200 1010 one hundred 100/3200 1011 300 300/3200 1100 one hundred 100/3200 1101 300 300/3200 1110 300 300/3200 1111 one hundred 100/3200

To record any serial number number in a particular prefix group, the number of bits is allocated that is necessary to record the maximum serial number number in a given prefix group, therefore, in the example, two bits are allocated in all prefix groups for recording the serial number numbers.

At the same time, at least the sum of the bit length of the shortest prefix code and the bit length allocated for recording the sequence numbers of the numbers in the prefix group indicated by the shortest prefix code should be less than 4. In the above example, the code of the first prefix group 0 occupies one bit, 2 bits are needed to record the sequence number in a given prefix group.

table 2 All numbers from 0 to 2 ⁴ -1 (binary) Amount in compressible data stream Group Prefix Codes The sequence number of the number in the prefix group one 2 3 four 0000 one hundred 111 00 0001 300 0 00 0010 300 0 01 0011 one hundred 110 00 0100 300 0 10 0101 one hundred 110 01 0110 one hundred 110 10 0111 300 10 00 1000 300 0 eleven 1001 one hundred 110 eleven 1010 one hundred 111 01 1011 300 10 01 1100 one hundred 111 10 1101 300 10 10 1110 300 10 eleven 1111 one hundred 111 eleven

Thus, to write any number that is assigned to the first prefix group, 3 bits are required. In this case, the gain from such a conversion will be one bit for each number with a length of 4 bits.

All numbers from zero to 2 ⁴ -1, prefix codes, serial numbers in prefix groups are entered in table 3 and save it.

Table 3 All numbers from 0 to 2 ⁴ -1 (binary) Group Prefix Codes The sequence number of the number in the prefix group one 2 3 0000 111 00 0001 0 00 0010 0 01 0011 110 00 0100 0 10 0101 110 01 0110 110 10 0111 10 00 1000 0 eleven 1001 110 eleven 1010 111 01 1011 10 01 1100 111 10 1101 10 10 1110 10 eleven 1111 111 eleven

All of the above actions precede the transformation of the data stream.

Now directly convert the data stream. To do this, instead of the first number 4 bits long of the initial data stream, the code of the prefix group and the serial number number in the prefix group are recorded in accordance with Table 3. The entire subsequent sequence of actions is repeated for all subsequent segments of 4 bits in length.

To restore the data stream, the group prefix code and the serial number number in the prefix group are read and, in accordance with Table 3, the group prefix code and the serial number number in the prefix group are replaced by the number corresponding to the group prefix code and the serial number number in the prefix group, then the following is read the prefix code of the group and the serial number in the prefix group and the entire subsequent sequence of actions are repeated.

Table 4 shows the calculation of the final size to which the original data stream will be compressed without taking into account the number of bits required to write table 3.

The size of the entire data stream before compression was: 4 bits * 3200 = 12800 bits.

The data size after compression was 12400 bits.

The inventive method allows to achieve

- a higher data compression ratio compared to the Huffman data compression method for data with high entropy;

- the high speed of compression and data recovery operations achieved by replacing calculation operations with table searches and reducing computational operations;

Table 4 All numbers from 0 to 2 ⁴ -1 (binary) The number of numbers in the compressible stream (in decimal) Record the number after conversion (group code and serial number in the group) The number of bits that the compressed number occupies (in decimal) The number of bits required to compress all numbers: column 2 × column 4 (in decimal) one 2 3 four 5 0000 one hundred 111 00 5 500 0001 300 0 00 3 900 0010 300 0 01 3 900 0011 one hundred 110 00 5 500 0100 300 0 10 3 900 0101 one hundred 110 01 5 500 0110 one hundred 110 10 5 500 0111 300 10 00 four 1200 1000 300 0 11 3 900 1001 one hundred 110 11 5 500 1010 one hundred 111 01 5 500 1011 300 10 01 four 1200 1100 one hundred 111 10 5 500 1101 300 10 10 four 1200 1110 300 10 11 four 1200 1111 one hundred 111 11 5 500 Total: 3200 12400

- the inventive method can be used for segments of various lengths;

- the method is easy to implement.

Thus, a higher speed of the data compression and data recovery operation is achieved due to the fact that prefix codes are assigned not to all numbers of length n bits, but only to groups whose number is much smaller, and also due to the fact that the number of computational operations is reduced, particular operations of reading codes of variable length, these computational operations are replaced by the operations of reading records from the table, which takes significantly less time.

A higher compression ratio is achieved due to the fact that operations of grouping numbers are performed and prefix codes are assigned not to all numbers of length n bits, but only to prefix groups.

Claims (1)

A method of compressing and restoring data, according to which equal lengths of segments are selected, into which the stream of compressible data is then divided and denoted by n bits, then the probabilities of each of the numbers of length n bits in the entire compressible data stream are calculated, characterized in that the numbers are combined into prefix groups and denote these groups by prefix codes, while the numbers in the first group are placed with the highest probability and the shortest prefix code is assigned to this prefix group, the next group is also placed the numbers with the highest probabilities of those numbers that were not placed in the previous group and assign the next prefix code to the given prefix group, and the total number of prefix groups should not be more than n, after which in each prefix group all numbers are numbered in order starting from zero and get the serial number in the prefix group, while to record any serial number in a particular prefix group, the number of bits that is necessary to record the maximum serial number in the data is allocated prefix group, and at least the sum of the bit length of the shortest prefix code and the bit length allocated to record the serial numbers of the numbers in the prefix group indicated by the shortest prefix code must be less than n, then numbers from zero to 2n-1 , prefix codes, serial numbers in prefix groups are entered into a table and saved, then the entire stream of compressible data is converted in such a way that instead of the original number of length n bits, the code of the prefix group and the serial number are written in the prefix group, the entire subsequent sequence of actions is repeated for the next number of length n bits, to restore the data stream, read the group prefix code and serial number in the prefix group and, in accordance with the table, replace the group prefix code and serial number in the prefix group with the number corresponding to the group prefix code and the serial number number in the prefix group, then the next group prefix code and the serial number number in the prefix group and the entire subsequent sequence are read actions are repeated.