哈夫曼编码的分析与实现

吉林建筑大学吉林建筑大学 电气与计算机学院电气与计算机学院 信息理论与编码课程设计报告信息理论与编码课程设计报告 设计题目 设计题目 哈夫曼编码的分析与实现哈夫曼编码的分析与实现 专业班级 专业班级 电子信息工程电子信息工程 131 学生姓名 学生姓名 学学 号 号 指导教师 指导教师 设计时间 设计时间 2016 11 21 2016 12 2 教师评语 成绩 评阅教师 日期 0 第 1 章 概述 1 1 设计的作用 目的 通过完成具体编码算法的程序设计和调试工作 提高编程能力 深刻理解 信源编码 信道编译码的基本思想和目的 掌握编码的基本原理与编码过程 增强逻辑思维能力 培养和提高自学能力以及综合运用所学理论知识去分析解 决实际问题的能力 逐步熟悉开展科学实践的程序和方法 主要目的是加深对 理论知识的理解 掌握查阅有关资料的技能 提高实践技能 培养独立分析问 题 解决问题及实际应用的能力 通过课程设计各环节的实践 应达到如下要求 1 理解无失真信源编码的理论基础 掌握无失真信源编码的基本方法 2 根据哈夫曼编码算法 考虑一个有多种可能符号 各种符号发生的概率 不同 的信源 得到哈夫曼编码和码树 3 掌握哈夫曼编码的优缺点 4 通过完成具体编码算法的程序设计和调试工作 提高编程能力 深刻理 解信源编码 信道编译码的基本思想和目的 掌握编码的基本原理与编码过程 增强逻辑思维能力 培养和提高自学能力以及综合运用所学理论知识去分析解 决实际问题的能力 逐步熟悉开展科学实践的程序和方法 1 2 设计任务及要求 1 理解无失真信源编码的理论基础 掌握无失真信源编码的基本方法 2 掌握哈夫曼编码 费诺编码方法的基本步骤及优缺点 3 深刻理解信道编码的基本思想与目的 理解线性分组码的基本原理与编 码过程 4 能够使用 MATLAB 或其他语言进行编程 编写的函数要有通用性 1 3 设计内容 一个有 8 个符号的信源 X 各个符号出现的概率为 04 005 006 0 07 0 1 012 017 0 39 0 87654321 xxxxxxxx XP X 进行哈夫曼编码 并计算平均码长 编码效率 冗余度 1 第 2 章 哈夫曼编码的分析与实现 2 1 哈夫曼编码介绍及原理 哈夫曼编码 Huffman Coding 是一种熵编码编码压缩方式 哈夫曼编码是可 变字长编码 VLC 的一种 哈夫曼压缩是个无损的压缩算法 一般用来压缩文 本和程序文件 哈夫曼压缩属于可变代码长度算法一族 意思是不同符号 例 如 文本文件中的字符 用一个特定长度的位序列替代 因此 在文件中出现 频率高的符号 使用短的位序列 而那些很少出现的符号 则用较长的位序列 哈夫曼编码的码长是变化的 对于出现频率高的信息 编码的长度较短 而对于出现频率低的信息 编码长度较长 这样 处理全部信息的总码长一定 小于实际信息的符号长度 下面给出具体的 Huffman 编码算法 1 首先统计出每个符号出现的频率 如本次课程设计 x1到 x7的出现频率 分别为 0 39 0 17 0 12 0 1 0 07 0 06 0 05 0 04 2 从左到右把上述频率按从小到大的顺序排列 3 每一次选出最小的两个值 作为二叉树的两个叶子节点 将和作为它 们的根节点 这两个叶子节点不再参与比较 新的根节点参与比较 4 重复 3 直到最后得到和为 1 的根节点 5 将形成的二叉树的左节点标 0 右节点标 1 把从最上面的根节点到最 下面的叶子节点途中遇到的 0 1 序列串起来 就得到了各个符号的编码 2 2 哈夫曼编码步骤 1 将信源消息符号按其出现的概率大小依次排列为 12n ppp 2 取两个概率最小的字母分别分配以 0 和 1 两个码元 并将这两个概率 相加作为一个新字母的概率 与未分配的二进制符号的字母重新排队 3 对重排后的两个概率小符号重复步骤 2 的过程 4 不断继续上述过程 直到最后两个符号配以 0 和 1 为止 5 从最后一级开始 向前返回得到各个信源符号所对应的码元序列 即 相应的码子 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 4 哈夫曼编码特点 1 哈弗曼的编码方法保证了概率大的符号应对于短码 概率小的应对于 长码 充分利用了短码 2 缩减信源的最后两个码子总是最后一位不同 从而保证了哈弗曼码是 及时码 3 哈夫曼码没有错误保护功能 在译码时 如果码串中没有错误 那么 就能一个接一个地正确译出代码 但如果码串中有错误 哪怕仅是 1 位出现错 误 不但这个码本身译错 更糟糕的是后面的数据串也会接着被译错 全乱了 套 这种现象称为错误传播 error propagation 计算机对这种错误也无能为力 说不出错在哪里 更谈不上去纠正它 4 哈夫曼编码只能用整数来表示单个符号而不能用小数 这很大程度上 限制了压缩效果 5 哈夫曼所有位都是合在一起的 如果改动其中一位就可以使其数据变 得面目全非 2 5 设计步骤 设一个有 8 个符号的信源 X 各个符号出现的概率为 04 0 05 0 06 0 07 0 1 012 0 17 0 39 0 87654321 xxxxxxxx XP X 则有两种哈夫曼编码方法 0 1 编码或者 1 0 编码 表 1 哈夫曼 0 1 编码过程框图 信源符 号 概率 编码过程码字 码长 X10 39 0 39 0 39 0 39 0 39 0 39 0 61 111 X20 17 0 17 0 17 0 19 0 25 0 36 0 390013 X30 12 0 12 0 13 0 17 0 19 0 250113 X40 1 0 1 0 12 0 13 0 1700004 X50 07 0 09 0 1 0 1201004 X60 06 0 07 0 0901014 X70 05 0 06000105 X80 04000115 i x i p x i W i K 3 该哈夫曼码的平均码长 为K 8 1 0 39 1 0 17 3 0 12 3 0 1 4 0 07 4 0 06 4 0 05 5 0 04 5 2 63 ii i Kp x K 码元 符号 信源熵为 H x 8 1 log bit ii i H xp xp x 0 39l og0 39 0 17l og0 17 0 12l og0 12 0 1l og0 1 0 07l og0 07 0 06l og0 06 0 05l og0 05 0 04l og0 04 2 58 符号 编码效率 2 58 0 98 2 63 H X K 冗余度 11 0 977 0 02 表 2 哈夫曼 1 0 编码过程框图 信源符 号 概率 编码过程码字 码长 X10 39 0 39 0 39 0 39 0 39 0 39 0 61 101 X20 17 0 17 0 17 0 19 0 25 0 36 0 391103 X30 12 0 12 0 13 0 17 0 19 0 251003 X40 1 0 1 0 12 0 13 0 1711114 X50 07 0 09 0 1 0 1210114 X60 06 0 07 0 0910104 X70 05 0 061110 1 5 X80 041110 0 5 信源熵为 H x i x i p x i W i K 1 0 1 0 1 0 1 0 1 0 1 0 1 0 4 8 1 log bit ii i H xp xp x 0 39l og0 39 0 17l og0 17 0 12l og0 12 0 1l og0 1 0 07l og0 07 0 06l og0 06 0 05l og0 05 0 04l og0 04 2 58 符号 该哈夫曼码的平均码长 为K 8 1 0 39 1 0 17 3 0 12 3 0 1 4 0 07 4 0 06 4 0 05 5 0 04 5 2 63 ii i Kp x K 码元 符号 编码效率 2 58 0 98 2 63 H X K 冗余度 11 0 977 0 02 通过以上的两种不同的编码方式进行比较 我们发现其实以上两种编码的 码虽然不同 但是其知识将原来的 1 换成了 0 0 换成了 1 他的码长 编码效 率 冗余度是没有变化的 需要注意的是 对于多进制哈夫曼编码 为了提高编码效率 就要使长码 的符号数量尽量少 概率尽量小 所以信源符号数最好满足 其rnrm 1 中 r 为进制数 n 为缩减的次数 比如说如果要进行三进制编码 那么最好信源 具有 7 个符号 第一次合并后减少 2 个称为 5 个 第二次合并后又减少 2 个称 为 3 个 这样给每一个赋予三进制符号就没有浪费的了 但是如果信源只有 6 个符号的话 为了减少最长码的数量 那么应该在第一次合并是添置为零的虚 拟符号 1 个 事实上只合并 2 个概率最小的符号 后面每次合并 3 个 就可以 是的最长的码的符号数量最少 也就是长码的概率最小 从而得到最高的编码 效率 但是对于信源的某一个符号来说 有时候可能还会比定长码长 例如当 信源有 5 个是 采用定长码方式可用 3 个二进制符号组成码字 而用变长码是 有时候码字却长达 4 个二进制符号 所以编码简单化的代价就是要有大量的储 存设备用来缓冲码字长度的差异 也就是码方差小的码质量好的原因 设一秒 钟送一个信源符号 输出码字却只有 5 个二进制符号 若希望平均每秒输出 个二进制的信息率输出 才能从长久计算 输出和输入保持平衡 当储61 2 k 存量不够大的时候 可能有时取空 有时溢出 例如信源连续发出短码时 就 会出现取空 就是说还没有存入就要输出 连续发出长码时 就会出现溢出 5 就是说存入太多 以致于存满了还未取出就要再次存入 所以应估计所需的存 储器容量 才能使上述现象发生的概率小至可以容忍 当我们计算两个概率之和时 假设这两种的概率之和与上方概率有相同 我们应该把这个和概率放在其相同概率上方还是下方 我们就此进行讨论 设我们有一组概率为 0 4 0 2 0 2 0 1 0 1 则离散无记忆信源 1 01 02 02 04 0 54321 xxxxx XP X 当概率相同放在下方时 哈夫曼编码为 当概率相同放在上方时 哈夫曼编码为 则上面两表给出的哈夫曼平均码长相等 即 K 符号 码元 2 2 8 1i Kixip 编码效率也相同 即 信源 编码 概 率 编码过程 码字 码 长 X10 4002 X20 2102 X30 2112 X40 10103 X50 1 0113 信源 编码 概 率 编码过程码字 码 长 X10 411 X20 2012 X30 20002 X40 100104 X50 1 0 4 0 4 0 6 1 0 0 2 0 4 0 4 0 2 0 2 0 2 00114 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 4 0 4 0 6 0 2 0 2 0 2 0 4 0 2 0 4 1 0 0 1 表 3 哈夫曼编码方法一 表 4 哈夫曼编码方法二 6 965 0 K XH q i iii KkapKkE 1 2 2 2 1 但是两种码的质量不完全相同 可用码方差来表示 即 36 1 2 1 16 0 2 2 由此可见放在上面的哈夫曼编码比放在下面的哈夫曼编码得到的码方差要 小许多 故应该放在上面 2 6 哈弗曼树原理及过程 哈夫曼树 Huffman tree 又名最优树 指给定 n 个权值作为 n 的叶子结 点 构造一棵二叉树 若带权路径长度达到最小 称这样的二叉树为最优二叉 树 也称为哈夫曼树 Huffman tree 哈夫曼树是带权路径长度最短的树 权值 较大的结点离根较近 若将树中结点赋给一个有着某种含义的数值 则这个数 值称为该结点的权 哈夫曼树是一种树形结构 用哈夫曼树的方法解编程题的算法就叫做哈夫 曼算法 树并不是指植物 而是一种数据结构 因为其存放方式颇有点象一棵 树有树叉因而称为树 最简哈夫曼树是由德国数学家冯 哈夫曼 发现的 此 树的特点就是引出的路程最短 哈弗曼最优二叉树步骤 1 初始化 根据给定的 n 个权值构成 n 棵二叉树的集合 12n w ww 其中每棵二叉树中只有一个带权的根结点 左右子树均 12 n FT TT i w 空 2 找最小树 在 F 中选择两棵根结点权值最小的树作为左右子树构造一 棵新的二叉树 且至新的二叉树的根结点的权值为其左右子树上根结点的权值 之和 3 删除与加入 在 F 中删除这两棵树 并将新的二叉树加入 F 中 4 判断 重复前两步 2 和 3 直到 F 中只含有一棵树为止 该树即为 哈夫曼树 7 0 0 0 0 00 0 1 11 11 1 1 X 1 001010 0000 0001000011 01100111 图 1 哈夫曼 0 1 编码树图形 X 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1000 1001 101 110 11100 11101 1111 图 2 哈夫曼 1 0 编码树图形 哈夫曼树也可以是 k 叉的 只是在构造 k 叉哈夫曼树时需要先进行一些调 整 构造哈夫曼树的思想是每次选 k 个权重最小的元素来合成一个新的元素 该元素权重为 k 个元素权重之和 但是当 k 大于 2 时 按照这个步骤做下去可 能到最后剩下的元素少于 k 个 解决这个问题的办法是假设已经有了一棵哈夫 曼树 且为一棵满 k 叉树 则可以计算出其叶节点数目为式子中 11 knk 的 nk 表示子节点数目为 k 的节点数目 于是对给定的 n 个权值构造 k 叉哈夫曼 树时 可以先考虑增加一些权值为 0 的叶子节点 使得叶子节点总数为 这种形式 然后再按照哈夫曼树的方法进行构造即可 11 knk 0 8 第 3 章 哈夫曼编码 C 语言实现 3 1 C 语言编程 3 1 1 程序介绍 本程序的编码和运行都是在 VS2008 中实现的 整个程序虽然看似庞大 但编写过程清晰 采用模块化编写 各个问题逐个击破 也方便对程序的管理 和运行 整个程序的编写分为五大部分 main 主函数 xiaoxi 子函数 add 子函数 coding 子函数 ordination 子函数 五大部分紧密相连 环环相扣 共同实现程序的编码 Main 主函数主要负责其它函数的调用和最后结果的输出 Xiaoxi 子函数主要负责输入需要的概率数据 Add 子函数负责概率相加以便于排序 coding 子函数负责具体编码工作 从右往左逐列编码 在每一列从下 往上逐个编码 与上课时学习的方法稍有不同 其原理相同 ordination 子函数主要负责各个概率间以及概率和的排序 该程序的优点有以下四个方面 1 程序在刚运行的时候需要输入概率数据 程序会启动蜂鸣器 提示需要 输入数据 在输入需要输入的数据个数之后 会再次启动蜂鸣器提醒需要输入 概率数程序具有的提醒功能是本程序的一大特色 2 程序在输入完需要的数据后 会自动排序 而不需要再去麻烦的排序 3 程序在运行过程中会自动检错 错误报警 a 当输入的概率大于 1 或小于 0 的时候 系统会自动提示错误 9 b 当输入的概率之和大于 1 时 系统会自动检错 4 程序的编码过程清晰 编码过程中所有的概率都会在显示窗口显示出来 更清楚易懂 5 若两概率之和与另一概率相等 概率之和会自动排在后面 a 理论上讲求和排序的时候是按照列的形式 但程序按照行的形式 当然了 再完美的计划也会有破绽 这个程序也不可避免地存在些小缺点 b 出错报警时增加蜂鸣器长时间工作 c add 函数语句重复 流程图中已经进行了修改 程序使用说明 该程序是在 VS2008 环境下编写的 运行也需要在 VS2008 中运行 请确 保你在装载有 VS2008 环境下运行 3 2 程序流程图以及说明 10 主程序 N 结束 定义全局数组 a b c d 定义全局变量 定义变量 n x y K 开始 输出编码过程中产 生的新概率 输出码字 输出平均码长 信源熵 编码效 率 冗余度 初始 输出提示 获取 y xiaoxi ordination m a Y 数组 a 一维 存放输入概率 数组 b 二维存放编码过程概率 数组 c 三维 存放编码每个位置即时编 码 数组 d 一维存放码长 i 为整型变量 计 数编码次数 m 为整型 n x 为控制循环整型变量 y 为检错 控制整型变量 K 为存放平均码长浮点 型变量 H 为存放信源熵浮点型变量 三重循环初始化 使其所有值为 2 显示 请输入消息个数 响蜂鸣器 调用获取概率函数 将返回值给 y Y 0 存在错误 结束程序 调用获取概率函数 将返回值给 y 说明 图 3 主程序流程图 3 3 C 语言源程序 include include define w 10 11 float a w b w w 0 f w 0 int i c w w w d w 0 m xiaoxi int n float P 0 printf n 请分别输入消息概率 区间在 0 1 概率之和应为 n a for n 0 n 1 a n 0 printf 出错 概率应在 0 1 范围内 n return 0 break P a n if P 1 printf 出错 概率和应为 1 n return 0 else return 1 ordination int f float e int g j float k for g 0 g f 1 g for j g 1 j f j if e g 0 i t 0 for k m 2 i k 0 k if f i b i 1 k for r 0 c i 1 k r 2 r c i m i 2 r c i 1 k r c i m i 1 r c i 1 k r c i m i 2 r 0 c i m i 1 r 1 for j m i 3 j 0 j for k m 2 i k 0 k if b i j b i 1 k for r 0 c i 1 k r 2 r c i j r c i 1 k r 13 add int j for i 0 i m i b 0 i a i for i 1 i m i b i m i 1 b i 1 m i 1 b i 1 m i f i 1 b i m i 1 for j 0 j m i 1 j b i j b i 1 j ordination m i b i main int n x y float K 0 H 0 for n 0 n w n for x 0 x w x for y 0 y w y c n x y 2 printf n 请输入消息个数 n a scanf d printf n y xiaoxi if y 1 ordination m a add coding printf n 编码过程如下 n for n 0 n m n 14 printf n 第 d 列 n 1 for x 0 x m x if b n x 0 break printf t 5 4f b n x printf n printf n for n 0 n m n printf 概率为 5 4f 的符号编码后码字为 t a n for x 0 x m x if c 0 n x 2 break printf d c 0 n x d n K a n d n H a n log10l a n log10l 2 printf t 其码长为 d n d n printf n 平均码长 K printf 3 2f K printf n 信源熵 3 2f H printf n 编码效率 H K 3 2f H 100 K printf n 冗余度 3 2f n 1 H K 3 4 程序步骤及运行 本程序会对输入的概率自动检错 任何输入大于 1 或小于 0 的概率 或 概率之和不等于 1 系统都会提示错误 15 图 4 仿真纠错情况及结果 进行哈弗曼编码 第一步 输入你所需要的概率个数 如你需要输入概率 x1 x8 请输入 8 点回车键 第二步 输入你所需要的概率 程序会自动排序 如输入概率 x1 x8 分 别点回车键确认 否则请按退格键 第三步 输入完成后 按下回车键 程序会出现结果 图 5 哈夫曼 1 0 编码运行结果显示各列重新排列的概率值 16 图 6 哈夫曼 0 1 编码树运行结果显示各列重新排列的概率值 从运行结果可知该结果与理论一致 并且可以看出哈夫曼编码的 3 个特点 1 哈夫曼码的编码方法保证了概率大的符号对应于短码 概率小的符号 对应于长码 2 缩减信源的最后二个码字总是最后一位码元不同 前面各位码元相同 二元编码情况 从而保证了哈夫曼是即时码 3 每次缩减信源的最长两个码字有相同的码长 这三个特点保证了所得的哈夫曼码一定是最佳码 因此哈夫曼是一种应用 广泛而有效的数据压缩技术 利用哈夫曼编码进行通信可以大大提高信道利用 率 加快信息传输速度 降低传输成本 数据压缩的过程称为编码 解压的过 程称为译码 进行信息传递时 发送端通过一个编码系统对待传数据 明文 预先编码 而接受端将传来的数据 密文 进行译码 17 第 4 章 总结 本次课程设计 让我对哈夫曼编码以及 C 语言有了更深的理解和操作能力 开始针对题目进行分析 将所涉及的知识点 及相关函数做了分析 大体能够 把握整体的设计流程及思路 再通过查阅相关资料 使自己的知识也更加丰富 了 明白了哈夫曼编码的原理以及仿真的实现 首先对给题目进行了计算 进行哈夫曼编码 求出平均码长 编码效率 开始时不是很顺利 以前学的很多书本上的东西记得不太清楚了 经过复习课 本的内容 掌握原理后顺利求出结果 然后是利用 C 语言编写程序 由于我现 在正在公司实习 接触到编程的东西比较多 所以对 C 语言编程还是比较熟悉 的 所以我选择使用 C 语言来实现仿真 仔细研究后得到程序的算法 还有我 也参考了一部分网上的