Huffman算法的分析与改进.pdfVIP

第 22 卷 　第 3 期 兰 州 铁 道 学 院 学 报 ( 自 然 科 学 版 ) Vol. 22 No. 3 2003 年 6 月 JOURNAL OF LANZHOU RAIL WA Y UNIVERSITY (Natural Sciences) J une. 2003 ( ) 　　文章编号 :1001 - 4373 2003 03 - 0120 - 02 Huffman 算法的分析与改进 韩俊英1 ,2 , 　韩 　虎3 ( 1. 兰州大学 信息科学与工程学院 ,甘肃 兰州 　730000 ; 2. 甘肃农业大学 计算机与信息技术系 ,甘肃 兰州 　730070 ; 3. 兰州交通大学 数理与软件工程学院 ,甘肃 兰州 　730070) 摘 　要 :数据压缩是信息科学中的一项重要的技术 ,利用 Huffman 算法得到的前缀码可以使文件总编码长度最短. 通过对算法进行分析和改进 ,优化了算法 ,从而使 Huffman 编码更简洁 、实用. 关键词 :前缀码 ; Huffman 算法 ;WPL 中图分类号 : TP311. 12 　　　　　文献标识码 :A 件总编码长度最短, 就必须要确定 l i , 使 WPL = 0 　引言 n p i ×l i 最小. WPL 表示树的带权路径长度, 定义 ∑ 数据压缩是信息科学中的一项重要的技术 ,有 i = 1 着广泛的应用. 它可以使存储的文件变小 ,也可以提 为树中的所有叶子结点的权值与叶结点的路径长乘 高模块之间数据交换的速度等. 通常 ,文件是由字符 积之和[ 3] . 构成的 ,而字符在计算机中是由二进制串表示的. 这 为了设计出使 WPL 最小的前缀码 ,Huffman 于 就是说 ,如果字符集包含 C 个字符 , 则在标准的等 1952 年提出了哈夫曼算法, 描述如下 : ) 长编码中 ,每个字符由 ┌log c ┐位的二进制串表示. 1 根据给定的 n 个权值的集合 W = { w 1 , w 2 , 2 …, w } , 构成 n 棵二叉树的集合 F = { T , T , …, 但在实际应用的一些大文件中 ,字符被使用的比率 n 1 2 T } , 其中每棵二叉树 T 的根结点的权值为 w , 其 不是平均的 ,有时甚至相差很悬殊. 因此 ,如果所有 n i i 字符都由等长的二进制码表示 ,那么将造成一定的 左右子树均为空; 空间浪费. 为了尽量减少