-
Notifications
You must be signed in to change notification settings - Fork 0
/
huffman.py
215 lines (154 loc) · 5.12 KB
/
huffman.py
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
import binascii
import math
# Nó de uma árvore de Huffman
class Node:
# Inicializa nó da árvore
def __init__(self, symbol, frequency, code = "", left = None, right = None):
self.symbol = symbol
self.frequency = frequency
self.left = left
self.right = right
self.code = code
# Árvore Binária
class BTree:
# Inicializa árvore binária
def __init__(self, root = None):
self.root = root
# Inserção
def insert(self, symbol, frequency, code):
if self.root is None:
self.root = Node(symbol, frequency, code)
else:
self._insert(symbol, frequency, self.root, code)
# Inserção
def _insert(self, symbol, frequency, node, code):
if frequency < node.frequency:
if node.left is not None:
self._insert(symbol, frequency, node.left, code)
else:
node.left = Node(symbol, frequency, code)
else:
if node.right is not None:
self._insert(symbol, frequency, node.right, code)
else:
node.right = Node(symbol, frequency, code)
# Insere nó como nó raiz
def insert_root_node(self, node):
if self.root is None:
self.root = node
else:
return
# Imprime a probabilidade dos símbolos em uma tabela
# Codificação com Huffman
class Huffman:
# Inicializa codificação
def __init__(self):
self.content = None
self.encoded_content = None
self.symbols = dict()
self.huffman_encoding = dict()
self.gains = dict()
self.huffman_tree = BTree()
# Calcula a probabilidade dos símbolos
def __calculate_probability(self):
for el in self.content:
if(self.symbols.get(el) == None):
self.symbols[el] = 1
else:
self.symbols[el] += 1
# Calcula os códigos
def __calculate_codes(self, node, value = ""):
value = value + str(node.code)
if(node.left):
self.__calculate_codes(node.left, value)
if(node.right):
self.__calculate_codes(node.right, value)
if(not node.left and not node.right):
self.huffman_encoding[node.symbol] = value
# Ganho total de compressão em bits (Desconsiderando o preâmbulo)
def __total_gain(self):
uncompressed = len(self.content) * 8
compressed = 0
for symbol in self.huffman_encoding.keys():
count = self.content.count(symbol)
compressed += count * len(self.huffman_encoding[symbol])
self.gains = {"uncompressed": math.ceil(uncompressed / 8), "compressed": math.ceil(compressed / 8)}
# Resultado da compressão e conversão para binário
def __encode_output(self):
output = []
for c in self.content:
output.append(self.huffman_encoding[c])
self.encoded_content = self.__bitstring_to_bytes('1' + ''.join([str(item) for item in output]))
# Conversão de string de bits para blob de bytes
def __bitstring_to_bytes(self, value):
return int(value, 2).to_bytes((len(value) + 7) // 8, byteorder='big')
# Codificação com Huffman
def encode(self, content):
self.content = content
self.__calculate_probability()
# Inicializa fila de prioridade dos nós
nodes = []
# Converte símbolos e probabilidades em nós da árvore Huffman
for key, value in self.symbols.items():
nodes.append(Node(key, value))
while len(nodes) > 1:
nodes = sorted(nodes, key=lambda x: x.frequency)
right = nodes[0]
left = nodes[1]
left.code = 0b0
right.code = 0b1
node = Node(left.symbol + right.symbol, left.frequency + right.frequency, left = left, right = right)
nodes.remove(left)
nodes.remove(right)
nodes.append(node)
# Inicializa árvore
self.huffman_tree.insert_root_node(nodes[0])
self.__calculate_codes(self.huffman_tree.root)
self.__total_gain()
self.__encode_output()
# Decodificação com Huffman
def decode(self, encoded_content):
tree_head = self.huffman_tree.root
btree = self.huffman_tree.root
self.encoded_content = bin(int(binascii.hexlify(encoded_content), base=16)).lstrip('0b')
decoded_content = []
for it in self.encoded_content[1:]:
if( it == '1'):
btree = btree.right
elif( it == '0'):
btree = btree.left
try:
if btree.left.symbol == None and btree.right.symbol == None:
pass
except AttributeError:
decoded_content.append(btree.symbol)
btree = tree_head
self.content = ''.join([str(it) for it in decoded_content])
# Obter ganhos totais em bytes
def get_gains(self):
return self.gains
# Obter conteúdo do texto
def get_content(self):
return self.content.encode("utf-8")
# Obter conteúdo do texto codificado
def get_encode_content(self):
return self.encoded_content
# Obter árvore de huffman
def get_tree(self):
return self.huffman_tree
# Definir árvore de huffman
def set_tree(self, huffman_tree):
self.huffman_tree = huffman_tree
# Obtem tabela com probabilidade, número de bits originais e número de bits após compressão
def get_table(self):
total = 0
prob_dict = dict()
original_bits = dict()
compressed_bits = dict()
for value in self.symbols.values():
total += value
for value in self.symbols.items():
prob_dict[value[0]] = str((value[1]/total) * 100)+'%'
original_bits[value[0]] = '8 bits'
compressed_bits[value[0]] = str(len(self.huffman_encoding[value[0]])) + ' bits'
return {'probability': prob_dict, 'original': original_bits, 'compressed': compressed_bits}