静态哈夫曼编码的原理及应用

1、 收稿日期 :20090118 作者简介 :女 ,1972年生 , 讲师 , 张家口市 ,075024静态哈夫曼编码的原理及应用康洪波河北建筑工程学院摘 要 介绍的哈夫曼编码就是一种无损压缩编码 , 应用非常广泛 .关键词 哈夫曼编码 ; 数据压缩中图分类号 TP3 哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的 , 它借助了数据结构当中的树型结构 , 在 哈夫曼算法的支持下构造出一棵最优二叉树 , 我们把这类树命名为哈夫曼树 . 因此 , 准确地说 , 哈夫曼编 码是在哈夫曼树的基础之上构造出来的一种编码形式 , .那么 , ?众所周知 , 在计算机当中 , , 个字节来表达 , 而一个

2、汉字就要用两个字节 , 形式称为定长编码 . 以西文为例 , :I am a teacher. 就需要 15个字节 , 也就是 . 它根据字符出现的概率来构造平均长度最 短的编码 . , 它的编码就相应的短 , 如果一个字符 在一段文档当中出现的次数少 , 它的编码就相应的长 . 当编码中 , 各码字的长度严格按照对应符号出现 的概率大小进行逆序排列时 , 则编码的平均长度是最小的 . 这就是哈夫曼编码实现数据压缩的基本原理 .要想得到一段数据的哈夫曼编码 , 需要用到三个步骤 :第一步 :扫描需编码的数据 , 统计原数据中各 字符出现的概率 . 第二步 :利用得到的概率值创建哈夫曼树 . 第

3、三步 :对哈夫曼树进行编码 , 并把编码后 得到的码字存储起来 .我们依然以 I am a teacher. 这句话为例 , 来创建属于它的哈夫曼编码 .首先 , 扫描这句话可以得出每一个字符出现的概率 , 并把它记录下来 , 形成一个集合 , 为计算方便 , 我们以近似整数值来代替概率值 , 如表 1所示 .表 1字符I 空格 a m t e c h r . 总字符数 次数133112111115概率0106701201201067010670113010670106701067010671概率近似整数值 7191977137777100 其次 , 利用这些概率值构造哈夫曼树 .哈夫曼树是在

4、哈夫曼算法的支持下建构起来的 , 它的具体实现过程如下 :首先从的概率集合 7191977137777中选择概率最小的两个如 r 及 1连同这两个字符的概率之和 14, 构成一棵子树 , 并 将这两个字符的概率之和放回集合当中 , 构成一个新的集合 7191977137714, 然后再在这个集合 中取概率最小的两个数值 , 以及概率之和构成子树 , 生成新的集合 7191977131414, 依照这样的规 则 , 就可以建立起一棵哈夫曼树 , 如下图所示 .通过观察可以发现 , 这棵哈夫曼树的叶子结点全部由原文档中的数据字符构成 . 其他结点都有两个 第 27卷 第 1期 2009年 3月 河

5、 北 建 筑 工 程 学 院 学 报 JOURNAL OF HEBEI INSTITUTE OF ARCHITECTURE AND CIVIL ENGINEERING V ol 127No 11March 2009 后继结点 , 把每一个结点的左分支标注为 1, 而把每一个结点的右分支标注为 0, 从根结点开始到需要编 码字符为至 , 所有分支上标注的数据将构成一个集合 , 这集合就是该字符的哈夫曼编码 , 例如 e 的编码 就是 (1,1,1 而 h 的编码就是 (1,0,0,0 , 这就完成了哈夫曼编码的第三步 . 也就得到了 I am a teacher. 这句话的哈夫曼编码如下 : I

6、 :000 空格 :101 a :01 m :0011 t :0010 e :111 c :1001r I 空格 a m 空格 a 空格 t a h e h r .48个字符 , 和 ASCII 码 120个字符相比 , , 而我们构造哈夫曼树的过程是严格按照 , 这就保证了文档当中出现的次数多的字符出现在了整棵树的相对高一些 的层次上 , 编码就相应的短 , 而在文档当中出现的次数少的字符出现在了整棵树的最下层 , 它的编码就 相应的长 . 那么这组编码能否实现准确的解码呢 ?我们再来观察一组字符 :a b c d , 它们的编码分别为 :0,10,101,11, 如果我们得到的压缩数据为

7、1010时 , 那么在解压缩时就会存在两种翻译的可能 , 一种为 bb , 另一种为 ca , 为什么会出现这样的现象 呢 ? 通过观察我们发现 , 字符 b 的编码为 10, 而字符 c 的编码为 101,b 的编码恰好是 c 的编码的前两 位 , 就造成了 b 的编码添加一位就有可能成为 c , 这就增加了解压缩的过程中误码的可能 . 因为定长编 码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀 , 所以这种情况只 会出现在变长编码当中 , 要想避免这种情况 , 我们就必须用一个条件来制约定长编码 , 这个条件就是要 想成为压缩编码 , 变长编码就必须是前缀编码 .

8、什么是前缀编码呢 ? 所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀 . 那么哈夫曼编码是否是前缀编码呢 ? 观察 a 、 b 、 c 、 d 构成的编码树 , 可以发现 b 之所以成为 c 的前缀 , 是 因为在这棵树上 ,b 成为了 c 的父结点 , 从在哈夫曼树当中 , 原文档中的数据字符全都分布在这棵哈夫 曼树的叶子位置 , 从而保证了哈夫曼编码当中的任何一个字符的编码都不能是另一个字符编码的前缀 . 也就是说哈夫曼编码是一种前缀编码 , 也就保证了解压缩过程当中译码的准确性 .哈夫曼编码的解压缩过程也相对简单 , 就是将编码严格按照哈夫曼树进行翻译就可以了 , 例如

9、遇到000, 就可以顺着哈夫曼树找到 I , 遇到 101就可以顺着哈夫曼树找到空格 , 以此类推 , 我们就可以很顺利的找到原来所有的字符 .哈夫曼编码是一种一致性编码 , 有着非常广泛的应用 , 例如在J PEG 文件中 , 就应用了哈夫曼编码来实现最后一步的压缩 ; 在数字电视大力发展的今天 , 哈夫曼编码成为了视频信号的主要压缩方式 .应当说 , 哈夫曼编码出现 , 结束了熵编码不能实现最短编码的历史 ,也使哈夫曼编码成为一种非常重要的无损编码 .(下转第 144页 621 河 北 建 筑 工 程 学 院 学 报 第 27卷现代化管理进程 .综上所述 , 高校教学档案管理工作是学校教学

10、管理工作的重要组成部分 . 加强教学档案管理工作是 强化教学管理的需要 , 是深化教学改革的需要 , 也是提高教学质量的需要 . 可以想见 , 以计算机及其网络 作为工具或基本工作环境自动或半自动地代替人来从事档案管理工作是时代发展的需要 . 它对于提高 教学档案的保存和利用有着不可低估的作用 . 随着高校科技教育网的兴起和普及 , 必将带动档案的全面 信息化 .On the Computer Management of T eaching Files in Colleges Zhong Xi aoch u n 1, Zh u Y i ngli ng 1, Dai Cha ngm i ng 1

11、, L i J i a n h u a 2, D u Ch u n mei 111Hebei Institute of Architecture civil Engineering21Zhangjiakou Maternity and Child 2care CentreAbstract As one of t he college files , teaching files are playing an equally role t hroughout t he teaching management and p ractice. The rising p t education webs

12、ite of colleges and universities must f ully driveK ey w ords teaching files ; comp uter(上接第 126页 On Theory and Application of H uff m an CodingKa ng HongboHebei Institute of Architecture and Civil EngineeringAbstract This article described a lossless comp ressio n encoding t he Huff man coding ,whi

13、ch has a wide range of applications.K ey w ords t he Huff man coding ; data compression(上接第 138页 On The Vibration La w of the Vibration Systemof the V ertical Suspending Light SpringCui Hongn aHebei Institute of Architecture and Civil EngineeringAbstract This paper is intended to st udy t he movement of t he vibration system of t he vertical suspen 2 sion sp rings by t he energy law , in which t he quality of sp ring can not be ignored. In addition , it also o btains t he differential equation of t heir movement s and t