huffman coding python

1import math
2import sys
3global probabilities
4probabilities = []
5
6class HuffmanCode:
7    def __init__(self,probability):
8        self.probability = probability
9
10    def position(self, value, index):
11        for j in range(len(self.probability)):
12            if(value >= self.probability[j]):
13                return j
14        return index-1
15
16    def characteristics_huffman_code(self, code):
17        length_of_code = [len(k) for k in code]
18
19        mean_length = sum([a*b for a, b in zip(length_of_code, self.probability)])
20
21        print("Average length of the code: %f" % mean_length)
22        print("Efficiency of the code: %f" % (entropy_of_code/mean_length))
23
24    def compute_code(self):
25        num = len(self.probability)
26        huffman_code = ['']*num
27
28        for i in range(num-2):
29            val = self.probability[num-i-1] + self.probability[num-i-2]
30            if(huffman_code[num-i-1] != '' and huffman_code[num-i-2] != ''):
31                huffman_code[-1] = ['1' + symbol for symbol in huffman_code[-1]]
32                huffman_code[-2] = ['0' + symbol for symbol in huffman_code[-2]]
33            elif(huffman_code[num-i-1] != ''):
34                huffman_code[num-i-2] = '0'
35                huffman_code[-1] = ['1' + symbol for symbol in huffman_code[-1]]
36            elif(huffman_code[num-i-2] != ''):
37                huffman_code[num-i-1] = '1'
38                huffman_code[-2] = ['0' + symbol for symbol in huffman_code[-2]]
39            else:
40                huffman_code[num-i-1] = '1'
41                huffman_code[num-i-2] = '0'
42
43            position = self.position(val, i)
44            probability = self.probability[0:(len(self.probability) - 2)]
45            probability.insert(position, val)
46            if(isinstance(huffman_code[num-i-2], list) and isinstance(huffman_code[num-i-1], list)):
47                complete_code = huffman_code[num-i-1] + huffman_code[num-i-2]
48            elif(isinstance(huffman_code[num-i-2], list)):
49                complete_code = huffman_code[num-i-2] + [huffman_code[num-i-1]]
50            elif(isinstance(huffman_code[num-i-1], list)):
51                complete_code = huffman_code[num-i-1] + [huffman_code[num-i-2]]
52            else:
53                complete_code = [huffman_code[num-i-2], huffman_code[num-i-1]]
54
55            huffman_code = huffman_code[0:(len(huffman_code)-2)]
56            huffman_code.insert(position, complete_code)
57
58        huffman_code[0] = ['0' + symbol for symbol in huffman_code[0]]
59        huffman_code[1] = ['1' + symbol for symbol in huffman_code[1]]
60
61        if(len(huffman_code[1]) == 0):
62            huffman_code[1] = '1'
63
64        count = 0
65        final_code = ['']*num
66
67        for i in range(2):
68            for j in range(len(huffman_code[i])):
69                final_code[count] = huffman_code[i][j]
70                count += 1
71
72        final_code = sorted(final_code, key=len)
73        return final_code
74
75string = input("Enter the string to compute Huffman Code: ")
76
77freq = {}
78for c in string:
79    if c in freq:
80        freq[c] += 1
81    else:
82        freq[c] = 1
83
84freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)
85length = len(string)
86
87probabilities = [float("{:.2f}".format(frequency[1]/length)) for frequency in freq]
88probabilities = sorted(probabilities, reverse=True)
89
90huffmanClassObject = HuffmanCode(probabilities)
91P = probabilities
92
93huffman_code = huffmanClassObject.compute_code()
94
95print(' Char | Huffman code ')
96print('----------------------')
97
98for id,char in enumerate(freq):
99    if huffman_code[id]=='':
100        print(' %-4r |%12s' % (char[0], 1))
101        continue
102    print(' %-4r |%12s' % (char[0], huffman_code[id]))
103
104huffmanClassObject.characteristics_huffman_code(huffman_code)
105