最后更新: 2026-05-26 17:34 查看: 80 次纠错评论(0) 课件开VIP

Huffman编码（算法）

－输入：正实数序列 $w_1, w_2, \ldots, w_{ t }$ 。
－输出：具有 t 个树叶，其权序列为 $w_1, w_2, \ldots, w_{ t }$ 的最优二叉树。
－过程：
－ T 棵根树（森林），其根的权分别是 $w_1, w_2, \ldots, w_{ t }$ 。
－选择根权最小的两棵树，以它们为左，右子树（合并）生成新的二叉树，其根权等于 2 棵子树的根权之和。
重复第2步，直至形成一棵树。
注意：结果可能不唯一（如果＂当前＂权最小顶点对不唯一）。

## Huffman编码（算法）：举例
－例子：开始序列：2，2，3，3，5
－1步后：4，3，3，5
－ 2 步后：4，6，5
－3步后：9，6
 ![图片](/uploads/2025-01/69474a.jpg)
 
 ## 一个应用示例
－八个字符的传输问题
－假设八个字符的频率如下：

$$
\begin{array}{ll}
\text { 0: } 25 \% & 1: 20 \% \\
2: 15 \% & 3: 10 \% \\
4: 10 \% & 5: 10 \% \\
6: 5 \% & 7: 5 \%
\end{array}
$$

－则对应的权为：
- 5,5,10,10,10,15,20,25

![图片](/uploads/2025-01/e191f0.jpg)
 
 
 
 例7-8.5 在通信中八进制数字出现的频率如下：
     0：25%          1：20%
     2：15%          3：10%
     4：10%          5：10%
     6：  5%          7：  5%
求传输它们的最佳前缀码
求传输10n(n≥2)个按上述比例出现的八进制数字需要多少个二进制数字；若用等长的(长为3)的码字传输需要多少个二进制数字

解答
以 100 乘各频率为权，并按小到大排列，得 $w_1=5$ ， $w_2=5, w_3=10, w_4=10, w_5=10, w_6=15, w_7=20, w_8=25$ 。
产生的最优树如下。
  ![图片](/uploads/2025-01/a54464.jpg)
  
  （2）传 100 个按比例出现的八进制数字所需二进制数字个数 $W(T)=285$ ，故传 $10^n(n \geq 2)$ 个数字需用的二进制数字为 $2.85 \times 10^n$ 。用等长码（长为 3 ）应该用 $3 \times 10^n$ 个数字
   ![图片](/uploads/2025-01/727d06.jpg)
   
   由于在每一步选择两个最小的权的选法不唯一。
因为两个权对应的顶点所放左右位置不同。
画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权应该相等，即它们都应该是最优树。
Huffman算法的正确性
设 $C$ 是字母表，其中每个字符 $c$ 的频率为 $f[c]$ 。若 $x, y$ 是两个频率最小的字符，则必存在 $C$ 的一种最优前缀码，使得 $x, y$的编码仅有最后一位不同。
 ![图片](/uploads/2025-01/6278c6.jpg)
 
 
 ## 保持权不变的变换
  ![图片](/uploads/2025-01/fc91cc.jpg)
   ![图片](/uploads/2025-01/0dd698.jpg)

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：编码

下一篇：生成树

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