Haffman quick decoding method based on probability table look-up

Abstract

The invention relates to a huffman fast decoding method based on the probability table look-up, comprising: reading the code stream in turn in the decoding, looking up the corresponding information in the supplementary table according to the read code stream, and outputting the corresponding character after coding based on the corresponding information, wherein the supplementary table is built according to the huffman table, comprising a plurality of groups of information after coding, and reflecting the probability of occurrence in the code stream of the corresponding character after coding. According to the invention, a supplementary table is built before the huffman decoding, one or a plurality of huffman codes are obtained through one replacement and the 16-bit table look-up under the condition of higher probability of occurrence of the coded character in the data stream, and the reading of the code stream uses word as the unit, while in the lower probability, a huffman code is obtained in the routine way, which advances the coding speed of the huffman.

Description

technical field [0001] The invention relates to a Huffman fast decoding method based on probability look-up table. Background technique [0002] Huffman coding is a kind of entropy coding, which is a lossless compression method of variable word length coding (VLC). Its basic idea is to compress by assigning code values ​​of different lengths to characters with different probabilities of appearance in the data stream. In short, when the character to be encoded has a high probability of appearing in the data stream, a shorter code value is assigned to it, otherwise, a longer code value is assigned to it. Huffman coding is widely used in computer science, and many compressed data formats use Huffman coding as part of their standards. [0003] Generally speaking, Huffman decoding is a simple operation with a computational complexity of O(n), and its computational load is not very large. However, it is still important to increase the Huffman decoding speed in some cases where ...

AI Technical Summary

Problems solved by technology

There are three time-consuming points in this process: First, because Huffman coding is bit-by-bit coding, this process requires more bit operations, and the data reading process is often not a whole byte reading; second, Huffman coding It is a variable-length code, so it is often necessary to repeat several operations to obtain the corresponding code value; again, for a modern CPU, the length of its register is often 16 or 32 bits, but the length of the Huffman code is often only a few bit, which does not effectively utilize the width of the register

Images