首页 > Python算法 > 贪心算法 阅读数:46

哈夫曼编码—贪心算法经典例子

哈夫曼编码是一种变长的字符编码方式,常用于对指定的字符集进行数据压缩,压缩率在 20%~90%。

1. 问题描述

现在有一个包含 5 个字符的字符表 {A,B,C,D,E},各字符出现的频率统计如表 1 所示。

表 1:各字符出现的频率统计
字符 出现概率 字符 出现概率 字符 出现概率
A 0.35 C 0.2 E 0.15
B 0.1 D 0.2    

需要构造一种有效率的编码类型,使用该编码表达以上字符表内容时可以产生平均长度最短的位串。在对由 n 个字符组成的文本进行编码过程中,有两种编码方式,即定长编码和变长编码。

对于定长编码而言,会为每个字符赋予一个长度固定为 m(m≥log2n) 的位串,我们常用的标准 ASCII 码就是采用定长编码策略对字符集进行编码的。长度各异的编码,其中出现频率较高的字符,采用长度较短的编码表示,出现频率较低的字符,采用长度较长的编码表示。著名的摩尔斯电码就是采用这种策略进行编码的。

通常情况下,与定长编码相比,变长编码可以有效减少表示同一字符集所需的编码长度,提升编码效率。但是,为了使用变长编码策略,需要解决在定长编码模式下不会遇到的一个问题,就是前缀码问题。对每一个字符规定一个 0-1 串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀,这种编码称为前缀码。

有了前缀码,我们可以在编码完成的位串中准确定位每个属于字符集的字符,通过简单扫描一个位串,直到得到某个等于字符集中字符的位串后,将该字符替换之前的位串,重复以上操作,即可根据位串恢复原来的文本。本节所讲的哈夫曼编码就是一种前缀码。

2. 哈夫曼树

为了对某字母表构造一套二进制的前缀码,可以借助二叉树。将树中所有的左向边都标记为0,所有的右向边都标记为 1。通过记录从根节点到字符所在的叶子节点的简单路径上的所有 0-1 标记来获得表示该字符的编码。

用于表示二进制前缀码的二叉树每个叶子节点对应一个字符,非叶子节点不对应任何字符。由于二叉树叶子节点之间没有互联的简单路径,所以依据这种二叉树生成的编码序列为前缀码,即字符集中各个字符对应的前缀各不相同。

对于给定的字符集和字符表而言,每个字符的出现频率可以确定,我们怎么才能构造一棵二叉树,将较短的编码分配给高频字符,将较长的编码分配给低频字符呢?用贪心算法可以实现这个目标。

这个算法由戴维·哈夫曼(David Huffman)发明,因此,能达到这个目标的二叉树称为哈夫曼树。

具体算法如下:
  • 初始化 n 个单节点的树,并为它们标上字母表中的字符。把每个字符出现的频率记在其对应的根节点中,用来标记各个树的权重,即树的权重等于树中所有叶子节点的概率之和。
  • 重复下面的步骤,直到只剩一颗单独的树。找到两棵权重最小的树,若两棵树权重相同,可任选其一,分别把它们作为新二叉树的左右子树,并把其权重之和作为新的权重记录在新树的根节点中。

用上述算法构造出的二叉树即为哈夫曼树。根据哈夫曼树获取的编码称为哈夫曼编码。

在初始状态,构造图 1 所示的根节点集合。
初始化根节点示意图
图 1:初始化根节点示意图

此时,我们将节点 B 和 E 合并成一棵新的子树,如图 2 所示。
合并节点B和E后示意图
图 2:合并节点B和E后示意图

合并节点  B 和 E 之后,重新排序根节点,合并两个权值最小的节点,即节点 C 和 D,如图 3 所示。
合并节点C和D后示意图
图 3:合并节点 C 和 D 后示意图

之后,合并由节点 B 和 E 组成的树的根节点和节点 A,如图 4 所示。
合并由节点B和E组成的树的根节点和节点A后示意图
图 4:合并由节点 B 和 E 组成的树的根节点和节点 A 后示意图

最后,获取剩余的两个节点,得到结果哈夫曼树,如图 5 所示。
结果哈夫曼树示意图
图 5:结果哈夫曼树示意图

获得哈夫曼树后,根据沿着结果哈夫曼树的左侧分支编 0,沿着右侧分支编 1,可以得到字符表中的各个字符的对应编码如表 2 所示。

表 2:对应编码
字符 出现概率 哈夫曼编码 字符 出现概率 哈夫曼编码
A 0.35 11 D 0.2 01
B 0.1 100 E 0.15 101
C 0.2 00      

至此,字符集编码问题得到解决。根据给定的字符出现的概率和求得的各字符对应的编码长度,若采用上述编码策略,每个字符的平均位长度为:

2 * 0.35 + 3 * 0.1 + 2 * 0.2 + 2 * 0.2 + 3 * 0.15 = 2.25


若采用定长编码策略,则表示上面字符表中的每个字符至少需要用 3 位编码来表示。因此,针对这一实例,哈夫曼编码的实现的压缩率为:

[(3 - 2.25) / 3] * 100% = 25%


综上,若采用哈夫曼编码,我们表达该字符集时比采用定长编码策略可以少占用 25% 的存储空间。

3. 贪心选择性质

二叉树 T 表示字符集 C 的一个最优前缀码,证明可以对 T 作适当修改后得到一棵新的二叉树 T'',在 T'' 中 x 和 y 是最深叶子节点且为兄弟,同时 T'' 表示的前缀码也是 C 的最优前缀码。设 b 和 c 是二叉树 T 的最深叶子,且为兄弟。设 f(b)≤f(c),f(x)≤f(y)。

由于 x 和 y 是 C 中具有最小频率的两个字符,有 f(x)≤f(b),f(y)≤f(c)。首先,在树 T 中交换叶子 b 和 x 的位置得到 T',然后在树 T' 中交换叶子 c 和 y 的位置,得到树 T'',如图 6 所示。由于 T 是字符集 C 的最优前缀码,因此可知 B(T)≤B(T'')。
贪心选择性质证明示意图
图 6:贪心选择性质证明示意图

由此可知,树 T 和 T' 的前缀码的平均码长之差为:
树 T 和 T' 的前缀码的平均码长之差
因此,可得出 B(T)≥B(T′)。

同理,可计算树 T' 和 T'' 的前缀平均码长只差为:
树T'和T''的前缀平均码长差
因此,可得出 B(T′)≥B(T′′)。

综上,可根据以下两个不等式得出最终结论:
最终结论

因此,T′′ 表示的前缀码也是最优前缀码,且 x 和 y 具有相同的码长,同时,仅最优一位编码不同。

4. 最优子结构性质

二叉树 T 表示字符集 C 的一个最优前缀码,x 和 y 是树 T 中的两个叶子且为兄弟,z 是它们的父亲。若将 z 当作是具有频率 f(z)=f(x)+f(y) 的字符,且定义树 T' 表示字符集 C'=C-{x,y}∪{z} 的一个最优前缀码。

因此,有:
1) c∈C−{x,y},dT(c)=dT'(c)=>f(c)dT(c)=f(c)dT'(c)
2) f(x)dT(x)+f(y)dT(y)=f(x)+f(y)+f(z)dT'(z)

B (T)=B(T′)+f(x)+f(y) 如果 T' 不是 C' 的最优前缀码,假定 T'' 是 C' 的最优前缀码,那么显然 T'' 是比 T 更优的前缀码,这与前提条件相矛盾,故 T' 所表示的 C' 的前缀码是最优的。

根据上述论证,生成哈夫曼树的策略具备贪心选择性质和最优子结构性质,因此,生成的哈夫曼树所对应的编码为最优前缀码。

5. 参考实现

实现代码如下:
# Huffman Encoding
# 树节点定义
class Node:
    def __init__(self,pro):
        self.left = None
        self.right = None
        self.parent = None
        self.pro = pro
    def isLeft(self): # 判断左子树
        return self.parent.left == self
#create nodes创建叶子节点
def createNodes(pros):
    return [Node(pro) for pro in pros]
#create Huffman-Tree创建Huffman树
def createHuffmanTree(nodes):
    queue = nodes[:]
    while len(queue) > 1:
        queue.sort(key=lambda item:item.pro)
        node_left = queue.pop(0)
        node_right = queue.pop(0)
        node_parent = Node(node_left.pro + node_right.pro)
        node_parent.left = node_left
        node_parent.right = node_right
        node_left.parent= node_parent
        node_right.parent= node_parent
        queue.append(node_parent)
    queue[0].parent= None
    return queue[0]
# Huffman编码
def huffmanEncoding(nodes,root):
    codes = [''] * len(nodes)
    for i in range(len(nodes)):
        node_temp = nodes[i]
        while node_temp != root:
            if node_temp.isLeft():
                codes[i] = '0' + codes[i]
            else:
                codes[i] = '1' + codes[i]
            node_temp = node_temp.parent
    return codes
if __name__ == '__main__':
    #letters = ['A','B','C','D','E']
    #pros = [35,10,20,20,15]
    letters_pros = [('B', 10), ('E', 15), ('C', 20), ('D', 20), ('A', 35)]
    nodes = createNodes([item[1] for item in letters_pros])
    root = createHuffmanTree(nodes)
    codes = huffmanEncoding(nodes, root)
    for item in zip(letters_pros, codes):
        print('Label:%s pro:%-2d Huffman Code:%s'%(item[0][0],item[0][1],item[1]))
最终的输出结果为:

Label:B pro:10 Huffman Code: 100
Label:E pro:15 Huffman Code: 101
Label:C pro:20 Huffman Code: 00
Label:D pro:20 Huffman Code: 01
Label:A pro:35 Huffman Code: 11