一种不用构造二叉树的哈夫曼编码

A Huffman coding Algorithm Based on a binary tree

针对传统哈夫曼编码算法都需要建立哈夫曼树的缺点,提出了一种不用建立哈夫曼树也可以进行哈夫曼编码的算法。该算法抛开具体的树结构,只需用一维数组模拟二叉树的创建过程求得每个符号的编码长度,然后根据编码长度为每个符号分配编码。算法分析表明,该算法需要的内存空间比传统哈夫曼编码算法要少很多。同时,算法的时间复杂度为O(n)。

In view of the disadvantage that the traditional Huffman coding algorithm needs to build a huffman tree. this paper presents a huffman coding algorithm that doesn＇ t rely on establishment of the huffman tree. The algorithm can put aside a specific tree structure, and obtain each symbol coding length from simulating tree creation process used only a one-dimensional array. At last, the algorithm can assign a code for each symbol according to the length of code. The example shows that the algorithm requires much less memory space than the traditional huffman coding algorithm. At the same time, the algorithm＇ s time complexity is 0 （n）.