Python 算法(2) 哈夫曼编码 Huffman Encoding详解编程语言

 

  这个问题原始是用来实现一个可变长度的编码问题,但可以总结成这样一个问题,假设我们有很多的叶子节点,每个节点都有一个权值w(可以是任何有意义的数值,比如它出现的概率),我们要用这些叶子节点构造一棵树,那么每个叶子节点就有一个深度d,我们的目标是使得所有叶子节点的权值与深度的乘积之和$$/Sigma w{i}d{i}$$最小。

  很自然的一个想法就是,对于权值大的叶子节点我们让它的深度小些(更加靠近根节点),权值小的让它的深度相对大些,这样的话我们自然就会想着每次取当前权值最小的两个节点将它们组合出一个父节点,一直这样组合下去直到只有一个节点即根节点为止。如下图所示的示例

代码实现比较简单,使用了heapq模块,树结构是用list来保存的,有意思的是其中zip函数的使用,其中统计函数count作为zip函数的参数,  Python 算法(2) 哈夫曼编码 Huffman Encoding详解编程语言

 

 

 

 

代码实现比较简单,使用了heapq模块,树结构是用list来保存的,有意思的是其中zip函数的使用,其中统计函数count作为zip函数的参数,

from heapq import heapify, heappush, heappop 
from itertools import count 
 
def huffman(seq, frq): 
    num = count() 
    trees = list(zip(frq, num, seq))            # num ensures valid ordering 
    heapify(trees)                              # A min-heap based on freq 
    while len(trees) > 1:                       # Until all are combined 
        fa, _, a = heappop(trees)               # Get the two smallest trees 
        fb, _, b = heappop(trees) 
        n = next(num) 
        heappush(trees, (fa+fb, n, [a, b]))     # Combine and re-add them 
    # print trees 
    return trees[0][-1] 
 
seq = "abcdefghi" 
frq = [4, 5, 6, 9, 11, 12, 15, 16, 20] 
print huffman(seq, frq) 
# [['i', [['a', 'b'], 'e']], [['f', 'g'], [['c', 'd'], 'h']]]

现在我们考虑另外一个问题,合并文件问题,假设我们将大小为 m 和大小为 n 的两个文件合并在一起需要 m+n 的时间,现在给定一些文件,求一个最优的合并策略使得所需要的时间最小。

如果我们将上面哈夫曼树中的叶子节点看成是文件,两个文件合并得到的大文件就是树中的内部节点,假设每个节点上都有一个值表示该文件的大小,合并得到的大文件上的值是合并的两个文件的值之和,那我们的目标是就是使得内部节点的和最小的合并方案,因为叶子节点的大小是固定的,所以实际上也就是使得所有节点的和最小的合并方案!

细想也就有了一个叶子节点的所有祖先节点们都有一份该叶子节点的值包含在里面,也就是说所有叶子节点的深度与它的值的乘积之和就是所有节点的值之和!可以看下下面的示例图,最终我们知道哈夫曼树就是这个问题的解决方案。

            Python 算法(2) 哈夫曼编码 Huffman Encoding详解编程语言

 

 

 哈夫曼树问题的一个扩展就是最优二叉搜索树问题,后者可以用动态规划算法来求解

 其他实现方式:

#Huffman Encoding 
 
#Tree-Node Type 
class Node: 
    def __init__(self,freq): 
        self.left = None 
        self.right = None 
        self.father = None 
        self.freq = freq 
    def isLeft(self): 
        return self.father.left == self 
#create nodes创建叶子节点 
def createNodes(freqs): 
    return [Node(freq) for freq in freqs] 
 
#create Huffman-Tree创建Huffman树 
def createHuffmanTree(nodes): 
    queue = nodes[:] 
    while len(queue) > 1: 
        queue.sort(key=lambda item:item.freq) 
        node_left = queue.pop(0) 
        node_right = queue.pop(0) 
        node_father = Node(node_left.freq + node_right.freq) 
        node_father.left = node_left 
        node_father.right = node_right 
        node_left.father = node_father 
        node_right.father = node_father 
        queue.append(node_father) 
    queue[0].father = None 
    return queue[0] 
#Huffman编码 
def huffmanEncoding(nodes,root): 
    codes = [''] * len(nodes) 
    for i in range(len(nodes)): 
        node_tmp = nodes[i] 
        while node_tmp != root: 
            if node_tmp.isLeft(): 
                codes[i] = '0' + codes[i] 
            else: 
                codes[i] = '1' + codes[i] 
            node_tmp = node_tmp.father 
    return codes 
 
if __name__ == '__main__': 
    #chars = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N'] 
    #freqs = [10,4,2,5,3,4,2,6,4,4,3,7,9,6] 
    chars_freqs = [('C', 2), ('G', 2), ('E', 3), ('K', 3), ('B', 4), 
                   ('F', 4), ('I', 4), ('J', 4), ('D', 5), ('H', 6), 
                   ('N', 6), ('L', 7), ('M', 9), ('A', 10)] 
    nodes = createNodes([item[1] for item in chars_freqs]) 
    root = createHuffmanTree(nodes) 
    codes = huffmanEncoding(nodes,root) 
    for item in zip(chars_freqs,codes): 
        print 'Character:%s freq:%-2d   encoding: %s' % (item[0][0],item[0][1],item[1])

输出结果:

>>> 
Character:C freq:2  encoding: 10100 
Character:G freq:2  encoding: 10101 
Character:E freq:3  encoding: 0000 
Character:K freq:3  encoding: 0001 
Character:B freq:4  encoding: 0100 
Character:F freq:4  encoding: 0101 
Character:I freq:4  encoding: 0110 
Character:J freq:4  encoding: 0111 
Character:D freq:5  encoding: 1011 
Character:H freq:6  encoding: 1110 
Character:N freq:6  encoding: 1111 
Character:L freq:7  encoding: 001 
Character:M freq:9  encoding: 100 
Character:A freq:10 encoding: 110

 

原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/15781.html

(0)
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论