一种不用建造Huffman树的高效Huffman编码算法

Huffman编码作为一种高效的不等长编码技术正日益广泛地在文本、图像、视频压缩及通信、密码等领域得到应用。为了更有效地利用内存空间、简化编码步骤和相关操作,首先研究了重建Huffman树所需要的信息,并提出通过对一类一维结构数组进行相关操作来获取上述信息的方法,然后利用这些信息,并依据提出的规范Huffman树的编码性质,便能直接得到Huffman编码。与传统的Huffman算法及近年来国内外文献中提出的改进算法相比,由于该方法不需要构造Huffman树,不仅使内存需求大大减少,而且编码步骤和相关操作更简洁,因而更利于程序的实现和移植。更重要的是,该算法思路为Huffman算法的研究和发展提供了新的途径。

An Efficient Huffman Coding Algorithm ofNon creating Huffman Tree(NHTC)

As an efficient and simple variable length coding technique, Huffman codes are being widely used in text, image, video compression and so on. To reduce the requirement of the memory space, simplify encoding procedure, a layer information table(LIT) of Huffman tree is discussed to describe and reconstruct Huffman tree. An approach which adopts a special operating technique for a kind of structural array is designed to get data of LIT. A canonical Huffman tree(CAHT) is presented in this paper, and the existence, determination conditions and properties of encoding and decoding for CAHT are proved. Using LIT and encoding properties of CAHT, Huffman codes can be directly found. Comparing with traditional Huffman coding technique and other improved algorithms, the best advantage of the algorithm NHTC proposed in this paper is no need to create Huffman tree, so the operating process and coding procedure are more simplified and memory space requirement is reduced significantly.