最后更新: 2025-01-21 18:45 查看: 27 次反馈刷题

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算法的正确性

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