Python programming Huffman tree

I have homework on python language. the first attachment is how the huffman decoding working and the second one is description of the homework

ELEC-621 Information Theory and Coding, Spring 2018

Lab 2 – Huffman Coding

Huffman Tree:

• Finish the Python code for determining the Huffman Tree for the English alphabet. Your code
needs to work for any probability distribution. For example, your code should work for the
alphabet of another language too. The algorithm you need to implement is the same algorithm
in the tutorial of Lab 1. Letters have to be sorted in ascending order of probabilities. The two
least probable letters are combined into one tree where the two letters are the only leaf nodes,
and the parent node is a new symbol whose probability is the addition of the probabilities of the
two letters. The two letters are removed from the list of letters, and the new symbol is added to
the list making sure that the list is still sorted in ascending order of probabilities. This process is
repeated until there is only one symbol left in the list. This symbol is the root of the Huffman
tree.

• Update the list of letters with the space character. For example, the text “hello world” has one
space between letters “o” and “w”. You can find the frequency of the space character online.
The space character is more frequent than the letter of higher frequency, “e”.

# Ali Alshamali
## LAB1
class HuffmanTree(object):
def __init__(self, symbol=’*’, p=0, child0=None, child1=None):
self.symbol = symbol
self.p = p
self.child0 = []
self.child1 = []
if child0 is not None:
for child in child0:
self.add_child(child0)
if child1 is not None:
for child in child1:
self.add_child(child0)
def __repr__(self):
return self.symbol
def add_child0(self, node):
assert isinstance(node, HuffmanTree)
self.child0.append(node)
def add_child1(self, node):
assert isinstance(node, HuffmanTree)
self.child1.append(node)
# Need to finish the same process for all letters: c, d, …, z
a = HuffmanTree(symbol=’a’, p=8.167)
print ‘p(‘ + a.symbol + ‘) = ‘ + str(a.p)
b = HuffmanTree(symbol=’b’, p=1.492)
print ‘p(‘ + b.symbol + ‘) = ‘ + str(b.p)
c = HuffmanTree(symbol=’c’, p=2.782)
print ‘p(‘ + c.symbol + ‘) = ‘ + str(c.p)
d = HuffmanTree(symbol=’d’, p=4.253)
print ‘p(‘ + d.symbol + ‘) = ‘ + str(d.p)
e = HuffmanTree(symbol=’e’, p=12.702)
print ‘p(‘ + e.symbol + ‘) = ‘ + str(e.p)
f = HuffmanTree(symbol=’f’, p=2.228)
print ‘p(‘ + f.symbol + ‘) = ‘ + str(f.p)
g = HuffmanTree(symbol=’g’, p=2.015)
print ‘p(‘ + g.symbol + ‘) = ‘ + str(g.p)
h = HuffmanTree(symbol=’h’, p=6.094)
print ‘p(‘ + h.symbol + ‘) = ‘ + str(h.p)
i = HuffmanTree(symbol=’i’, p=6.966)
print ‘p(‘ + i.symbol + ‘) = ‘ + str(i.p)
j = HuffmanTree(symbol=’j’, p=0.153)
print ‘p(‘ + j.symbol + ‘) = ‘ + str(j.p)
k = HuffmanTree(symbol=’k’, p=0.772)
print ‘p(‘ + k.symbol + ‘) = ‘ + str(k.p)
l = HuffmanTree(symbol=’l’, p=4.025)
print ‘p(‘ + l.symbol + ‘) = ‘ + str(l.p)
m = HuffmanTree(symbol=’m’, p=2.406)
print ‘p(‘ + m.symbol + ‘) = ‘ + str(m.p)
n = HuffmanTree(symbol=’n’, p=6.749)
print ‘p(‘ + n.symbol + ‘) = ‘ + str(n.p)
o = HuffmanTree(symbol=’o’, p=7.507)
print ‘p(‘ + o.symbol + ‘) = ‘ + str(o.p)
p = HuffmanTree(symbol=’p’, p=1.929)
print ‘p(‘ + p.symbol + ‘) = ‘ + str(p.p)
q = HuffmanTree(symbol=’q’, p=0.095)
print ‘p(‘ + q.symbol + ‘) = ‘ + str(q.p)
r = HuffmanTree(symbol=’r’, p=5.987)
print ‘p(‘ + r.symbol + ‘) = ‘ + str(r.p)
s = HuffmanTree(symbol=’s’, p=6.327)
print ‘p(‘ + s.symbol + ‘) = ‘ + str(s.p)
t = HuffmanTree(symbol=’t’, p=9.056)
print ‘p(‘ + t.symbol + ‘) = ‘ + str(t.p)
u = HuffmanTree(symbol=’u’, p=2.758)
print ‘p(‘ + u.symbol + ‘) = ‘ + str(u.p)
v = HuffmanTree(symbol=’v’, p=0.978)
print ‘p(‘ + v.symbol + ‘) = ‘ + str(v.p)
w = HuffmanTree(symbol=’w’, p=2.360)
print ‘p(‘ + w.symbol + ‘) = ‘ + str(w.p)
x = HuffmanTree(symbol=’x’, p=0.150)
print ‘p(‘ + x.symbol + ‘) = ‘ + str(x.p)
y = HuffmanTree(symbol=’y’, p=1.974)
print ‘p(‘ + y.symbol + ‘) = ‘ + str(y.p)
z = HuffmanTree(symbol=’z’, p=0.074)
print ‘p(‘ + z.symbol + ‘) = ‘ + str(z.p)

# Need to include all letters in your tree below
MyTree = [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]
print MyTree
# Need to finish the funcition below that sorts the list MyTree in ascending order of probabilities.
def sort_mytree(tree=None):

if tree is None:
print tree
else:
tree=sorted(tree, key=lambda sort_data: sort_data.p)
return tree
# Don’t need to do anything here. The print below is to verify that your code sorts your tree correctly in ascending order of probabilities.
MyTree = sort_mytree(MyTree)
# place the code below:
# this is code is trying to do lab2
def buildTree(tree1) :
while len(tree1) > 1 :

for alpa in tree1:
alpa=2
p0=tree1[0].p
p1=tree1[1].p
leastTwo=p0+p1
node = HuffmanTree(symbol=’:*’, p=leastTwo)
print ‘p(‘ + node.symbol + ‘) = ‘ + str(node.p)
theRest = tree1[alpa:].p
tree1 = node.p + theRest
tree1 = sort_mytree(tree1)
return tree1
# place the code above

MyTree = buildTree(MyTree)
print MyTree