数据结构课件：Huffman树与Huffman编码.pptx

Huffman树与Huffman编码

本讲要点信息编码问题Huffman树（贪心算法思想）Huffman编码和译码

1.信息编码问题假设给定一个字符串“ADCBDABDCBDBCDCDCD“请对其中字符进行编码，使得该字符串的编码存储空间最少，且从存储空间取出编码也能还原成唯一的原字符串。问题分析用ASCII码，这是一种定长编码每个字符占7bit，如果这个字符串很长，各个字符出现的概率又有较大的差别，采用ASCII编码不经济。

1.信息编码问题问题分析信息编码是指将信息符号串转换为编码文件，其主要目标之一是提高信息的存储效率。存储效率可以用编码系统的平均码长来衡量。设编码系统中有n个符号，每个符号的编码长度为L1,L2,…,Ln，各符号出现的频率分别是F1,F2,…,Fn，则用不定长编码？

1.信息编码问题用不定长编码？不定长编码的优点：存储效率优于定长编码的效率。缺点：不定长编码由于码长不固定，在还原字符时，存在各符号的码串相互混淆的可能。如问题中原字符串前两个字符为“AD”，用上述不定长编码，编码串为“101”，进行还原时，可以解释为“AD”也可以解释为“DB”，因此这样的编码方式不能还原成唯一的原字符串。不定长编码必须增加约束条件：在同一编码系统中，任何符号的编码不能是另一符号编码的前缀。满足此条件的编码也被称为前缀编码，有效的统计编码一定是前缀编码。

1.信息编码问题如何设计高效率的前缀编码？1952年正在麻省理工攻读博士学位的DavidA.Huffman给出了最优解决方案，即Huffman编码，中文通常写作哈夫曼编码。

2.Huffman树叶子结点的权值：对叶子结点赋予的一个有意义的数值量。二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。

记为：Huffman树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。WPL=?=niiilw1第i个叶子的权值；从根结点到第i个叶子的路径长度

2.Huffman树例：对于“ADCBDABDCBDBCDCDCD”，4个叶子结点ABCD，其权值分别为{2，4，5，7}，可以构造出形状不同的多个二叉树。WPL=36WPL=46WPL=41245724574527图中有Huffman树吗？如何快速地构造一棵Huffman？

2.Huffman树第1步：初始化W＝{2，4，5，7}Huffman树的构造过程7524第2步：选取与合并426第3步：删除与加入75426

2.Huffman树W＝{2，4，5，7}Huffman树的构造过程重复第2步75426511426

2.Huffman树W＝{2，4，5，7}Huffman树的构造过程重复第3步7511426511426718重复第2步

2.Huffman树Huffman树的特点：权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。7524贪心算法思想：一步一步地进行，常以当前情况为基础根据某个优化测度做最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。

3.Huffman编码和译码Huffman编码算法以需要编码的字符作为叶子结点，根据各字符在字符串中出现的频率构建相应的Huffman树。规定在Huffman树中左分支记作编码0，右分支记作编码1，则从根结点到每个叶子结点的路径所构成的0/1串就是该叶子结点对应字符的Huffman编码。Huffman编码是一种不定长编码。

3.Huffman编码和译码Huffman译码算法当已知编码要求还原字符时，需要依据编码时的原Huffman树进行译码。对每个字符的译码都是从Huffman树的根结点向叶子结点的下行过程。逢0沿左分支下行，逢1沿右分支下行。当下行遇到叶子结点时，该叶子结点中的data域的值就是译码字符。

练一练字符串“alibaba”的二进制Huffman编码有（）位。3211

本讲要点信息编码问题Huffman树（贪心算法思想）Huffman编码和译码