哈夫曼编码.

Presentation on theme: "哈夫曼编码."— Presentation transcript:

1 哈夫曼编码

2 霍夫曼树 (Huffman Tree) 路径长度 (Path Length) 两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各叶结点到根结点的路径长度之和。 具有不 同路径长度的 二叉树

3 n 个结点的二叉树的路径长度不小于下述数列前 n 项的和，即
其路径长度最小者为 带权路径长度 ( Weighted Path Length, WPL ) 树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。

4 具有不同带权路径长度的扩充二叉树 霍夫曼树 带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。

5 霍夫曼算法 (1) 由给定的 n 个权值{w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 }，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。

6 霍夫曼树的构造过程

7 扩充二叉树的类定义 template <class Type> class ExtBinTree; template <class Type> class Element { friend class ExtBinTree; private: Type data; Element<Type> *leftChild, *rightChild; }; template <class Type> class ExtBinTree { public: ExtBinTree ( ExtBinTree<Type> &bt1, ExtBinTree<Type> &bt2 ) {

8 root→leftChild = bt1.root;
root→rightChild = bt2.root; root→data.key = bt1.root→data.key + bt2.root→data.key; } protected: const int DefaultSize = 20; Element <Type> *root; //扩充二叉树的根

9 建立霍夫曼树的算法 template <class Type>
void HuffmanTree (Type *fr, int n, ExtBinTree <Type> & newtree ) { ExtBinTree <Type> & first, & second; ExtBinTree <Type> Node[DafualtSize]; MinHeap < ExtBinTree <Type> > hp; //最小堆 if ( n > DefaultSize ) { cout << “大小 n ” << n << “超出了数组边界 ” << endl; return; } for ( int i = 0; i < n; i++ ) { Node[i].root→data.key = fr[i];

10 Node[i].root→leftChild =
Node[i].root→rightChild = NULL; } //传送初始权值 hp.MinHeap ( Node, n ); for ( int i = 0; i < n-1; i++ ) { //建立霍夫曼树的过程，做n-1趟 hp.DeleteMin ( first ); //选根权值最小的树 hp.DeleteMin ( second ); //选根权值次小的树 newtree = new ExtBinTree <Type> ( first, second ); //建新的根结点 hp.Insert ( newtree ); //形成新树插入 }

11 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。
霍夫曼编码 主要用途是实现数据压缩。 设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : C : S : 11 则总编码长度为 ( ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }。

12 化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立霍夫曼树。左分支赋 0，右分支赋 1，得霍夫曼编码(变长编码)。
A : 0 T : C : S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于 霍夫曼树的带权路径长 度WPL。 霍夫曼编码是一种无 前缀编码。解码时不会 混淆。 霍夫曼编码树

13 树 树的定义、树的基本运算 二叉树 二叉树定义、基本运算 小结 需要复习的知识点 树的分层定义是递归的 树中结点个数与高度的关系 二叉树性质
小结 需要复习的知识点 树 树的定义、树的基本运算 树的分层定义是递归的 树中结点个数与高度的关系 二叉树 二叉树定义、基本运算 二叉树性质 二叉树结点个数与高度的关系 不同二叉树棵数 完全二叉树的顺序存储

14 完全二叉树的双亲、子女和兄弟的位置 二叉树的前序 · 中序 · 后序 · 层次遍历 前序 · 中序 · 后序的线索化二叉树中前驱与后继的查找方法 应用二叉树遍历的递归算法

15 霍夫曼树 树的存储 霍夫曼树的构造方法 霍夫曼编码 带权路径长度的计算 树的广义表表示与双亲表示 树与二叉树的对应关系
树的先根 · 后根 · 层次遍历

16 堆 堆的定义、堆的插入与删除 形成堆时用到的向下调整算法 形成堆时比较次数的上界估计 堆插入时用到的向上调整算法 堆的插入与删除算法

17 【例1】在结点个数为n (n > 1)的各棵树中，高度最小的树的高度是多少？它有多少叶结点？多少分支结点？高度最大的树的高度是多少？它有多少叶结点？多少分支结点？

18 【解答】结点个数为 n 时, 高度最小的树的高度为 1, 有 2层；有 n-1 个叶结点，1 个分支结点；

19 【例2】已知一棵二叉树的前序遍历的结果序列是
ABECDFGHIJ 中序遍历的结果序列是 EBCDAFHIGJ 试画出这棵二叉树。

20 【解答】前序序列 ABECDFGHIJ，中序序列 EBCDAFHIGJ 时：

21 前序序列 ABECDFGHIJ 中序序列 EBCDAFHIGJ A A B F B F E C G E C G D H J D HI J I

22 【例3】若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：
(1) 统计二叉树中叶结点个数。 (2) 以二叉树为参数, 交换每个结点的左子女和右子女。

23 【解答】 (1) 定义二叉树结构 template <class Type> class BinaryTree; //二叉树 class BinTreeNode //二叉树结点 leftChild data rightChild

24 (2) 统计二叉树中叶结点个数 3 2 1 1 1 1 1

25 template <class Type>
int leaf ( BinTreeNode<Type>* t ) { int leaves; if ( !t ) leaves = 0; else if ( !t→leftChild && !t→rightChild ) leaves = 1; else leaves = leaf ( t→leftChild ) + leaf ( t→rightChild ); return *leaves; }

26 (3) 交换每个结点的左子女和右子女

27 template <class Type>
void exchange ( BinTreeNode<Type>* t ) { BinTreeNode<Type>* p; if ( t→leftChild || t→rightChild ) { //非叶结点，交换左、右子女 p = t→leftChild; t→leftChild = t→rightChild ; t→rightChild = p; exchange ( t→leftChild ); exchange ( t→rightChild ); }

28 【例4】假定用于通信的电文仅由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。试为这 8 个字母设计不等长 Huffman 编码, 并给出该电文的总码数。

29 【解答】

30 则Huffman编码为 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 +
c1 c2 c c c5 c6 c7 c8 电文总码数为 4 * * * * 6 + 3 * * * * 4 = 257