xcc.es
[READ-ONLY] Mirror of https://github.com/mrgnw/python-scripts.
3.3 kB
144 lines
1# Choose the two lowest frequencies
2# Combine these frequencies as the parent frequency for both nodes
3 # Left branches = 0 (lesser used = 0)
4 # Right branches = 1 ( more used = 1)
5# Repeat
6
7# PriorityQueue makes it easy to manage the data
8import PriorityQueue
9
10
11def count_chars(str):
12 dict = {}
13 for char in str:
14 if char in dict:
15 dict[char] += 1
16 else:
17 dict[char] = 1
18 return dict
19
20def queue_dict(dict):
21 term_queue = PriorityQueue()
22 for t in dict:
23 this_q_item = Q_item(t, dict[t])
24 term_queue.add(this_q_item)
25
26 return term_queue
27
28
29def count_and_q(str):
30 return queue_dict(count_chars(str))
31
32def huffmanate(str):
33 pq = count_and_q(str)
34 bitdict = {}
35 while len(pq) > 1:
36 #1 POP first two
37 alpha = pq.remove()
38 bravo = pq.remove()
39
40 #2 Prepend bitstrings to letters (in bitdict)
41 for a in alpha.thing:
42 if a in bitdict:
43 bitdict[a] = '0' + bitdict[a]
44 else:
45 bitdict[a] = '0'
46 for b in bravo.thing:
47 if b in bitdict:
48 bitdict[b] = '1' + bitdict[b]
49 else:
50 bitdict[b] = '1'
51
52 omega = alpha + bravo
53 pq.add(omega)
54
55
56 # Generate bitstring
57 bitstr = ''
58 word = ''
59 for a in str:
60 word += a
61 if word in bitdict:
62 bitstr += bitdict[word]
63 word = ''
64
65 return bitstr, bitdict
66
67def flip_dictionary(dictionary):
68 #return dict((dictionary[k], k) for k in dictionary)
69 new_dict = {}
70 for k in dictionary:
71 new_dict.update({dictionary[k] : k})
72 return new_dict
73
74
75def dehuffmanate(bitstring, bitdict):
76 bit2char = flip_dictionary(bitdict)
77
78 str = ''
79 word = ''
80 for a in bitstring:
81 word += a
82 if word in bit2char:
83 str += bit2char[word]
84 word = ''
85
86 return str
87
88
89def q_test():
90 alan = Q_item('alan', 3)
91 brad = Q_item('brad', 2)
92 carl = Q_item('carl', 1)
93 alanbrad = alan + brad
94
95 tesco = PriorityQueue()
96 tesco.add(brad)
97 tesco.add(alan)
98 tesco.add(carl)
99 tesco.add(alanbrad)
100 print tesco
101
102 return 'q_test done'
103
104#q_test()
105
106def huff_setup():
107 ex1 = 'abacabbac'
108 ex2 = 'alskdjflwweltkjh;lkj;lwker'
109 ex3 = 'aaaabbbcccdddeefffggggggzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz'
110 # answer should be a 0110 / b 0111 / c 010 / d 00 / e 1 : 111001100110101101011001100110111110110111
111 count_chars(ex1)
112
113 dex1 = count_and_q(ex1)
114 dex2 = count_and_q(ex2)
115 dex3 = count_and_q(ex3)
116
117 print dex1
118 #print dex2
119 print dex3
120
121 return 'huff_setup done!'
122
123def encode_decode(str):
124 a_string, a_dict = huffmanate(str)
125 decoded = dehuffmanate(a_string, a_dict)
126 print 'original %s' % str
127 print ' encoded %s' % a_string
128 print ' bitdict %s' % a_dict
129 print ' decoded %s' % decoded
130
131 print '\toriginal == decoded?', decoded == str
132 print
133 print
134 return decoded == str
135
136ex0 = 'eeedeedeeceeceedeedeebeeaeee'
137ex1 = 'abacabbac'
138ex2 = 'alskdjflwweltkjh;lkj;lwker'
139ex3 = 'aaaabbbcccdddeefffggggggzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz'
140
141encode_decode(ex0)
142encode_decode(ex1)
143encode_decode(ex2)
144encode_decode(ex3)