pythonはハフマン符号化を実現
12170 ワード
一、問題
二叉木の構造を利用してHuffman木を符号化し、最短符号化二、解決を実現する
三、総括ハフマンツリーの符号化形式でデータの圧縮が可能であるため、ハフマンの応用も広範である.ここにメモしておくと便利です.
転載先:https://www.cnblogs.com/future-dream/p/10801934.html
二叉木の構造を利用してHuffman木を符号化し、最短符号化二、解決を実現する
1 #
2 class TreeNode:
3 def __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 self.code = ""
13
14
15 #
16 def create_node_queue(codes):
17 queue = []
18 for code in codes:
19 queue.append(TreeNode(code))
20 return queue
21
22
23 #
24 def add_queue(queue, node_new):
25 if len(queue) == 0:
26 return [node_new]
27 for i in range(len(queue)):
28 if queue[i].priority >= node_new.priority:
29 return queue[:i] + [node_new] + queue[i:]
30 return queue + [node_new]
31
32
33 #
34 class NodeQueue:
35 def __init__(self, code):
36 self.queue = create_node_queue(code)
37 self.size = len(self.queue)
38
39 def add_node(self, node):
40 self.queue = add_queue(self.queue, node)
41 self.size += 1
42
43 def pop_node(self):
44 self.size -= 1
45 return self.queue.pop(0)
46
47
48 #
49 def frequent_char(string_s):
50 store_d = {}
51 for c in string_s:
52 if c not in store_d:
53 store_d[c] = 1
54 else:
55 store_d[c] += 1
56 return sorted(store_d.items(), key=lambda x: x[1])
57
58
59 # Huffman
60 def create_huffman_tree(node_queue):
61 while 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)
68 return node_queue.pop_node()
69
70
71 code_dict1 = {}
72 code_dict2 = {}
73
74
75 # Huffman Huffman
76 def huffman_code_dict(head, x):
77 # global code_dict, code_list
78 if head:
79 huffman_code_dict(head.left_child, x + "0")
80 head.code += x
81 if head.value:
82 code_dict2[head.code] = head.value
83 code_dict1[head.value] = head.code
84 huffman_code_dict(head.right_child, x + "1")
85
86
87 #
88 def trans_encode(string_s):
89 # global code_dict1
90 trans_code = ""
91 for c in string_s:
92 trans_code += code_dict1[c]
93 return trans_code
94
95
96 #
97 def trans_decode(string_s):
98 # global code_dict1
99 code = ""
100 answer = ""
101 for c in string_s:
102 code += c
103 if code in code_dict2:
104 answer += code_dict2[code]
105 code = ""
106 return answer
三、総括ハフマンツリーの符号化形式でデータの圧縮が可能であるため、ハフマンの応用も広範である.ここにメモしておくと便利です.
転載先:https://www.cnblogs.com/future-dream/p/10801934.html