Huffman树及其应用-白红宇

首先需要介绍一个概念：

等长编码

计算机二进制编码
- ASCII 码
- 中文编码

等长编码
- 假设所有编码都等长
- 表示 n 个不同的字符需要 log₂n位
- 字符的使用频率相等

空间效率
- 对于使用频率不同的字符，给频率低的字符等长编码，空间效率就不高

数据压缩和不等长编码

可以利用字符的出现频率来编码

经常出现的字符的编码较短，不常出现的字符编码较长

数据压缩既能节省磁盘空间，又能提高运算速度(外存时空权衡的规则)

对于编码实现，我们可以使用前缀编码

前缀编码

任何一个字符的编码都不是另外一个字符编码的前缀

这种前缀特性保证了代码串被反编码时，不会有多种可能

若编码为Z(00), K(01), F(11), C(0), U(1), D(10), L(110), E(010) 。则对应:”ZKD”,”CCCUUC”等多种可能，这就不是前缀编码

Huffman树与前缀编码

Huffman编码将代码与字符相联系

不等长编码

代码长度取决于对应字符的相对使用频率或“权”

逻辑结构上是扩充二叉树

建立Huffman编码树

定义

对于n个字符K0，K1，...，Kn-1，它们的使用频率分别为w0, w1，...，wn-1，给出它们的前缀编码，使得总编码效率最高。

给出一个具有n个外部结点的扩充二叉树
- 该二叉树每个外部结点 Ki 有一个权 wi外部路径长度为li
- 权越大的叶结点离根越近

可以看出：

只有在外部节点保存了实际信息

频率越大其编码越短

编码过程

首先，按照“权”(例如频率)将字符排为一列
- 接着，拿走前两个字符(“权”最小的两个字符)
- 再将它们标记为Huffman树的树叶，将这两个树叶标为一个分支结点的两个孩子，而该结点的权即为两树叶的权之和

将所得“权”放回序列，使“权”的顺序保持

重复上述步骤直至序列处理完毕

译码: 从左至右逐位判别代码串，直至确定一个字符

与编码过程相逆

从树的根结点开始
- “0”下降到左分支
- “1”下降到右分支
- 到达一个树叶结点，对应的字符就是文本信息的字符连续译码

译出了一个字符，再回到树根，从二进制位串中的下一位开始继续译码

Huffman树ADT

template 
    
      class HuffmanTree {private:    HuffmanTreeNode
     
      * root;//Huffman树的树根     void MergeTree(HuffmanTreeNode
      
        &ht1, HuffmanTreeNode
       
         &ht2, HuffmanTreeNode
        
         *parent);//把ht1和ht2为根的合并成一棵以parent为根的Huffman子树public:     HuffmanTree(T weight[],int n);//构造Huffman树，weight是存储权值的数组，n是数组长度     virtual ~HuffmanTree(){DeleteTree(root);}; //析构函数} 复制代码

Huffman树的构造

template
    
     HuffmanTree
     
      ::HuffmanTree(T weight[], int n) {    MinHeap
      
       
        > heap;    HuffmanTreeNode
        
          *parent,&left,&right;    HuffmanTreeNode
         
           *NodeList = new HuffmanTreeNode
          
           [n]; for(int i=0;i
           
            ; left = heap.removeMin(); right = heap.removeMin(); MergeTree(left,right,parent); //合并两颗最小子树 heap.Insert(*parent); root = parent; //建立根节点 } delete [] NodeList;}复制代码

Huffman树编码效率

估计Huffman编码所节省的空间

平均每个字符的代码长度等于每个代码的长度 ci 乘以其出现的概率 pi ，即: c0p0 + c1p1 + ... + cn-1pn-1 或 (c0f0 + c1f1 + ... + cn-1fn-1) / fT 这里fi为第i个字符的出现频率，而fT为所有字符出现的总次数

总之，概率分布越不均匀，压缩比越高；最差的压缩比与等长编码一样。实际效率分析，参考