基于二叉树和一维数组的哈夫曼编码  

Huffman Coding based on Binary Tree and One-dimensional Array

作　　者：石博文[1] 苑海朝 路慧泽 闫英娜[1] 

机构地区：[1]河北农业大学理工学院,河北沧州061000

出　　处：《通信技术》2017年第5期867-872,共6页Communications Technology

摘　　要：传统哈夫曼编码借助二叉树构造,算法实现时使用指针和结构体,空间中的每个结点有左右子树、双亲结点。提出一种新的实现算法,以减少循环重数,降低时间复杂度。新算法抛开二叉树结构,用一个一维数组模拟二叉树的构造过程,并得到字符编码的长度,然后根据编码长度为每个字符分配编码。算法分析表明,传统哈夫曼编码采用自底向上的编码方式,时间复杂度为O(n^2),而新算法采用自顶向下的编码方式,时间复杂度为O(n)。Traditional Huffman Coding is structured in the way of binary tree, and implemented with the pointer and structural morphology for algorithm. Every node in space has left, right sub-trees and parents node. Meanwhile, a novel implementation algorithm of Huffman Coding is proposed, thus to remove binary tree structure. And a one-dimensional array is used to simulate the creation process of binary tree so as to obtain the depth of symbol coding, and then a code is assigned to each symbol according to this information. Algorithm analysis indicates that the traditional Huffman Coding is based on the bottom-up coding, and the time complexity is O（n^2）, while the new algorithm based on the top-bottom coding, the time complexity isO（n）.

关 键 词：前缀码 哈夫曼树 一维数组 编码长度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]