最后更新: 2025-01-22 09:57 查看: 85 次纠错评论(0) 课件开VIP

最优树

这一节主要介绍最优树的霍夫曼（Huffman）算法，并通过前缀码的设计说明最优树的用处。下面首先用例子引进前缀码的概念。
我们来考虑远距离通信中的一个问题，一篇英文字母组成的短文从发送端发出信息，通过远距离传输送到接收端。通常的电报是用长度为 5 的 0 和 1 序列来表示英文字母和标点符号的，这种长度为 5 的 0 和 1 序列组成的集合称为 5 单位编码。为了传输一篇短文，将对应的 0 和 1 序列组成的信息串发送出去以后，在接收端就将此信息串划分成长度为 5 的序列，这样就得到对应的短文。

但在一篇短文中每个字母出现的频率是不同的。例如 $e, t$ 出现的频率要比 $j, z$ 出现的频率大很多。为了使短文对应的信息串的总长度缩短，首先要求出现次数多的字母用较短的 0 和 1 序列表示，出现次数少的字母用较长的 0 和 1 序列表示；其次要求在接收端能从一个信息串中明确地分辨出字母所对应的序列。例如字母 $a, b, c, d, e$ 分别用下列 0 和 1 序列表示，对应关系如下：

$$
\begin{array}{ccccc}
a & b & c & d & e \\
00 & 110 & 010 & 10 & 01
\end{array}
$$

我们把集合 $\{00,110,010,10,01\}$ 叫做码。如果接收端收到信息串是 010010 ，这时分辨不清发送来的是 $e a d$ 还是 $c c$ ，这是因为 $e$ 对应的序列 01 是 $c$ 对应的序列 010 的前缀。为了避免这样的情况发生，就要将 $c$ 对应的序列改为 111 ，才能确定送来的是 $e a d$ 。集合 $\{00$ ， $110,111,10,01\}$ 就叫前缀码。前缀码定义如下。

定义 10.17 二进制有限序列组成的集合称为码。其中每个元素称为一个码字。在一个码中，任一码字都不是其他码字的前缀，则称该码为二元前缀码，简称前缀码。

为了设计 26 个英文字母所对应的前缀码，我们先来看前缀码与二分树的关系。
定理 10.12 给定一棵二分树，则可确定一个前缀码。反之，对应于一个前缀码，存在一棵二分树。

证明：从给定二分树的每个分枝点向它儿子连出两条边，自左到右，分别标记 0 和 1 ，从树根到树叶的路上边的标号组成的序列标记在该片树叶上，用方框标出，如图 10.6 所示。树叶上序列组成的集合就是前缀码。如果不是前缀码，则存在一个序列是另一个序列的前缀，那么该序列必位于根到另一序列对应树叶的这条路的分枝点上，导致矛盾。

反之，设前缀码中最长序列的长度为 $h$ ，画一棵高度为 $h$ 的正则二分树，并使树叶在同一层上。从每个分枝点向它的儿子连出两条边分别标记 0 和 1 。从根到每个顶点的路上边的标号组成的序列标在每个顶点上。然后将不属于前缀码中序列所对应的顶点及其关联的边删去，便得到一棵二分树。它的树叶对应的序列全体就是前缀码。

例如，图 10.6 给出由前缀码 $\{00,0100,011,11\}$ 对应的一棵二分树。
如何设计 26 个英文字母对应的前缀码，使得同一短文字母串所对应的信息串序列尽可能地短，也就是说，使 1000 个字母的短文中其信息串长度 $\sum_{i=1}^{26} w_i l_i$ 最小，其中 $w_i$ 表示第 $i$ 个字母出现的频率，$l_i$ 表示第 $i$ 个字母对应的序列长度。这一问题归结为如何构造一棵最优二分树的问题，下面介绍求最优二分树的霍夫曼算法，为此首先给出最优二分树的定义。

定义 10.18 （最优树）给定一组权 $w_1, w_2, \cdots, w_n$ 且 $w_1 \leqslant w_2 \leqslant \cdots \leqslant$

![图片](/uploads/2025-01/fafb7c.jpg)
 
0100 $w_n$ ，如果一棵二分树的 $n$ 片树叶带权 $w_1, w_2, \cdots, w_n$ ，称这棵二分树为带权 $w_1, w_2, \cdots, w_n$ 的二分树，记为 $T_{\circ} T$ 的权记为 $W(T), W(T)=\sum_{i=1}^n w_i l_i$ ，其中 $l_i$ 是从根到带权 $w_i$ 的树叶的路的长度。在所有带权 $w_1, w_2, \cdots, w_n$ 的二分树 $T$ 中，使 $W(T)$ 最小的二分树称为最优二分树，简称最优树。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：子树与有序树

下一篇：霍夫曼算法

本文对您是否有用？有用 (0) 无用 (0)