compression/programiz.py at code · Jachtabahn/compression · GitHub

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
# Huffman Coding in python

DEBUG=False

string='BCAADDDCCACACAC'


classNodeTree(object):

def__init__(self, left=None, right=None):
self.left=left
self.right=right

defchildren(self):
return (self.left, self.right)

defnodes(self):
return (self.left, self.right)

def__str__(self):
return'%s_%s'% (self.left, self.right)


defhuffmanCodeTree(node, left=True, binString=''):
iftype(node) isstr:
return {node: binString}
 (l, r) =node.children()
d=dict()
d.update(huffmanCodeTree(l, True, binString+'0'))
d.update(huffmanCodeTree(r, False, binString+'1'))
returnd


ifDEBUG:
print('Input file: '+sys.argv[1])

freq= {}
forcinstring:
ifcinfreq:
freq[c] +=1
else:
freq[c] =1

freq=sorted(freq.items(), key=lambdax: x[1], reverse=True)

ifDEBUG:
print(' Char | Freq ')
for (key, c) infreq:
print(' %4r | %d'% (key, c))

nodes=freq

whilelen(nodes) >1:
 (key1, c1) =nodes[-1]
 (key2, c2) =nodes[-2]
nodes=nodes[:-2]
node=NodeTree(key1, key2)
nodes.append((node, c1+c2))

nodes=sorted(nodes, key=lambdax: x[1], reverse=True)

ifDEBUG:
print('left: %s'%nodes[0][0].nodes()[0])
print('right: %s'%nodes[0][0].nodes()[1])

huffmanCode=huffmanCodeTree(nodes[0][0])

print(' Char | Huffman code ')
print('----------------------')
for (char, frequency) infreq:
print(' %-4r |%12s'% (char, huffmanCode[char]))