数据结构与算法实训

数据结构与算法数据结构与算法 实训实训 哈夫曼编 译码器哈夫曼编 译码器 一 问题描述一 问题描述 哈夫曼树哈夫曼树又称最优二叉树最优二叉树 它是一类带权路径长度最短的树 有着广泛的应用 如 JPEG 中就应用了哈夫曼编码 在给出哈夫曼树的定义之前 首先给出路径和路径长度的概 念 从树中的一个节点到另一个节点之间的分支构成这两个节点之间的路径 路径上的分 支数目称为路径长度路径长度 树的路径长度树的路径长度是从树根到树中每一节点的路径长度之和 根据树的 路径长度 可知在节点数目相同的二叉树中 完全二叉树的路径长度最短 在树中还可以为树的节点添加权形成带权二叉树 在一些应用中 这些权值可以是一 个具有某种意义的实数 对于带权二叉树 定义节点的带权路径长度节点的带权路径长度为节点到树根之间的 路径长度与该节点权值的乘积 树的带权路径长度树的带权路径长度 weighted path length of tree 为树中所有 叶子节点的带权路径长度之和 记为 n i iil wWPL 1 其中 n 表示叶子节点的数目 wi和 li分别表示叶子节点 ki的权值和根到节点岛之间 的路径长度 树的带权路径长度也称为树的代价 所谓最优二叉树最优二叉树是指带权路径长度最小的二叉树 下图给出了 3 种不同路径长度的带 权二叉树 具有不同带权路径长度的二叉树具有不同带权路径长度的二叉树 由此可知 图 c 所示的树的 WPL 最小 它就是一棵最优二叉树 即哈夫曼树 可以 看出 对于最优二叉树 权值越大的节点越接近树的根节点 权值越小的节点越远离树的 根节点 根据这一特点 可以得到最优二叉树的构造算法的步骤如下 根据给定的 n 个权值 w1 w2 wn 构成 n 棵二叉树的集合 即森林 F T1 T2 Tn 其中每棵二叉树 Ti中只有一个带权为 wi的根节点 其 左 右子树均为空 在 F 中选取两棵根节点的权值最小的树作为左右子树构成一棵新的二叉树 且 置新的二叉树的根节点的权值为其左 右子树上根节点的权值之和 在 F 中删除这两棵树 同时将得到的二叉树加入 F 中 重复第一步和第二步 直到 F 只有一棵树为止 这棵树则为哈夫曼树 上面给出的最优二叉树的构造算法 是由哈夫曼在 20 世纪 50 年代提出来的 为了纪 念哈夫曼 因此又将最优二叉树称为哈夫曼树 在构造哈夫曼树的过程中常会遇到这样的情况 根节点权值最小的树不止两棵 对于 这种情况 只要任选两棵即可 选出的两棵树谁做新节点的左孩子或右孩子均可 从上例所示的构造过程可以看出 经过一次合并 森林中就少一棵树 具有经过一次合并 森林中就少一棵树 具有 n 棵树的棵树的 森林 经过森林 经过 n 1 次合并才能得到一棵哈夫曼树 并且每次合并时都会产生一个新节点 一次合并才能得到一棵哈夫曼树 并且每次合并时都会产生一个新节点 一 共会产生共会产生 n 1 个新节点 因此 得到的哈夫曼树具有个新节点 因此 得到的哈夫曼树具有 2n 1 个节点 并且 所得到的哈夫曼个节点 并且 所得到的哈夫曼 树中没有度为树中没有度为 1 的节点 的节点 根据这一特点 可以采用一个大小为 2n 1 的一维数组来存储哈夫 曼树 并且为了便于查找节点的左孩子 右孩子和双亲节点 值得一提的是 parent 域有助于找到某节点的双亲节点 在构造哈大曼树时 需要选 取的是权值最小的根节点 一个节点为根节点 则 parent 的值为 1 在后面将讲到的哈夫 曼编码中也起到了很大的作用 哈夫曼编码哈夫曼编码是采用哈夫曼树实现的一种编码方式 编码是数据压缩的过程 即将文件 中的每个字符均转换为一个唯一的二进制位串 与编码相对应的就是解码 解码是数据解 压的过程 即将二进制位串转换为其对应的字符 在信息社会中 有效的编码技术可以节 省数据文件在计算机内的存储空间和提高信息的传输速度 如何采用有效的编码方法是现 在信息学研究的一个重点 编码主要有两种方式 等长编码和变长编码 等长编码等长编码是最简单的编码方式 例如 要对 A B C D E F G 这 7 个字符进行 编码 可以将这 7 个字符作为树的节点 生成一棵完全二叉树 规定在完全二叉树中 每 个分支的左节点 右节点分别用 0 1 编码 这样 这 7 个字符就需要 3 位二进制进行编码 例如 A 对应的编码为 000 D 对应的编码为 011 那么 对于一个由这 7 个字符组成的共 有 100000 个字符组成的数据文件 采用等长的方式进行编码 得到的整个文件的长度为 300000 然而 在实际通信中 这 7 个字符出现的频率不一样 据统计 在英文中 据统计 在英文中 E 的出现的出现 概率很高 概率很高 Z 出现的概率最低 出现的概率最低 根据这一特点 人们提出了变长编码 变长编码方法完全 依据字符出现的概率来构造平均长度最短的编码 这种编码方法让出现频率较高的字符具 有较短的编码 让出现频率较低的字符具有较长的编码 这样就可以有效地缩短电文的长 度 但是这种编码方式会出现译码的二义性 又称为多义性 例如 E 的使用频率较高 对应的译码为 1 D 使用的频率次之 对应的译码为 10 A 使用的频率又次之 对应的译码为 110 假设接到的编码串为 110 是翻译成 ED 还是 A 呢 这样就产生了译码的二义性 为了避免译码的二义性 人们规定 对某一字符集进行不等长编码时 任一个字符的编码都不能是其他字符编码的前缀 在上 例中 E 就是 D 和 A 的前缀 哈夫曼编码就是一种不等长编码 其定义如下 对于给定的字符集 D d1 d2 dn 及其频率分布 F wl w2 wn 用 d1 d2 dn作为叶节点 wl w2 wn作为节点的权 利用哈夫曼算法构造一棵最 优二叉树 将树中每个分支节点的左分支标上 0 右分支标上 1 把从根到每个叶子 的路径符号 0 或 1 连接起来 作为该叶子的编码 由于哈夫曼树是带权路径长度 最小的树 因此采用这种方法得到的编码长度最小 哈夫曼编码是在哈夫曼树的基础上求出来的 其基本思想是 从叶子节点 di 0 i n 出 发 向上回溯至根节点 依次求出每个字符的编码 哈夫曼编码的回溯步骤如下 1 选出哈夫曼树的某一叶子节点 2 利用其双亲指针 parent 找到其双亲节点 3 利用找到的双亲节点的指针域中的 lchild 和 rchild 判断该节点是双亲的左孩子还 是右孩子 若该节点是其双亲节点的左孩子 则生成代码 0 若该节点是其双亲节 点的右孩子 则生成代码 1 4 由于生成的编码与要求的编码反序 将所生成的编码反序 5 重复步骤 1 4 直到所有的节点都回溯完 在第 4 步中需要将所生成的编码反序 反序的方法是 首先将生成的编码从后向前依 次存放在一个临时的一维数组中 并设一个指针 start 指示编码在该一维数组中的起始位置 当某个叶子节点的编码完成时 从临时的一维数组的 start 处将编码复制到该字符对应的 bits 中即可 哈夫曼树不但可以用来编码 而且还可以用来解码 解码过程正好与编码过程相反 其解码过程为 从哈夫曼树的根节点出发 依次识别电文中的二进制编码 如果为 0 则 走向左孩子 否则走向其右孩子 走到叶节点时 就可以得到相应的解码字符 利用哈夫曼编码进行信息通信可以大大提高信道利用率 缩短信息传输时间 降低传 输成本 但是 这要求在发送端通过一个编码系统对待传数据预先编码 在接收端将传来 的数据进行译码 复原 对于双工信道 即可以双向传输信息的信道 每端都需要一个完整 的编僻码系统 试为这样的信息收发站写一个哈夫曼码的编译码系统 二 基本要求二 基本要求 一个完整的系统应具有以下功能 1 I 初始化 初始化 Initialization 从终端读入字符集大小 n 及 n 个字符和 m 个权值 建立 哈夫曼树 并将它存于文件 hfmtree 中 2 C 编码 编码 Coding 利用已建好的哈夫曼树 如不在内存 则从文件 hfmtree 中读入 对文件 tobetrans 中的正文进行编码 然后将结果存入文件 codefile 中 3 D 解码 解码 Decoding 利用已建好的哈夫曼树将文件 codefile 中的代码进行译码 结 果存入文件 textfile 中 4 P 打印代码文件 打印代码文件 Print 将文件 codefile 以紧凑格式显示在终端上 每行 50 个代 码 同时 将此字符形式的编码文件写入文件 codeprint 中 5 T 打印哈夫曼树 打印哈夫曼树 Treeprinting 将已在内存中的哈夫曼树以直观的方式 树或凹 人表形式 显示在终端上 同时将此字符形式的哈夫曼树写入文件 treeprint 中 三 实现提示三 实现提示 可以根据题目要求把程序划成 5 个模块 设计成菜单方式 每次执行一个模块后返回 菜单 除了初始化 I 过程外 在每次执行时都经过一次读取磁盘文件数据 这是因为如果在 程序执行后一直没有进行初始化 I 过程 为了能使后面的操作顺利进行 可以通过读取旧 的数据来进行工作 比如 如果程序的工作需要的字符集和权值数据是固定的 只要在安 装程序时进行一次初始化 I 操作就可以了 再次运行程序时 不管进行哪项操作都可以把 需要的数据读入到内存 四 算法分析四 算法分析 本程序主要用到了 3 个算法 1 哈夫曼编码 哈夫曼编码 在初始化 I 的过程中间 要用输入的字符和权值建立哈夫曼树并 求得哈夫曼编码 先将输入的字符和权值存放到一个结构体数组中 建立哈夫曼 树 将计算所得的哈夫曼编码存储到另一个结构体数组中 2 串的匹配 串的匹配 在解码 D 的过程中间 要对已经编码过的代码译码 可利用循环 将 代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较 如果相等就回显 并存人文件 3 二叉树的遍历 二叉树的遍历 在打印哈夫曼树 T 的过程中 因为哈夫曼树也是二叉树 所以就 要利用二叉树的先序遍历将哈夫曼树输出 五 测试数据五 测试数据 根据实验要求 在 tobetrans dat 中输入 THIS PROGRAM IS MY FAVORITE 字符 集和其频度如表 10 1 所示 字字 符符 空空 格格 ABCDEFGHIJKLM 频频 度度 1866423223210321154757153220 字字 符符 NOPQRSTUVWXYZ 频频 度度 20561925051553010112212 在以上数据验证准确的情况下 根据指定的文本文件 test txt 统计其中各种字符出 现的频度 进一步测试程序的运行结果 六 程序运行结果大致如下 六 程序运行结果大致如下 程序运行结果 程序运行结果 The huffman code is 2284 2284 110110 A 45 A 45 0010001000100010 B 3 B 3 001000011111001000011111C 52 C 52 0010010100100101 D 3 D 3 001000111010001000111010E 5 E 5 0010000110000100001100 F 2 F 2 11100011101001110001110100G 6 G 6 0010001110000100011100 H 14 H 14 11100011001110001100I 63 I 63 1110001011100010 J 4 J 4 111000110110111000110110K 1 K 1 0010000111101100100001111011 L 4 L 4 111000110111111000110111M 9 M 9 00100001000010000100 N 2 N 2 11100011101011110001110101O 5 O 5 0010000110100100001101 P 5 P 5 0010000111000100001110Q 1 Q 1 00100001111000010000111100 R 3 R 3 001000111011001000111011S 10 S 10 00100001010010000101 T 37 T 37 0010000000100000 U 4 U 4 111000111000111000111000 V 2 V 2 11100011101101110001110110W 8 W 8 1110001101011100011010 X 0 X 0 0010000111101000100001111010Y 4 Y 4 111000111001111000111001 Z 2 Z 2 11100011101111110001110111a 938 a 938 10001000 b 124 b 124 11100001110000 c 592 c 592 1110111101 d 501 d 501 1010010100 e 1609 e 1609 010010 f 215 f 215 011110011110 g 286 g 286 111001111001 h 538 h 538 1010110101 i 1025 i 1025 10011001 j 13 j 13 00100011110010001111k 51 k 51 0010010000100100 l 430 l 430 0111001110 m 362 m 362 0000100001 n 1073 n 1073 10111011 o 860 o 860 01100110 p 240 p 240 011111011111 q 12 q 12 00100011010010001101 r 691 r 691 00010001 s 812 s 812 00110011 t 1223 t 1223 11111111 u 404 u 404 0010100101 v 110 v 110 00100110010011 w 167 w 167 000001000001 x 19 x 19 11100011111110001111y 144 y 144 000000000000 z 11 z 11 00100011000010001100 MainMain menumenu 1 1 CodingCoding 2 2 DeCodingDeCoding 3 3 PreOrderTreePreOrderTree 4 4 exitexit PleasePlease enterenter youryour option 1option 1 4 14 1 PleasePlease enterenter a a string Welcomestring Welcome toto chinachina TheThe CodingCoding resultresult is 11100011010is 11100011010 010010 0111001110 1110111101 01100110 0000100001 010010 110110 11111111 01100110 110110 1110111101 1010110101 10011001 10111011 10001000 MainMain menumenu 1 1 CodingCoding 2 2 DeCodingDeCoding 3 3 PreOrderTreePreOrderTree 4 4 exitexit PleasePlease enterenter youryour option 1option 1 4 24 2 PleasePlease enterenter codecode stream stream 111000110111100100101001000110010101011000101111000110111100100101001000110010101011000101 TheThe DeCodingDeCoding resultresult is Liuzhouis Liuzhou MainMain menumenu 1 1 CodingCoding 2 2 DeCodingDeCoding 3 3 PreOrderTreePreOrderTree 4 4 exitexit PleasePlease enterenter youryour option 1option 1 4 34 3 TheThe treetree is 15028 is 15028 6316 6316 2962 2962 1364 1364 673 673