3
\$\begingroup\$
"""
### General Idea:

Given a set of n character set C.

1. Begin with a set of |C| leaves.
2. Repeatedly using **min-priority** queue `Q`, keyed on frequencies,
   identify the two least-frequent objects to merge together.
3. Until all be merged.

### Input

List of tuple containing frequency and character.

### Output

A tree T, called Huffman tree.
"""

import heapq


class Node(object):
    def __init__(self, key, freq, left=None, right=None):
        self.key = key
        self.freq = freq
        self.left = left
        self.right = right

    def __cmp__(self, other):
        return cmp(self.freq, other.freq)

    def __str__(self):
        return "({0}, {1})".format(self.key, self.freq)

    def __repr__(self):
        return self.__str__()

def encode(rel_freq):
    nodes = create_leaf_nodes(rel_freq)
    heapq.heapify(nodes)
    root = build_encode_tree(nodes)
    #print_tree(root)
    return root

def create_leaf_nodes(rel_freq):
    return map(lambda (freq, key): Node(key, freq), rel_freq)

def merge(n1, n2):
    freq = n1.freq + n2.freq
    if n1.freq <= n2.freq:
        return Node(n1.key + n2.key, freq, n1, n2)
    return Node(n2.key + n1.key, freq, n2, n1)

def build_encode_tree(nodes):
    root = nodes[0]
    while len(nodes) > 1:
        n1 = heapq.heappop(nodes)
        n2 = heapq.heappop(nodes)
        root = merge(n1, n2)
        heapq.heappush(nodes, root)
    return root

# ---------------- Helpers --------------------------
def print_tree(root):
    for nodes in level_order(root):
        for node in nodes:
            print node,
        print

def level_order(node):
  """Given Binary Tree gives list nodes in each level."""
  current_level = [node]
  while current_level:
    yield current_level
    next_level = []
    for node in current_level:
      if node.left:
        next_level.append(node.left)
      if node.right:
        next_level.append(node.right)
    current_level = next_level

import unittest


class TestHuffmanEncoding(unittest.TestCase):
    def test_single_char(self):
        rel_freq = [(24, 'A')]
        actual = str(encode(rel_freq))
        self.assertEqual(actual, "(A, 24)")

    def test_valid_encoding(self):
        #expected = [('A', '0'), ('B', '100'), ('C', '101'), ('D', '110'), ('E', '111')]
        rel_freq = [(24, 'A'), (12, 'B'), (10, 'C'), (8, 'D'), (8, 'E')]
        expected = "(AEDCB, 62)"
        actual = str(encode(rel_freq))
        self.assertEqual(actual, expected)

        rel_freq = [(45, 'A'), (13, 'B'), (12, 'C'), (16, 'D'), (9, 'E'), (5, 'F')]
        expected = "(ACBFED, 100)"
        actual = str(encode(rel_freq))
        self.assertEqual(actual, expected)

if __name__ == '__main__':
    unittest.main()

Note:

The code do generate the Huffman tree but I am more interested in finding the encoding of each character, the basic approach what I think is traversing each path from root to leaf such that moving left adds 0 to the path and moving right adds 1. Hopefully I would post the solution soon in another review.

\$\endgroup\$
4
\$\begingroup\$

Merging is a thing a node and only a node does, using that function on a non-node is meaningless so include it in the node class:

class Node:
    ...
    def merge(self, other_node):

Now the person that uses your code knows that merge works for nodes and nothing else and the code has more structure.

\$\endgroup\$
  • \$\begingroup\$ Hmm, I am confused with the concept of parametric polymerphism, when to apply this concept? \$\endgroup\$ – CodeYogi Oct 29 '15 at 14:39
  • \$\begingroup\$ @CodeYogi i do not mean enforcing type safety, just hinting at the way to use it. \$\endgroup\$ – Caridorc Oct 29 '15 at 14:40
  • \$\begingroup\$ Cool! it seems that I am learning alot, now my code seems to have lot less comments :), but I am still confused about the __repr__ stuff, you gave me some comment in my previous post by it was not clear. \$\endgroup\$ – CodeYogi Oct 29 '15 at 15:12
  • \$\begingroup\$ If what if I want to merge objects which behaves like node, why bound my method to just one type? \$\endgroup\$ – CodeYogi Dec 17 '15 at 8:56
  • \$\begingroup\$ @CodeYogi You are not bounding yourself \$\endgroup\$ – Caridorc Dec 17 '15 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.