数据结构与算法-赫夫曼树(最优二叉树)、赫夫曼编码

以你之姓@ 2022-03-21 08:23 314阅读 0赞

### 概要 ###

*   *   *  赫夫曼树定义
         *  如何构造赫夫曼树
         *  赫夫曼编码

### 赫夫曼树定义 ###

>   以两棵带权的二叉树为例：  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70][]  
>   从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度。二叉树a中，根结点到结点D的路径长度就为4，二叉树b中根结点到结点D的路径长度为2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。  
>   如果考虑带权的结点，结点的带权的路径长度为该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。  
>   我们将带权路径长度WPL最小的二叉树称做赫夫曼树。也称最优二叉树。

### 如何构造赫夫曼树 ###

>   目前二叉树a的WPL=5x1+15x2+40x3+30x4+10x4=315。（这里5是A结点的权，1是A结点的路径长度，其他同理。）  
>   尝试将二叉树a构造成最优二叉树：
> 
> > 1.  先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5, E10, B15, D30, C40;
> 
> > 1.  取头两个最小权值的结点作为一个新结点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子。新结点的权值为两个叶子权值的和：5+10=15；  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1][]
> 
> > 1.  将N1替换A与E，插入有序序列中，保持从小到大排列。即：N115, B15, D30, C40;
> 
> > 1.  重复步骤2。将N1与B作为一个新结点N2的两个子结点。N2的权值：15+15=30；  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 2][]
> 
> > 1.  将N2替换N1与B，插入有序序列中，保持从小到大排列。即：N230, D30, C40;
> 
> > 1.  重复步骤2。将N2与D作为一个新结点N3的两个子结点。N3的权值：30+30=60；  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 3][]
> 
> > 1.  将N3替换N2与D，插入有序序列中，保持从小到大排列。即：C40, N360;
> 
> > 1.  重复步骤2。将C于N3作为一个新结点T的两个子结点，由于T即是根结点，完成赫夫曼树的构造。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 4][]  
> >       此时原二叉树a的WPL=40x1+30x2+15x3+10x4+5x4=205。

### 赫夫曼编码 ###

>   赫夫曼树的研究目的是为了解决远距离通信的数据传输最优化问题。  
>   比如需要传输一段文字内容为“BADCADFEED”给别人，通过相应的二进制数据传输，编码前为“001000011010000011101100100011”；  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 5][]  
>   对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制也将非常的可怕。而且事实上，不管英文、中文或是其他语言，字母或汉字的出现频率是不相同的，比如英语中的几个元音字母“a o e i u”，中文中的“的 了 有 在”等汉字都是高频词汇；  
>   现假设六个字母的频率为A27, B8, C15, D15, E30, F5, 合起来正好是100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。  
>   左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 6][]  
>   此时，我们对这六个字母用其从树根到叶子经过路径的0或1来编码，可以得到如图这样的定义。  
> ![20190201093937781.png][]  
>   我们将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了：
> 
> > 原编码二进制串：001000011010000011101100100011（共30个字符）  
> > 新编码二进制串：1001010010101001000111100 （共25个字符）
> 
>   也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。  
>   解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。比如当我们接收到“1001010010101001000111100”时，由约定好的赫夫曼树可知，1001得到一个字母是B，接下来01意味着第二个字母是A，如图所示，其余的也相应的可以得到，从而成功解码。  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 7][]  
>   总结：一般地，设需要编码的字符集为\{d1, d2, ···, dn\}，各个字符在电文中出现的次数或频率结合为\{w1, w2, ···, wn\}，以d1, d2, ···, dn作为叶子结点，以w1, w2, ···, wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70]: /images/20220321/b989510aad114b529d07c1330d946563.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1]: /images/20220321/a97d1c993a4046cda144625745c6d23b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 2]: /images/20220321/384dcdf3c36149dbbe8f277ec581a71f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 3]: /images/20220321/d618dbb7f5794027866534febbb3425d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 4]: /images/20220321/e50002eba7a742aa9dbbf43bd0b7c472.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 5]: /images/20220321/76b3ef5c5a604aaa9fed3da7dda73c73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 6]: /images/20220321/ea9cbdcbfae340feabacb925c0987d21.png
[20190201093937781.png]: /images/20220321/01a3023e4e294c2eb280c342a9cafb3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 7]: /images/20220321/d41a4bdc65794d89b65bf66e8f02f484.png