Huffman编解码问题——讲解

1、2.5 huffman 编码问题实验四题目 2:利用二叉树结构实现哈夫曼编 / 解码器。基本要求：1、初始化(init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2 、 建立编码表(createtable) ：利用己经建好的哈夫曼树进行编码，并将每个字符的 编码输出。3 、编码(encoding) : 根据编码表对输能的字符串进行编码，并将编码后的字符串输出。4 、译码(decoding) : 利用己经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5 、 打印 (print) : 以直观的方式打印哈夫曼树(选作)6 、 计算输能的字符串编码前和编码后

2、的长度，并进行分析，讨论赫夫曼编码的压缩效果。7 、 可采用二进制编码方式(选作)实验讲解：huffman编解码的实验按照模块化分，可以划分成如下部分:a) 统计输能的字符串中字符频率b) 创建huffman 树c) 打印huffman 树d) 创建huffman 编码表e) 对输能的字符串进行编码并输出编码结果f) 对编码结果进行解码，并输出解码后的字符串g) 最后编写测试函数，测试上述步骤的正确性。根据模块化分，设计huffman 的存储结构如下：1) huffman 树的结点结构struct hnode intweight;/结点权值intparent;/双亲指针intlchild;/左

3、孩子指针int rchild ; /右孩子指针;2）编码表结 点结构（如 右图2-6所 示）struct hcode char data; char codel00;；200datacodez1001c1012b113a0图2-6 huffman树编码结构3) huffman类结构class huffmanprivate :hnodc* htree; hcod e* hcodetable; char st r1024; char leaf 256; i nt a256; public : int n;void init ();void createhtree ();voidselectmin(

4、int&x,/huffman 树huffman编码表/输入的原始字符串/叶子 节点对应的字符/记录每个 出现字符的个数/叶子节点数/初始化/创建huffman树int &y, int s, int e ）;void createcodetable ();void encode(char * d);void decode(char *s, char *d);void print(int i , intn);/创建编码表/编码/解码/打印huffman树huffman ();根据实验要求，分步骤实现如下：步骤1：统计输入的字符串中字符频率huffman编码的第一步需要使用字符出现的频率作为输入，本

5、实验使用从键盘输入的方式进行，需要的解决得问题有 2个：一是输入的字符串中间有空格如何处理？二是如何使统 计效率更 高？例如：char str1024;cinstr;上述代码运行后输入字符串，但cmstr 遇到空格就停止本次读取，所以我们需要使用其它的方法来进行输入，即需要使用cm. get () 函数进行字符串读取。 get () 方法每调用一次， 读取一个字符，该字符的 ascii 码作为返回值返回，换行回车等控制字符也当作普通字符进行读取，因此需要指定结束读取的标志字符，才能停止get () 函数的循环调用。 本实验中可以/ 记录每一个字符出现的次数将字符读取和统计结合在一起进行。示例代

6、码如下：intnnum256= 0; intch = cin .get (); inti =0;/ 统计字符出现的次数/ 记录原始字符串 / 读取下一个字符 while ( ch!=v) &(c h!= n ) nnumch+; str i + = ch; ch =(); str i = ，其中，整型数组变量cin . get0nnurffl来记录每一个字符出现的次数(若该字符未出现，则对应 的nnumch的值为0),可以把读取的字符 ch的ascii码当成，当ch出现时，nnumch自 动加一。当然，数组nnu时的等于零的字符会有很多，不方便后续 hufman树的创建，因此可以进行过滤，仅留

7、下出现次数大于零的字符。因此，完整的初始化代码如下： voidhuffman : init ()?n = 0;for ( i =0; i 0)/若nnumi =0说明该字符未出现leaf n = ( char)i ; a n = nnum i ;n+;其中，数组leaf存储出现次数大于零的字符，相应的数组a存储该字符出现的次数，n为字符数，作为步骤2创建huffman树的输入。字符数组 str存储用户输入的字符串，作为步骤5编码的输入。当然，也可以使用其它方法进行字符的统计，请读者自行思考。步骤2:创建huffman树权值该步骤在教材5.4.2 小节中进行了详细的讲解和实现，其中有一个选择权值

8、之中最小的两个 的函数，即函数 selectmin(int &x, int &y, int s, int e );其中x为最小权值，y为次小权值，s为权值范围的起始下标，e为结束下标。该函数如何实现呢？分析：从所有未使用过的权值表中选择两个最小的权值，可以有多种方法，比如一次选择一个最小的，选择2遍；或者进行迭代，一次选择出两个。显然，后者的时间效率较高，因此 我们采用后者进行实现。迭代选择两个最小值得基本思想是：1、 从权值表 htree s. e 中选取第一个未使用结点下标为 x, 并设 y=x ；2、 从剩下的未使用的权值中依次遍历若当前结点 i 的权值 结点 x 的权值，则迭代，即y=

9、x; x = i ;否则：若此时y=x ( 即 y 还未赋值) ，则y=i ;若此时当前结点i的权值y结点的权值，则具体实现如下：void huffman : selectmin(int &x, int int i ;for ( i =s; i =e; i +)if ( htree i.parent = -1)x = y= i ; break ;for ( ; i e; i +)if ( htree i.parent = -1)if ( htree i . weight y = x; x = i ;else if ( x=y) | ( y = i;& y,y=i ;int s, int e )

10、/ 找出第一个有效权值x ，并令y=x/ 该权值未使用过 htree x. weight )/ 迭代，依次找出前两个最小值htree i . weight htree y. weight )/ 找出第 2个有效权值y特别说明，本例中叶子节点数n作为成员变量，因此，huffman类的成员函数的参数中不必在添加int n这个参数，直接使用 n即可。步骤 3 ：打印 huffman 树huffman 树的直观表示方式由多种，我们常见的树状结构如图所示是其中的一种，此外还有如图a所示的嵌套集合表示法，如图b所示的广义表表示法和图c所示的凹入表示法。口e图-8其他表示法树型表示法当结点很多的时候，不容易

11、打印的非常合适，所以我们可以选择使用凹入表的方式打印任意形状的 hufman树。根结点空一格直接打印，第2层结点空2格打印，第3层结点空3格的打印，以此类推，每个节点占用独立的一行。由于只有叶子结点是有对应字符的，所以其他结点可以打印该结点的权值。因此，我们可以尝试使用二叉树前序遍历的方式来进行直观的 打印。示例代码如下：#define n 10/定义树的最大深度void huffman 二 print(int i , int n) if ( htree i.lchild = -1)cout setfill ( )setw(m+1)eaf i sefill( - ):setw(n-n) n；e

12、lse cout setfill( )setw( n+1)htree i . weight setfill( - )setw(nkn)4n ； print (htreei . lchild , n+1); print (htreei . rchild , n+1);其中，参数i表示huffman树的下标为i的结点，n表示该结点的层次。该函数是递归 函数，所 以在main()函数中第一次调用该函数时，实参为 i =2*n-2, m=1;步骤4：创建编码表该步骤请参考教材5.4.2 小节中的讲解和实现即可。 步骤5: 编码编码表生成后， 进行编码相对容易， 实验要求只要能够显示出来编码后的字符串即

13、可， 也就 是说，若a的编码为0, b的编码为10,则 字符串aab勺编码显示为0010即可。由于初始化函数中己经记录了输入的字符串 str ，因此直接使用该变量作为输入即可。 void huffman: en code(char * d)char *s = str ;while (* s! =0 )for (int i =0; i n; i +)if (*s = hcodetablei.data ) strcat ( d, hcodetable i .code);/d 为编码后的字符串break ; s+; 上述代码用于本实验的编码显示和验证是没问题的，但并没有实现真正的压缩效果，这时因 为

14、代码的实现。比如若 a的编码为100,实际压缩中使用3个bit代替字符a,本例中使 用了 3个字符“ 100”来编码，因此没有真正的压缩效果。如果希望能够按照 bit 的方式进 行编码，需要使用位运算符进行bit 的操作，将编码按照 bit 的方式写入文件。请同学们自行思考，如何采用 bit 的方式使用 huffman 编码压缩文件。步骤 6: 解码该步骤请参考教材5.4.2 小节中的讲解和实现即可。步骤 7: 测试根据测试数据，编写如下的测试man() 函数进行测试： void main()huffman hfcode;cout 请输入要编码的字符串： ；hfcode. init ();co

15、ut 创建 huffman 枳:endl ;hfcode. createhtree ();hfcode. print (2*hfcode. n-2,1);cout ”创建huffman 编码表: endl ;hfcode. createcodetable ();char d1024=0;hfcode. encode( d);cout 编码结果： dendl ;char s1024=0;hfcodedecode(d, s); cout 解码结果: sendl ;最后，也是特别要注意的地方内存泄露。本实验中的主要数据结构htree和hcodetable都是动态内存，因此必须要在huffman树的析构函数中进行内存清理，示例代 码如下：huffman : huffman。delete htree; delete 口hcodetable;）图2-9运行测试结果根据要求，我们下面讨论一下huffman编码的压缩效果。数据压缩比（英文名称：data compression ratio ）为衡量数据压缩器压缩效率的质量指标。是指数据被压缩的比例。其计算公式如下：压缩比=压缩前字节数/压缩后字节数本实验为了方便显示和验证算法，采用的是