python实现Huffman编码⼀、问题
利⽤⼆叉树的结构对Huffman树进⾏编码，实现最短编码
⼆、解决
1# 构建节点类
2class TreeNode:
3def__init__(self, data):
4"""
5        :data is a tuple the first element is value and the second is priority
6        :param data:
7"""
8        self.value = data[0]
9        self.priority = data[1]
10        self.left_child = None
11        self.right_child = None
12        de = ""
13
14
15# 创建树节点队列的函数
16def create_node_queue(codes):
17    queue = []
18for code in codes:
19        queue.append(TreeNode(code))
20return queue
21
22
23# 在队列中间添加新的节点元素并保证优先度从⼤到⼩排列
24def add_queue(queue, node_new):
25if len(queue) == 0:
26return [node_new]
27for i in range(len(queue)):
28if queue[i].priority >= node_new.priority:
29return queue[:i] + [node_new] + queue[i:]
30return queue + [node_new]
31
32
33# 节点队列类
34class NodeQueue:
35def__init__(self, code):
36        self.queue = create_node_queue(code)
37        self.size = len(self.queue)
38
39def add_node(self, node):
40        self.queue = add_queue(self.queue, node)
41        self.size += 1
42
43def pop_node(self):
44        self.size -= 1
45return self.queue.pop(0)
46
47
48# 各个字符在字符串中出现的次数即计算优先度
49def frequent_char(string_s):
50    store_d = {}
51for c in string_s:
52if c not in store_d:
53            store_d[c] = 1
54else:
55            store_d[c] += 1
56return sorted(store_d.items(), key=lambda x: x[1])
57
58
59# 创建Huffman树
60def create_huffman_tree(node_queue):
61while node_queue.size != 1:
62        node1 = node_queue.pop_node()
63        node2 = node_queue.pop_node()
64        r_1 = TreeNode([None, node1.priority + node2.priority])
65        r_1.left_child = node1
66        r_1.right_child = node2
67        node_queue.add_node(r_1)
68return node_queue.pop_node()
69
70
71 code_dict1 = {}
72 code_dict2 = {}
73
74
75# 由Huffman树得到的Huffman编码表
76def huffman_code_dict(head, x):
77# global code_dict, code_list
78if head:
79        huffman_code_dict(head.left_child, x + "0")
80        de += x
81if head.value:
82            code_de] = head.value
83            code_dict1[head.value] = de
84        huffman_code_dict(head.right_child, x + "1")
85
86
87# 字符串编码
88def trans_encode(string_s):
89# global code_dict1
90    trans_code = ""
91for c in string_s:
92        trans_code += code_dict1[c]
93return trans_code
94
95
96# 字符串解码
二叉树的遍历python
97def trans_decode(string_s):
98# global code_dict1
99    code = ""
100    answer = ""
101for c in string_s:
102        code += c
103if code in code_dict2:
104            answer += code_dict2[code]
105            code = ""
106return answer
三、总结
利⽤Huffman树的编码形式可以进⾏数据的压缩，因此Huffman的应⽤也很⼴泛。在此记录⼀下⽅便以后查看。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。