G2A Many GEOs
SHARE
TWEET

ugly huffman code

a guest Mar 31st, 2020 78 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.  
  48.     def add_to_heap(self,node):
  49.         self.heap.append(node)
  50.         self.added_last(len(self.heap)-1)
  51.  
  52.     def added_last(self,child):
  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]
  59.             self.added_last(parent)
  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.  
  101.             self.heap.add_to_heap(top)
  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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top