KR101023536B1 - Lossless data compression method - Google Patents

Abstract

The present invention proposes a data lossless compression method that can improve the compression efficiency by compressing data by applying the Huffman coding method while updating the Huffman table whenever a specific symbol frequency is reduced to zero.

Description

Data Lossless Compression Method {LOSSLESS DATA COMPRESSION METHOD}

The present invention relates to a data lossless compression method, and more particularly, to a data lossless compression that improves the compression efficiency by applying a Huffman coding method while updating a Huffman table whenever a specific symbol frequency is reduced to zero. It is about a method.

In general, as a method of lossless compression of data, the entropy coding method is most widely used. A compression method that compresses data and restores the data exactly the same as the original data is called lossless compression.

The entropy coding method is called variable-length coding because a short code is assigned to a symbol with high occurrence frequency and a long code is assigned to a symbol with low frequency.

In entropy coding, only the frequency of symbols is taken into consideration. As a representative method, Huffman coding is used.

In other words, entropy coding requires optimal knowledge of the appearance of each symbol beforehand, and Huffman coding allows only one codeword of integer length because one codeword is assigned to each symbol.

For example, for X ₇ = { AAABBCD }, a conventional Huffman table is created as shown in Figure 2 based on FIG.

1 is a diagram illustrating a conventional Huffman tree, and FIG. 2 is a Huffman table created based on the Huffman tree of FIG. 1.

That is, if X ₇ is encoded by the Huffman table shown in Figure 2, the result is Y ₇ = {000 10 10 110 111}, which requires 13 bits.

Here, A is converted to 0, B to 10, C to 110, and D to 111, respectively.

As described above, in the conventional Huffman coding, once the Huffman table is created, the same codeword is assigned to all symbols until the coding is completed, and the assigned codeword is not changed.

In addition, the conventional entropy coding is almost close to the limit of compression, even if the compression efficiency is higher, there is a problem that can not be compressed to less than entropy beyond the limit to approach closer to the entropy of the limit of lossless compression.

In other words, there is a need to develop a new method that can compress below entropy.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and an object thereof is to update the Huffman table each time a specific symbol frequency is reduced to 0, and simultaneously compress data by applying the Huffman coding method to improve data compression efficiency. It is to provide a lossless compression method.

That is, an object of the present invention is to provide a data lossless compression method that can improve the compression efficiency by updating the Huffman table while changing coding to change the frequency of symbols, and regenerating the Huffman table according to the changed frequency.

In one aspect of the present invention for achieving the above object, a method of lossless compression of data using a Huffman table defining a frequency and a frequency of each symbol constituting an input symbol string for compression, Sequentially selecting symbols constituting the target symbol string according to an arrangement order, replacing the selected symbol with a codeword defined corresponding to the type of the selected symbol in the Huffman table; When the substitution of the symbol corresponding to the type is completed, reconstructing the Huffman table by reducing the number of bits of codewords for the remaining symbols except for the symbol corresponding to the specific type by one bit in the Huffman table; If there are no more symbols to select in the compression target symbol column, the substitution Comprises the step of lossless compressed symbol column outputs the code words generated by the heat process.

Preferably, the number of symbol types consecutively present in the compression target symbol string is counted, the frequency count for each symbol type is calculated based on the count value, and an initial Huffman table is configured by the calculated frequency for each symbol type. The process further includes.

In another aspect of the present invention for achieving the above object, a method of losslessly restoring data using a Huffman table defining a frequency and a type of symbols constituting an input symbol string for compression and a codeword is lossless. Sequentially selecting codewords registered in the Huffman table in a compressed symbol string according to an arrangement order, and replacing the selected codewords with symbols defined corresponding to the selected codewords in the Huffman table; When the substitution for the specific type of symbol corresponding to the frequency defined for the specific type in the Huffman table is completed, the codeword for the other types of symbols except for the specific type of symbol in the Huffman table Reconfigure the Huffman table by reducing the number of bits by 1 bit. And if the codeword to be selected no longer exists in the lossless compressed symbol string, outputting the symbol string generated by the replacing process as a restored symbol string.

Preferably, the Huffman table records frequency and codewords for each type of symbols constituting the restored symbol string or for each type of symbols except for symbols that have already been restored.

According to the data lossless compression method according to the present invention, since the Huffman table is changed by changing the frequency of symbols while coding, the Huffman table is re-created according to the changed frequency, thereby increasing the compression efficiency.

Other objects and advantages of the present invention in addition to the above object will be apparent from the detailed description of the embodiments with reference to the accompanying drawings.

Hereinafter, a data lossless compression method according to the present invention will be described in detail with reference to the accompanying drawings.

3 is a block diagram illustrating a system applied to a method for compressing and restoring data lossless according to an embodiment of the present invention.

As shown in FIG. 3, a system applied to a data lossless compression and decompression method according to an embodiment of the present invention includes an encoder 100 encoding an input symbol string X _n and an encoder 100. A decoder 200 for decoding the encoded symbol string.

Specifically, the encoder 100 encodes and outputs the Huffman table 110 created by the input symbol string X _n and the input symbol string based on the Huffman table 110. 120.

On the other hand, the decoder 200 is based on the Huffman table 220 for storing the information required to decode the compressed symbol string (Y _n ) output from the entropy encoder 120, and based on the Huffman table 220 An entropy decoding unit 230 for decoding and outputting the compressed symbol string.

In this case, the encoder 100 and the decoder 200 have a structure of updating the Huffman table based on the exact frequency of the symbols.

On the other hand, a method for data lossless compression and decoding through the system configured as described above will be described below.

Here, the input symbol string X _n input to the Huffman table 110 of the encoder 100 is composed of a combination of _m source symbols s ₀ , s ₁ , ..., s _m-1 , and the input The symbol string X _n is represented by {x ₀ , x ₁ , ..., x _n-1 }.

That is, since the input symbol string X _n is constituted by a combination of _m source symbols s ₀ , s ₁ , ..., s _m-1 , the total number of symbols _{n of} the input symbol string X n ) Is greater than or equal to the source symbol number m. Accordingly, each input symbol constituting the input symbol string X _n corresponds to one of the source symbols, and a plurality of source symbols may exist in the input symbol string X _n .

In addition, the source symbol set is S _m , and Sm may be represented by {s ₀ , s ₁ , ..., s _m-1 }. And the source symbols within a target symbol sequence (X _n) to compress the frequency of s _k is denoted by _k n, the number of symbols corresponding to symbol x _i is denoted by N (x _i). Therefore, since the input symbol x _i is an element of S _m , if s _k = x _j, then N (x _i ) = n _k .

Meanwhile, the compressed symbol string output through the entropy encoder 120 of the encoder 100 is represented by Y _n , and the compressed symbol string Y _n = (y ₀ , y ₁ , ..., y _{n − The} compressed symbol y _i constituting ₁ } may be generated by mapping the source symbol s _k to the codeword c _k . In this case, the codeword set is C _m , and C _m may be represented by {c ₀ , c ₁ , ..., c _m-1 }.

Here, a method of encoding the input symbol string X _n input to the encoder 100 will be described with reference to FIG. 4.

4 is a flowchart illustrating a method of encoding an input symbol string according to an embodiment of the present invention.

First, the frequency per source symbol (n ₀ , n ₁ , ..., n _{m- in the} input symbol column (( x _n ) = (x ₀ , x ₁ , ..., x _n-1 })) ₁ ) is calculated (S310).

Next, an initial Huffman table is configured based on the frequency number n ₀ , n ₁ , ..., n _{m-1 for} each source symbol calculated through the step S310 (S312). As shown in FIG. 2, the initial Huffman table may be configured as a codeword corresponding to a frequency number for each source symbol.

At this time, the variable i is initialized ( i = 0) (S314). The variable i is an index for designating a target symbol to be compressed in the input symbol string, and is used to sequentially select a symbol for substitution by a codeword according to a sequence of symbols constituting the input symbol string.

Then, if the input symbol x _i corresponds to s _k in the source symbol set (that is, x _i = s _k ), then check the frequency number n _k of that source symbol from the Huffman table (that is, N (x _i ) = n _k ) (S316).

After acquiring the codeword c _k registered corresponding to the source symbol s _k in the Huffman table, the input symbol x _i is replaced with the obtained c _k to output the compressed symbol y _i (that is, y _i = c). _k ) (S318).

Thereafter, as the compression of the input symbol x _i is performed, the frequency n _k of the previously identified s _k in the input symbol string decreases, so that N (x _i ) means the number of s _k in the input symbol string. Reduces 1 (S320).
Then, it is determined whether N (x _i ) is 0 based on the result of step S320 (S322). When N (x _i ) is 0, compression of all symbols having the same value as s _k existing in the input symbol string is completed.
Therefore, when N (x _i ) is determined to be 0, the Huffman table is newly formed by removing the corresponding source symbol s _k from the existing Huffman table, and newly defining a codeword in consideration of the frequency of the remaining source symbols. S324).

If it is determined that N (x _i ) is not zero or a new Huffman table is configured, the variable i is added (i = i + 1) (S326). Thereafter, it is determined whether or not the compression for the input symbol string is completed based on whether the variable i is equal to the total number of symbols n (S328). If the compression is completed, a compressed symbol string (Y _n = {y ₀ , y ₁ , ..., y _n-1 }) based on the compressed symbols obtained in S318 is output (S330). However, if the compression is not completed, return to the step S316.

Meanwhile, a method of decoding the compressed symbol string Y _n output from the encoder 100 through the decoder 200 will be described with reference to FIG. 5.

5 is a flowchart illustrating a method of decoding an output symbol string according to an embodiment of the present invention.

First, the frequency per source symbol (n ₀ , n ₁ , ..., n _{m- in the} input symbol column (( x _n ) = (x ₀ , x ₁ , ..., x _n-1 })) ₁ ) is calculated (S410).

Next, an initial Huffman table is configured based on the frequency number n ₀ , n ₁ , ..., n _{m-1 for} each source symbol calculated through the step S410 (S412). As shown in FIG. 2, the initial Huffman table may include a codeword corresponding to a frequency number for each source symbol.

Then, decoding starts on the compressed symbol string (Y _n = {y ₀ , y ₁ , ..., y _n-1 }).

At this time, the variable i is initialized ( i = 0) (S414). The variable i is an index specifying a target symbol to be restored in the compressed symbol string.

Next, if the compressed symbol y _i corresponds to s _k in the set of source symbols (that is, y _i = s _k or x _i = s _k ), then check the frequency number n _k of that source symbol from the Huffman table (that is, N (x _i ) = n _k ) (S416).

And by substituting in the Huffman table as the compressed symbol y _i by the corresponding acquisition of the code symbol x _i registered in correspondence to the word c _k, which then, the symbol x _i by the acquiring the compressed symbol y _i (namely, x _i = s _k ) (S418).

Thereafter, as the compression symbol y _i is restored, the frequency n _k of the previously identified s _k decreases, so that N (x _i ) representing the number of s _k in the symbol string to be output is decreased by 1 ( S420).
Then, it is determined whether N (x _i ) is 0 based on the result of step S420 (S422). When N (x _i ) is 0, the restoration of all symbols having the same value as s _k existing in the symbol string to be output is completed.
Therefore, when N (x _i ) is determined to be 0, the Huffman table is newly formed by removing the corresponding source symbol s _k from the existing Huffman table, and newly defining a codeword in consideration of the frequency of the remaining source symbols. S424).

If it is determined that N (x _i ) is not zero or a new Huffman table is configured, the variable i is added (i = i + 1) (S326). Thereafter, it is determined whether the restoration of the compressed symbol string is completed through whether the variable i is equal to the total number of symbols n (S428). If the restoration is completed, a compressed symbol string (X _n = {x ₀ , x ₁ , ..., x _n-1 }) based on the compressed symbols obtained in S318 is output (S430). However, if the restoration is not completed, the flow returns to step S416.

Meanwhile, an example of the above-described encoding and decoding method will be described.

Here, the Huffman table of the example will be used by applying the Huffman table of FIG. 2, and the Huffman table of FIG. 2 is stored in the encoder 100.

First, three symbols A are converted into three bits of zeros by the Huffman table of FIG. Therefore, if symbol A is converted three times, the frequency of A becomes zero.

Accordingly, the input symbol string becomes X ₄ = {BBCD}, and the Huffman table newly created based on the frequency count for each symbol constituting the input symbol string X ₄ is shown in Table 1 below.

symbol frequency Codeword S ₀ A 0 c ₀ S ₁ B 2 c ₁ 0 S ₂ C One c ₂ 10 S ₃ D One c ₃ 11

According to the Huffman table shown in Table 1, symbol B can be assigned 0, which is 1 bit as a codeword, 10 as 2 bits as a codeword for C, and 11 which is 2 bits as a codeword for D. Will be. That is, the bits constituting the codeword are reduced by one bit compared to the bits defined in FIG.

Therefore, since the frequency corresponding to B is 2, 0, which is 1 bit, is assigned to each of the two Bs.

The Huffman tree created based on Table 1 is shown in FIG. 6.

When each of the two Bs is converted to 0, which is 1 bit, the frequency of the B is reduced to zero.

Thus, a symbol with a frequency of zero appears, so we rebuild the Huffman table. That is, the input symbol string becomes X ₂ = {CD}, and the newly generated Huffman table based on the frequency for each symbol constituting the input symbol string X ₂ is shown in Table 2 below.

symbol frequency Codeword S ₀ A 0 c ₀ S ₁ B 0 c ₁ S ₂ C One c ₂ 0 S ₃ D One c ₃ One

According to the Huffman table shown in Table 2, the symbol C can be assigned 0, which is 1 bit in the codeword, and 1, which is 1 bit in the codeword. That is, the bits constituting the codeword decrease by one bit as compared with the bits defined in Table 1.

Therefore, since the frequency corresponding to the symbol C is 1, 0, which is 1 bit, is assigned to one C.

The Huffman tree created based on Table 2 is shown in FIG. 7.

Since the above operation showed a symbol having a frequency of 0, the Huffman table is recreated. That is, the input symbol string becomes X ₁ = {D}, and the Huffman table newly created based on the frequency of the symbols constituting the input symbol string X ₁ is shown in Table 3 below.

symbol frequency Codeword S ₀ A 0 c ₀ S ₁ B 0 c ₁ S ₂ C 0 c ₂ S ₃ D One c ₃ 0

Therefore, the codeword made by the above-described encoding method is Y ₇ = {0 0 0 0 0 0 0}. That is, the compressed symbol string output through compression on seven input symbols includes only 7 bits. In this case, since 7 bits representing the compressed symbol string are all 0, further compression is possible.

Meanwhile, a method of decoding a symbol string encoded by the above-described method is as follows.

Here, the Huffman table of the example will be used by applying the Huffman table of FIG. 2, and the Huffman table of FIG. 2 is stored in the decoder 200.

First, the decoder 200 starts decoding on the compressed symbol string Y ₇ = {0 0 0 0 0 0 0}. Referring to FIG. 2, the first zero corresponds to symbol A. In addition, the Huffman table confirms that the frequency corresponding to the symbol A is three.

Therefore, in the compressed symbol string, three symbols A are successively output instead of three consecutive zeros. After outputting the three symbols A continuously, the frequency of the symbol A becomes zero.
As a symbol having a frequency of 0 is generated, the Huffman table is reconstructed in consideration of the remaining frequency of each symbol, as shown in Table 1 above. In this case, it can be seen that the codewords assigned to the remaining symbols in the newly created Huffman table are reduced by one bit compared to the codewords in the previous Huffman table.
It can be seen that the next codeword 0 corresponds to symbol B. In addition, according to the newly generated Huffman table, since the frequency corresponding to the symbol B is 2, two codewords having a value of 0 are successively output as two symbols B. Therefore, the frequency of symbol B becomes zero.
As a symbol having a frequency of 0 is generated, when the Huffman table is again created in consideration of the remaining frequency of each symbol, it becomes as shown in Table 2 above.

Repeating the above process restores exactly the original symbol string X ₇ = { AAABBCD }.

That is, the method proposed through the data lossless compression method according to the present invention excludes the coded symbols and creates a table using the symbols to be coded in the future.

On the other hand, when the bit rate of the conventional adaptive Huffman coding is represented by R _A (X), a relationship of R _H (X _n ) ≦ R _A (X _n ) is established. That is, the adaptive Huffman coding method is used to achieve the best performance in consideration of unknown probability distribution while taking some reduction in bit rate.

However, the relationship between _{R K (X n) ≤ R} H (X n) is formed to define the bit rate of the method proposed in the present invention as R _K (X _n).

For reference, when coding for the above example X ₇ = { AAABBCD }, entropy H (X ₇ ) is 1.8424 bits / symbol.

In comparison, as a result of conventional Huffman coding, the bit rate R _H (X ₇ ) becomes 1.8575 bits / symbol. The output at this time is Y = {0 0 0 10 10 110 111}. In other words, the output for the seven input alphabets is 13 bits.

However, when coding with the method proposed in the present invention, the output is 7 bits with Y ₇ = {0 0 0 0 0 0 0}.

Therefore, R _K (X ₇ ) discloses that only 1 bit / symbol can be compressed even below entropy. For reference, various outputs of the input consisting of three symbols A, two symbols B, one symbol C, and one symbol D are shown in Table 4 below.

input Output of the present invention Bit rate Conventional coding output Bit rate AAABBCD 0000000 1.0000

0001010110110



1.8571

ABBAACD 010100000 1.2857 BBAAACD 101000000 1.2857 CBAABAD 11010001001 1.5714 CDBBAAA 1101111000 1.4286

As shown in Table 4 above, although the bit rate varies depending on the type of the input string, it can be seen that it is lower than entropy in any case.

Although the present invention has been described above according to an embodiment of the present invention, a person having ordinary skill in the art to which the present invention pertains has been changed and modified without departing from the technical spirit of the present invention. Of course.

1 is a diagram illustrating a conventional Huffman tree.

FIG. 2 illustrates a Huffman table based on the Huffman tree of FIG. 1. FIG.

3 is a block diagram showing a system applied to the data lossless compression method according to an embodiment of the present invention.

4 is a flowchart illustrating a method of encoding an input symbol string according to an embodiment of the present invention.

5 is a flowchart illustrating a method of decoding an output symbol string according to an embodiment of the present invention.

6 shows a Huffman tree created based on Table 1;

7 shows a Huffman tree created based on Table 2. FIG.

* Description of the symbols for the main parts of the drawings *

100: encoder 110: Huffman table

120: entropy encoding unit 200: decoder

220: Huffman table 230: entropy decoding unit

Claims (4)

A method of losslessly compressing data using a Huffman table defining a frequency and a codeword for each type of symbols constituting an input symbol string for compression, Sequentially selecting symbols constituting the compression target symbol sequence according to an arrangement order, replacing the selected symbols with codewords defined corresponding to the type of the selected symbol in the Huffman table; When the substitution of a symbol corresponding to a specific type in the compression target symbol string is completed, the Huffman is reduced by one bit in the Huffman table by decreasing the number of bits of codewords for the symbols of the other types except for the symbol corresponding to the specific type by one bit. Reorganizing the table, And if a symbol to be selected no longer exists in the symbol string to be compressed, outputting a codeword string generated by the substituting process as a lossless compressed symbol string. The method of claim 1, Counting the number of symbol types consecutively present in the compression target symbol string, calculating the frequency for each symbol type based on the count value, and constructing an initial Huffman table based on the calculated frequency for each symbol type Data lossless compression method further comprising. A method for losslessly restoring data by using a frequency count for each type of symbols constituting an input symbol string for compression and a Huffman table defining a codeword, Sequentially selecting codewords registered in the Huffman table in the lossless compressed symbol string according to an arrangement order, and replacing the selected codewords with symbols defined corresponding to the selected codewords in the Huffman table; When the substitution for the specific type of symbol corresponding to the frequency defined for the specific type in the Huffman table is completed by the substituting process, for the other types of symbols except for the specific type of symbol in the Huffman table Reconfiguring the Huffman table by reducing the number of bits of a codeword by one bit; And if the codeword to be selected is no longer present in the lossless compressed symbol string, outputting the symbol string generated by the substituting process as a restored symbol string. The method of claim 3, wherein And the Huffman table records frequency numbers and codewords for each type of symbols constituting the restored symbol string or for each type of symbols except for symbols that have already been restored.

Images