二叉树学习(三)哈夫曼树

朱雀 2022-03-16 16:06 270阅读 0赞

先来看一个例子:  
如果需要传输 一串文本:  
**abcdaabbbc**(假设是ascii码)  
一个英文字符是 1个字节,那么这里需要10 \* 8=80bit(80位来表示)  
能否使用某种编码,来减少位的使用,节省空间呢?  
比如 **高频率出现的字符使用较少的位来表示**  
**低频率出现的字符可以使用相对较多**的字符来表示  
哈夫曼编码就是这个思想.

# 一 为什么哈夫曼算法能节省空间?? #

1.  统计其中字符出现的次数

1.  将字符按照频率由低到高排列

1.  自底向上构建出一棵树:哈夫曼树(所有字符都在叶子节点,频率越小,深度越大),如下

C
               /    \
              B      b
            /   \
           A      a
         /   \
         c    d

1.  编码表:如果将向左记为1,向右记为0,  
    那么从根节点到各自叶节点的路径顺序即为编码:

平均编码长度AL= ∑ i = 1 n ( P i ∗ L i ) \\sum\\limits\_\{i=1\}^\{n\}(Pi\*Li) i=1∑n(Pi∗Li)  
注: Pi 表示字符i的出现频率;Li 表示字符i的编码长度  
上述示例的AL=1 \* 0.4+ 3 \* 0.1+2\*0.3+3\*0.2=1.9 (bit)  
上述计算结果有时称为树的**带权路径长度**(Pi 看做权重,路径长度是Li)  
**"最优树:"** 带权路径长度**最短**的一类树(哈夫曼树即是);  
相比原来的每个字符8 bit,这就节省了很多空间!!!

# 二 文字哈夫曼编码表示(明文转密文): #

**abcdaabbbc**  
10 0 111 110 10 10 0 0 0 111

# 三 哈夫曼编码转字符(密文转明文) #

很简单:直接将得到的编码序列从 哈夫曼树中**根节点**开始,如果为1,查找左孩子,0查找右孩子,如果查找到叶子节点,将叶子节点输出,从编码序列的下一个字符重复上述操作  
如果不能找到叶子节点,则无法解密

# 四 最优树的构建算法 #

给定权值序列:W=\{5,6,2,9,7\}

*  (1))先将权值升序排列:W 0 \_0 0=\{2,5,6,7,9\}
 *  (2)两两构成一棵子树:

7'                                                
       /   \                                       
       2  5      
     
         13'
        /   \
       6    7
       
         9

(3)新的权值升序列: W 1 \_1 1=\{7’,9,13’\}

16'
    /  \
    7'  9
    
    13'

(4) 重复(2) ,直到只剩一棵树时结束,完成最优树构建  
这里的结果是:

39'
                     /      \
                  16'        13'
                /      \     /   \
              7'       9    6     7
              /  \    
           2     5    
           如果假设:往左为1,右为0
           那么:   2        111
                   5          110
                   9           10
                   6           01
                   7           00

# 五 哈夫曼树的应用场景: #

1.  加密与解密
2.  压缩与解压缩
3.  优化条件判断分支效率(以成绩分数划分等级判断为例)

# 六 总结: #

1.  编码不唯一,同概率节点可以位于左子树也可以位于右子树
2.  如果哈夫曼树已经构建好,那么对应的的哈夫曼编码唯一
3.  如果**权值序列确定**,那么哈夫曼**平均码长**唯一(WPL 最短带权路径长度唯一,即使哈夫曼的具体形态可能不一样)