哈夫曼(Huffman)树是最优二叉树，基于哈夫曼树数据结构的编码方案称为哈夫曼编码，是一种常见的压缩编码。在这个数据指数递增的时代，高效的数据编码方案的意义不言而喻。构建哈夫曼树的过程和其他树类数据结构不过，它是自底向上。正是这个构建过程，使得编程实现该数据结构变得新奇。哈夫曼编码是不等长编码，稍后的实现中我们可以理解不等长编码的缘由。本文先简述哈夫曼树、哈夫曼编码，然后编程实现，最后以一个应用例子作为结尾。

哈夫曼树

定义

哈夫曼树有名最优二叉树，是带权路径长度最小的二叉树。为了给出带权路径长度的定义，我们先知道以下概念。

  • 结点的路径长度：结点到根结点的边数
  • 叶子结点的带权路径长度：叶子结点的权值和叶子结点的路径长度的乘积

根据上面的两个概念，给出树的带权路径长度。定义如下：

树的带权路径长度：树中的所有叶子结点的带权路径长度的和。

采用数据来表单如下：

1
WPL(Tree) = w1*l1 + ··· + wn*ln

各w值本表表示叶子结点的权重，l表示叶子结点的路径长度。

构造最优二叉树

构造最优二叉树的算法是Huffman提出，成为哈夫曼算法。该算法的具体过程如下：

（1）有二叉树集合Fn = {T1,T2,…,Tn}，权重分别是w1、w2、…、wn
（2）从Fn中取出两权值最小的二叉树Ti和Tj。构造新的树R，R的左右子树分别为Ti和Tj，R的根结点的权值为左右树权值和。
（3）把R加入到Fn中
（4）重复步骤（2）和（3）直到Fn中只有一颗树
（5）Fn中的最后一棵树为哈夫曼树

从上述的哈夫曼树构建过程可知，此数据结构是自底向上构建。相比之下，B树、AVL树、红黑树、BST等树类的构建过程都是自顶向下。

哈夫曼编码

哈夫曼编码来构建自哈夫曼树数据结构。直观上，可以理解为，编码的构建过程就是哈夫曼树的构建过程，编码和树的结点路径一一对应。我们一一个例子来理解。

字符串”littlefeng”中出现的字符集合{l,i,t,e,f,n,g}。它们的出现频次如下：

1
2
3
4
5
from collections import Counter
c = Counter("littlefeng")
>>> print(c)

Counter({'l': 2, 't': 2, 'e': 2, 'n': 1, 'g': 1, 'i': 1, 'f': 1})

不难计算出它们出现的频率：

{‘n’: 0.1, ‘l’: 0.2, ‘t’: 0.2, ‘g’: 0.1, ‘i’: 0.1, ‘f’: 0.1, ‘e’: 0.2}

我们把字符集合{l,i,t,e,f,n,g}看作二叉树集合，它们的权值就是它们的出现频率。于是，可以根据构造最优二叉树的算法过程构造字符串”littlefeng”的Haffuman树。

上面的表达并不严谨，仅用于直观理解。完整的算法过程如下：

（1）根据输入的字符串，统计出字符串及其出现频率的映射表
（2）一出现频率大小排序映射表
（3）选取映射表中频率最小的两个映射，这两个映射（其实就是两个键值对）构建一颗新的二叉树，它们出现的频率和作为根结点的权重。新构建的书重新放到排序映射表中。注意二叉树构建过程，频率较小的作为左叶子，较大的作为右叶子。
（4）重复步骤（3）知道映射表中只剩一个键值对（根结点）
（5）构建完成的二叉树左结点标记0，右结点标记1。那么各个字符的编码就是从根结点都该字符的叶子结点的标记的序列。

由于构建的树并不是平衡树，所以哈夫曼编码是不定长编码。

哈夫曼树和哈夫曼编码的实现

哈夫曼树的实现

实现哈夫曼树及哈夫曼编码需要较多的基础算法和数据结构，包括堆排序、优先队列、栈、树的遍历算法、二叉树的实现、递归编程、符号表（字典）。我们将使用Python实现，原因是Python代码简介，有“可执行的伪代码”称号。出于代码的简洁，我们不打算从最底层实现。例如，哈夫曼树的构造过程需要堆排序，将使用Python标准库中的heapq模块。

哈夫曼树也是二叉树，因此我们先定义树的结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from functools import total_ordering

@total_ordering
class Node:

    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.tag = None
        self.left = None
        self.right = None

    def __eq__(self, node):
        return self.weight == node.weight

    def __gt__(self, node):
        return self.weight > node.weight

    def __repr__(self):
        return 'Node<{}>'.format(self.weight)

self.value属性用于保存字符对象，在构建哈夫曼树并不需要，但实现哈夫曼编码时会用上。每个结点Node可以看作保存一个键值的映射。即

1
<k:v> == <value:weight>

__eq__和gt`用于实现Node对象的比较，堆排序过程需要对象具有可比较性。

优先队列的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import heapq

class PriorityQueue:

    def __init__(self, queue=None):
        if queue is not None:
            heapq.heapify(queue)
            self._q = queue
        else:
            self._q = []

    def push(self, item):
        heapq.heappush(self._q, item)

    def pop(self):
        return heapq.heappop(self._q)

    def empty(self):
        return len(self) == 0

    def __len__(self):
        return len(self._q)

构建哈希树

1
2
3
4
5
6
7
8
9
10
11
def build_huffman_tree_with_priority_queue(nodes):
    queue = PriorityQueue(nodes)
    while len(queue) > 1:
        left_child = queue.pop()
        right_child = queue.pop()
        total_weight = left_child.weight + right_child.weight
        root = Node(None, total_weight)
        root.left = left_child
        root.right = right_child
        queue.push(root)
    return queue.pop()

为了方便测试，我们编写一个生成结点序列的函数

1
2
3
4
5
def generate_nodes(weights):
    nodes = []
    for weight in weights:
        nodes.append(Node(Node, weight))
    return nodes

测试，我们建立序列[3, 1, 4, 1, 5, 9, 2, 6]的哈夫曼树。同时，编写一个树的广度优先遍历函数，用于呈现哈夫曼树的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Queue:
    
    def __init__(self):
        self._q = []

    def put(self, item):
        self._q.append(item)

    def get(self):
        item = self._q[0]
        del self._q[0]
        return item

    def empty(self):
        return len(self._q) == 0

def print_tree_from_top_to_bottom(root):
    queue = Queue()
    queue.put(root)
    while not queue.empty():
        node = queue.get()
        print(node)
        if node.left:
            queue.put(node.left)
        if node.right:
            queue.put(node.right)

weights = [3, 1, 4, 1, 5, 9, 2, 6]
nodes = generate_nodes(weights)
huffman_tree = build_huffman_tree_with_priority_queue(nodes)
print_tree_from_top_to_bottom(huffman_tree)

输出结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node<31>
Node<13>
Node<18>
Node<6>
Node<7>
Node<9>
Node<9>
Node<3>
Node<4>
Node<4>
Node<5>
Node<2>
Node<2>
Node<1>
Node<1>

我们可以手动建立该哈夫曼树检验输出。

哈夫曼编码的实现

构建哈夫曼编码是一个按深度遍历二叉树的过程，下面的实现采用递归方式是因为需要按层次把哈夫曼编码的前缀传入树的下一层中，这样的实现方便直观。codes是字典类型，用于保存字符的哈夫曼编码，由于字典是引用类型，_generate_codes不需要显式返回codes变量。有一个细节需要注意，计算机的浮点数运算是不精确的（例如在Python中0.2+0.4 == 0.6 的结果为False，因此这列使用decimal进行浮点数运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def _is_leaf_node(node):
    return bool(node.value)

def _generate_codes(node, prefix, codes):
    if _is_leaf_node(node):
        codes[node.value] = prefix
    else:
        left_prefix = prefix + '0'
        _generate_codes(node.left, left_prefix, codes)
        right_prefix = prefix + '1'
        _generate_codes(node.right, right_prefix, codes)

def generate_huffman_code(string):
    c = collections.Counter(string)
    length = len(string)
    code = {}
    nodes = []
    for value, weight in c.items():
        weight = decimal.Decimal(weight) / length
        nodes.append(Node(value, weight))
    tree = build_huffman_tree_with_priority_queue(nodes)
    codes = {}
    _generate_codes(tree, '', codes)
    return codes

下面构建给定字符串的哈夫曼编码，输入littlefeng字符串。

1
2
3
4
def main():
    string = 'littlefeng'
    codes = generate_huffman_code(string)
    print(codes)

输入字符串中各字符出现的频率

1
2
3
4
{'t': '0.2', 'f': '0.1', 
'g': '0.1', 'l': '0.2', 
'i': '0.1', 'e': '0.2', 
'n': '0.1'}

输出如下

1
2
3
4
{'n': '000', 'e': '01', 
'l': '110', 'i': '001', 
't': '10', 'g': '1111', 
'f': '1110'}

有了哈夫曼编码，接下来我们实现哈夫曼编码的解码过程。

哈夫曼编码的解码

哈夫曼编码的解码过程本质上是树的遍历过程，根据哈夫曼编码的构造过程不能写出实现。

1
2
3
4
5
6
7
8
9
10
11
def decode_huffman_codes(root, codes):
    p_node = root
    for code in codes:
        if code == '0':
            p_node = p_node.left
        else:
            p_node = p_node.right
            
        if _is_leaf_node(p_node):
            yield p_node.value
            p_node = root

应用例子

本节通过哈夫曼编码实现字符串压缩。

总结