fork download 
  1. from collections import Counter
  2. import heapq
  3.  
  4. class Node:
  5.     def __init__(self, value):
  6.         self.children = []
  7.         self.value = value
  8.     def __lt__(self, other):
  9.         return self.value < other.value
  10.     def branch_map(self):
  11.         """
  12.             returns a dictionary that describes the path from the root node to each leaf node.
  13.             for example, if the root's second child's first child's value is "X", then there will be a pair `10: "X"`
  14.         """
  15.         ret = {"": self.value}
  16.         for idx, child in enumerate(self.children):
  17.             for k,v in child.branch_map().iteritems():
  18.                 ret[str(idx)+k] = v
  19.         return ret
  20.  
  21. def frequency(data):
  22.     c = Counter(data)
  23.     return {char: count/float(len(data)) for char, count in c.iteritems()}
  24.  
  25. def gen_huffman_tree(data):
  26.     nodes = [Node((freq, value)) for value, freq in frequency(data).iteritems()]
  27.     heapq.heapify(nodes)
  28.     while len(nodes) > 1:
  29.         a = heapq.heappop(nodes)
  30.         b = heapq.heappop(nodes)
  31.         combined = Node((a.value[0]+b.value[0], "*"))
  32.         combined.children.extend([a,b])
  33.         heapq.heappush(nodes, combined)
  34.     return nodes[0]
  35.  
  36. def gen_huffman_coding(data):
  37.     tree = gen_huffman_tree(data)
  38.     codes = {}
  39.     for code, (freq, char) in tree.branch_map().iteritems():
  40.         codes[char] = code
  41.     return codes
  42.  
  43. data = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."
  44.  
  45. table = gen_huffman_coding(data)
  46. for char in table:
  47.     print char, table[char]
Success #stdin #stdout 0.02s 9128KB
comments (?)
stdin 
Standard input is empty
stdout 
  110
* 00000
, 0101111
. 000000
E 000001111
D 000001110
L 00000100
U 00000101
a 1000
c 10110
b 0000110
e 1111
d 11100
g 0101100
f 0000111
i 001
h 00000110
m 10111
l 0001
o 1001
n 0110
q 000010
p 01010
s 11101
r 0100
u 0111
t 1010
v 0101101
x 0101110
https://ideone.com/vs4TiM
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!