1. Field of the Invention
The present invention relates to a technique for compression of data and in particular relates to a technique for compression of data by using the Huffman code.
2. Discussion of the Related Art
Generally, for communicating or storing data, compression of data is effective to reduce the amount of stored data. Huffman coding is a typical compression technique.
The Huffman code is a publicly known technique which is described in "Document Data Compression Algorithm Guide", Uematsu, CQ Publishing Company, pp. 46-51, for example. Roughly speaking, in Huffman coding, data is compressed by assigning a short code to a symbol frequently generated and assigning a long code to a symbol rarely generated. An example of the Huffman code is shown in FIG. 13.
The following two items are conditions for rendering the Huffman code effective:
(1) the probability of appearance of each symbol is already known; and PA1 (2) the probability of appearance of each symbol is stationary. Condition (1) originates in that the generation of the Huffman code depends on the probability of appearance of each symbol, and condition (2) originates in that the Huffman coding uses a fixed code table. However, it is necessary to perform a statistical process on the input data before coding to satisfy condition (1) and therefore, the processing load is increased. Condition (2) in general, cannot be satisfied by general input data.
In order to achieve the above conditions, a method of updating the Huffman code at appropriate intervals is known. In this method, condition (1) is unnecessary because the code is designed based on the statistics of the data coded immediately before it. Condition (2) is achieved if the probability of appearance of each symbol varies slightly because the optimum code is used in every updating step. Such a method is discussed in Japanese Patent Application Laid-Open No. Hei. 7-7436 (1995).
FIGS. 15 and 17 are block diagrams illustrating a coding apparatus and a decoding apparatus of the prior art. First, the coding apparatus of the prior art is described with reference to FIG. 15.
In the apparatus of FIG. 15, the input data 100 to be coded is input through the data inputting element 10 and transferred to the frequency counting element 20 and a data memory 90. The frequency counting element 20 counts the frequency of appearance of symbols contained in the input data 100 and transfers the counted value to a code assigning element 40 as frequency data 110. The code assigning element 40 generates code word data 141 based on the frequency data 110 and stores it in a code word memory 60. A Huffman coding element 70 performs the Huffman coding on the input data 100 by using the code word data 141 stored in the code word memory 60 and transfers a coding result to a code outputting element 80 as code data 151. The code outputting element 80 outputs the generated code data 151.
Next the decoding apparatus of the prior art is discussed with reference to FIG. 17. Elements corresponding to elements in FIG. 15 have the same reference numbers as those in FIG. 15 and therefore, their explanations are omitted.
The code data 151 to be decoded is input through a code inputting element 15 and transferred to a Huffman decoding element 75. The Huffman decoding element 75 performs the Huffman decoding for the code data 151 input through the code inputting element 15 by using the code word data 141 stored in the code word memory 60 and transfers a decoding result to a data outputting element 85 as the input data 100. The data outputting element 85 outputs the generated input data 100.
The operation of the prior art apparatuses are now described based on the above construction. FIGS. 16 and 18 are flow charts illustrating a coding operation and a decoding operation of the prior art.
First, the coding process is described with reference to FIG. 16. In step 10, the frequency counting element 20 counts the symbols of each type contained in the input data 100 to obtain the frequency data 110. In step 211, it is determined whether the frequency data 110 satisfies a predetermined condition for the process of updating the code table at that time. If the frequency data 110 satisfies the condition, the process proceeds to step 212. Otherwise, the process proceeds to step 30. In step 212, the code assigning element 40 generates the Huffman code based on the frequency data 110 to obtain the code word data 141 and proceeds to step 30. In step 30, the Huffman coding element 70 performs the Huffman coding for the input data 100 by using the code word data 141 and goes to step 40. In step 40, it is determined whether there is any unprocessed input data 100. If there is, the process returns to step 10. Otherwise, the coding process is completed and ends.
The decoding process is now explained with reference to FIG. 18. Processes corresponding to processes in FIG. 16 have the same step numbers as those in FIG. 16 and their explanations are therefore omitted. In step 50, the Huffman decoding element 75 performs the Huffman decoding for the code data 151 by using the code word data 141.
In the above operation, the same initial value is given to the codes used in the coding and decoding processes. General purpose code or the code specially designed code may be used as input data. In the latter case, it is necessary to identify the code table to the decoding side by assigning the code table to the header of the code data.
The condition for updating the code table in step 212 can be arbitrarily determined. For example, in Japanese Patent Application Laid-Open No. Hei. 7-7436, the conditions are particularly applied to motion pictures and the code table is updated for every frame.
An algorithm for generating the Huffman code in step 213 is not described in detail here because it is publicly known and described in, for example, "Document Data Compression Algorithm Guide", Uematsu, CQ Publishing Company. Generally, in a Huffman code generating algorithm, symbols are sorted in the order of the probability of appearance. Two symbols having low probabilities are combined to generate a new symbol. This process is repeated and codes are assigned to the symbols.
In the prior art, it is desirable that the update of the code table be performed for every unit in which the distribution of the probabilities of appearance of the input symbols is constant. Therefore, the interval of updating should be as short as possible if sufficient statistical materials are available for presuming the distribution of probability of appearance of each symbol. Unlike the description in Japanese Patent Application Laid-Open No. Hei. 7-7436, if the conditions are applied to still pictures, similarity in distribution of probabilities of appearance of each symbol among images cannot be expected. Therefore, the update of the code table in a frame is effective.
The sorting process is frequently used in the process of generating the Huffman code in step 213. For this reason, if the interval of the update of the code table is shortened, the burden to the whole process is increased.
To overcome the above problem, a method described in Japanese Patent Application Laid-Open No. Sho. 63-232626 (1988) has been devised. In the application, symbols are rearranged in the order of frequency of appearance and written to the code table prepared in advance to generate the Huffman code with fewer processes. According to this method, the burden of generating the Huffman code can be reduced because the sorting process is required only one time.
The problem with this method is that there is no assurance of efficient reduction of the amount of code. That is, there is no assurance that an optimum code is generated because many patterns of distribution of probability of appearance are possible even though the symbols are sorted in the order of frequency of appearance.