数据结构 | Huffman编码树

一　建立Huffman编码树

Huffman编码将为字符分配代码。代码长度取决于对应字母的相对使用频率或者“权重”，因此它是一种变长编码。它的得到源于称为Huffman编码树的满二叉树。这棵树的每个叶结点对应一个字母，叶结点的权重就是对应字母的出现频率——这样设计的目的是按照最小外部路径权重建立一棵树，亦即对于给定叶结点集合具有加权路径长度（叶结点的权重乘以深度）之和最小的二叉树。简单地说，权重大的叶结点深度小。

建立n个结点的Huffman树很简单：

创建n个初始的Huffman树，每棵树包含单一的叶结点；
将这n棵树按照权重由小到大排为一列；
把前两棵树（权重最小的两棵树）标记为Huffman树的叶结点，并标记为一个分支结点（这个结点的权重是这两个叶结点权重之和）的两个子结点，将形成的新树置于序列中适当的位置，使序列始终为升序。重复本步骤直至序列中只剩下一个元素。

图F1展示了一个建立过程（局部）。
F1.建立Huffman树（局部）示例

单击此处查看Huffman树结点的实现

下面是从教材中摘录的Huffman树结点的实现。在这个实现中有两个子类——叶结点类和分支结点类。将其分类是因为这两种结点的构造不一致。

// Huffman tree node abstract base class
template <typename E> class HuffNode {
public:
  virtual ~HuffNode() {}                // Base destructor
  virtual int weight() = 0;             // Return frequency
  virtual bool isLeaf() = 0;            // Determine type
};
template <typename E>   // Internal node subclass
class IntlNode : public HuffNode<E> {
private:
  HuffNode<E>* lc;   // Left child
  HuffNode<E>* rc;   // Right child
  int wgt;              // Subtree weight
public:
  IntlNode(HuffNode<E>* l, HuffNode<E>* r)
    { wgt = l->weight() + r->weight(); lc = l; rc = r; }
  int weight() { return wgt; }
  bool isLeaf() { return false; }
  HuffNode<E>* left() const { return lc; }
  void setLeft(HuffNode<E>* b)
    { lc = (HuffNode<E>*)b; }
  HuffNode<E>* right() const { return rc; }
  void setRight(HuffNode<E>* b)
    { rc = (HuffNode<E>*)b; }
};
template <typename E>   // Leaf node subclass
class LeafNode : public HuffNode<E> {
private:
  E it;			// Value
  int wgt;		// Weight
public:
  LeafNode(const E& val, int freq)   // Constructor
    { it = val; wgt = freq; }
  int weight() { return wgt; }
  E val() { return it; }
  bool isLeaf() { return true; }
};

单击此处查看Huffman树的类说明

下面是从教材中摘录的Huffman树的类说明。

// HuffTree is a template of two parameters: the element
//  type being coded and a comparator for two such elements.
template <typename E>
class HuffTree {
private:
  HuffNode<E>* Root;         // Tree root
public:
  HuffTree(E& val, int freq) // Leaf constructor
    { Root = new LeafNode<E>(val, freq); }
  // Internal node constructor
  HuffTree(HuffTree<E>* l, HuffTree<E>* r)
    { Root = new IntlNode<E>(l->root(), r->root()); }
  ~HuffTree() {}                          // Destructor
  HuffNode<E>* root() { return Root; }    // Get root
  int weight() { return Root->weight(); } // Root weight
};

单击此处查看Huffman树构造函数的实现

下面是从教材中摘录的Huffman树构造函数的实现。注意传入的参数中HuffTree<E>** TreeArray是一个数组（的首元素）——这个数组的内容是之前提到过的初始的Huffman树，每棵树包含单一的叶结点。

Huffman树的建立方法是贪心算法（总是做出在当前看来是最好的选择，不从整体最优上加以考虑的算法）的一个例子。它总是选择当前权重最小的两棵子树相结合，简化了算法。

// Build a Huffman tree from a collection of frequencies
template <typename E> HuffTree<E>*
buildHuff(HuffTree<E>** TreeArray, int count) {
  heap<HuffTree<E>*,minTreeComp>* forest =
    new heap<HuffTree<E>*, minTreeComp>(TreeArray,
                                        count, count); 
  HuffTree<char> *temp1, *temp2, *temp3 = NULL;
  while (forest->size() > 1) {
    temp1 = forest->removefirst();   // Pull first two trees  
    temp2 = forest->removefirst();   //   off the list
    temp3 = new HuffTree<E>(temp1, temp2);
    forest->insert(temp3);  // Put the new tree back on list
    delete temp1;        // Must delete the remnants
    delete temp2;        //   of the trees we created
  }
  return temp3;
}

二　Huffman编码

从根结点开始，分别把0或者1标于树的每条边上——其中，0对应于连接左子结点的那条边，1对应于连接右子结点的那条边。例如对图F1，它的被标记的Huffman树如图F2所示，并可以得到字母编码如表T1所示。
F2.被标记的Huffman树示例

字母	频率	编码	位
C	32	1110	4
D	42	101	3
E	120	0	1
K	7	111101	6
L	42	110	3
M	24	11111	5
U	37	100	3
Z	2	111100	6

T1.对应于图F2字母的Huffman编码

一 建立Huffman编码树

二 Huffman编码

一　建立Huffman编码树

二　Huffman编码