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

• 作者: 石博文 苑海朝 路慧泽 闫英娜
• 来源期刊: 通信技术
• 学科: 工学
• 关键词: 前缀码 哈夫曼树 一维数组 编码长度
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 信息处理与传输
• 页码范围: 867-872
• 页数: 6页
• 分类号: TP301.6
• 字数: 3355字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-0802.2017.05.006

摘要

传统哈夫曼编码借助二叉树构造,算法实现时使用指针和结构体,空间中的每个结点有左右子树、双亲结点.提出一种新的实现算法,以减少循环重数,降低时间复杂度.新算法抛开二叉树结构,用一个一维数组模拟二叉树的构造过程,并得到字符编码的长度,然后根据编码长度为每个字符分配编码.算法分析表明,传统哈夫曼编码采用自底向上的编码方式,时间复杂度为O(n2),而新算法采用自顶向下的编码方式,时间复杂度为O(n).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	路慧泽	河北农业大学理工学院	5	44	4.0	5.0
2	苑海朝	河北农业大学理工学院	6	10	1.0	3.0
3	石博文	河北农业大学理工学院	2	15	2.0	2.0
4	闫英娜	河北农业大学理工学院	1	8	1.0	1.0