﻿

# ugly huffman code

a guest
Mar 31st, 2020
83
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. from random import randint
3.
4. from copy import copy
5.
6. class huf_tree_node:
7.     def __init__(self,data=None,freq=None,left=None,right=None):
8.         self.data=data
9.         self.freq=freq
10.         self.left=left
11.         self.right=right
12.
13.     def other_name(self, level=0):
14.
15.         print('\t' * level + repr(self.data) + "  " + repr(self.freq))
16.         if self.left is not None:
17.             self.left.other_name(level + 1)
18.         if self.right is not None:
19.             self.right.other_name(level + 1)
20.     """def __repr__(self, level=0):
21.        ret = "\t" * level + repr(self.data) + "\n"
22.
23.        ret += self.left.__repr__(level + 1)
24.        ret += self.right.__repr__(level + 1)
25.        return ret
26.        """
27. class huf_min_heap:
28.     def heapify(self,root):
29.         left = 2 * root + 1
30.         right = 2 * root + 2
31.         lowest = root
32.
33.         if left < len(self.heap) and self.heap[left].freq < self.heap[lowest].freq:
34.             lowest = left
35.
36.         if right < len(self.heap) and self.heap[right].freq < self.heap[lowest].freq:
37.             lowest = right
38.
39.
40.         if lowest != root:
41.             self.heap[root],self.heap[lowest]=self.heap[lowest],self.heap[root]
42.             self.heapify(lowest)
43.     def build_heap(self):
44.
45.         for i in range(len(self.heap) // 2 , -1 ,-1):
46.             self.heapify(i)
47.
49.         self.heap.append(node)
51.
53.         if child==0:
54.             return
55.         parent = (child - 1) // 2
56.
57.         if self.heap[parent].freq > self.heap[child].freq:
58.             self.heap[child], self.heap[parent] = self.heap[parent], self.heap[child]
60.
61.     def get_min(self):
62.         res=self.heap[0]
63.         self.heap[0]=self.heap[len(self.heap)-1]
64.         del self.heap[len(self.heap)-1]
65.         self.heapify(0)
66.         return res
67.
68.
69.     def __init__(self,arr,key,data):
70.         self.heap=[]
71.
72.         for i in range (len(arr)):
73.             tmp=huf_tree_node(arr[i][data],arr[i][key])
74.             self.heap.append(tmp)
75.
76.         self.build_heap()
77.
78.     def print_heap(self):
79.         print()
80.         for i in range (len(self.heap)):
81.             print(self.heap[i].data,self.heap[i].freq)
82.         print()
83.
84. class huffman_tree:
85.     def __init__(self):
86.         self.root=None
87.
88.     def create_tree(self,arr,key=0,data=1):
89.         self.arr=arr
90.         tmp=copy(arr)
91.         self.heap=huf_min_heap(tmp,key,data)
92.
93.         #self.heap.print_heap()
94.
95.         while len(self.heap.heap) > 1:
96.             left=self.heap.get_min()
97.             right=self.heap.get_min()
98.
99.             top = huf_tree_node(None,left.freq+right.freq,left,right)
100.
102.
103.             #self.heap.print_heap()
104.
105.         self.root=top
106.
107.
108.     def print_tree(self):
109.         def _print_tree(root,):
110.             if root is None:
111.                 return
112.             print(root.freq,root.data)
113.
114.             _print_tree(root.left)
115.
116.             _print_tree(root.right)
117.
118.         _print_tree(self.root)
119.
120.
121.
122.     def get_code(self):
123.         def printArr(arr,n):
124.             for i in range(n):
125.                 print(arr[i],end="")
126.             print()
127.         def printCode(arr,n):
128.             res=''
129.             for i in range(n):
130.                 res+=str(arr[i])
131.             return res
132.         def _get_code(root,res,i,code):
133.             #print(i)
134.             if root.left is not None:
135.                 res[i]=0
136.                 _get_code(root.left,res,i+1,code)
137.             if root.right is not None:
138.                 res[i]=1
139.                 _get_code(root.right,res,i+1,code)
140.             if root.right is None and root.left is None:
141.                 #print(root.data,end=" ")
142.                 #printArr(res, i)
143.                 code[self.k][0]=root.data
144.                 code[self.k][1]=printCode(res,i)
145.                 self.k += 1
146.
147.         #code_table = [[None,None]]*len(self.arr)
148.         code_table=[]
149.         for i in range(len(self.arr)):
150.             code_table.append([None,None])
151.
152.         #print(code_table)
153.         res=[None]*len(self.arr)
154.
155.         self.k=0
156.         _get_code(self.root,res,0,code_table)
157.         del self.k
158.         #print(code_table)
159.         return code_table
160.
161.     def other_name(self, level=0):
162.         self.root.other_name()
163.
164. def upperCaseAlphabet(n):
165.     return chr(65+n)
166.
167. n=10
168. arr=[]
169.
170. for i in range(n):
171.     arr.append([randint(10,100),upperCaseAlphabet(i)])
172.
173. #arr=[[50,'A'],[25,'B'],[75,'C'],[100,'D'],[25,'E'],[5,'F'],[50,'G'],[20,'H']]
174. print(arr)
175.
176. tree=huffman_tree()
177. tree.create_tree(arr,0,1)
178.
179. """print("\n\n\n\n")
180. tree.print_tree()
181. print("\n\n\n\n")"""
182. code=tree.get_code()
183. print("\n",code)
184.
185. #tree.other_name()
RAW Paste Data