Skip to content

Instantly share code, notes, and snippets.

@uolter
Created April 22, 2013 13:33
Show Gist options
  • Save uolter/5434901 to your computer and use it in GitHub Desktop.
Save uolter/5434901 to your computer and use it in GitHub Desktop.
Huffman code with python
from collections import Counter
import heapq
class Node(object):
def __init__(self, pairs, frequency):
self.pairs = pairs
self.frequency = frequency
def __repr__(self):
return repr(self.pairs) + ", " + repr(self.frequency)
def merge(self, other):
total_frequency = self.frequency + other.frequency
for p in self.pairs:
p[1] = "1" + p[1]
for p in other.pairs:
p[1] = "0" + p[1]
new_pairs = self.pairs + other.pairs
return Node(new_pairs, total_frequency)
def __lt__(self, other):
return self.frequency < other.frequency
def huffman_codes(s):
table = [Node([[ch, '']], freq) for ch, freq in Counter(s).items()]
heapq.heapify(table)
while len(table) > 1:
first_node = heapq.heappop(table)
second_node = heapq.heappop(table)
new_node = first_node.merge(second_node)
heapq.heappush(table, new_node)
return dict(table[0].pairs)
print(huffman_codes('yashaswita'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment