Demo entry 2843164

Python Implementation

   

Submitted by anonymous on Oct 19, 2015 at 08:30
Language: Python 3. Code size: 3.4 kB.

from queue import PriorityQueue


class Node():
    '''
    A Node with a symbol, frequency, left child, and right child.
    '''
    def __init__(self, symbol=None, frequency=None, left=None, right=None):
        self.symbol = symbol
        self.frequency = frequency
        self.left = left
        self.right = right
    
    def __str__(self):
        '''
        Return the string reprsentation of the Node.
        '''    
        return "Node(" + (self.symbol).__repr__() + ", " + str(self.frequency) + ", " + str(self.left) + ", " + str(self.right) + ")"

    def __repr__(self):
        '''
        Return a reprsentation of the Node (the string representation is returned).
        '''
        return self.__str__()

    def __gt__(self, other):
        '''
        Return True iff this Node is greater than other.
        Criteria compared: frequency.
        '''
        if (self.frequency is None):
            return False
        if (other.frequency is None):
            return True
        return self.frequency > other.frequency


def tree_to_list(tree):
    '''
    Given the tree representation of the prefix code,
    return a list containing tuples of symbols and their corresponding code word.

    >>> tree_to_list(Node(None, None, Node(None, None, Node('A', 1, None, None), Node('B', 2, None, None)), Node('C', 3, None, None)))
    [('A', '00'), ('B', '01'), ('C', '1')]
    '''
    def _tree_to_list(tree, word):
        if tree is None:
            return []
        if tree.symbol is None:
            return _tree_to_list(tree.left, word + "0") + _tree_to_list(tree.right, word + "1")
        return [(tree.symbol, word)] 
    return _tree_to_list(tree, "")


def shannon_fano(nodes):
    '''
    Given a list of nodes,
    return Shannon-Fano encoding tree representation.
    '''
    def _shannon_fano(nodes):
        length = len(nodes)
        if length == 1:
            return nodes[0]
        if length == 2:
            return Node(None, None, nodes[0], nodes[1])

        # Figure out where to split the list.    
        total = 0
        for i in range(length):
            total += nodes[i].frequency
        second_half_total = 0
        index = length

        while (index >= 0) and (second_half_total <= (total - second_half_total)):
            index -= 1
            second_half_total += nodes[index].frequency

        diff1 = second_half_total - (total - second_half_total)
        diff2 = abs(diff1 - (2 * nodes[index].frequency))
        if (diff2 < diff1):
            index += 1
        
        left = _shannon_fano(nodes[0:index])
        right = _shannon_fano(nodes[index:])

        return Node(None, None, left, right)

    nodes.sort()
    nodes.reverse()
    if len(nodes) == 1:
        return Node(None, None, nodes[0], None)
    return _shannon_fano(nodes)


def huffman(nodes):
    '''
    Given a list of nodes,
    return the Huffman encoding tree representation. 
    '''
    trees = PriorityQueue() # elements: (total_frequency, tree)
    for node in nodes:
        trees.put((node.frequency, node))
        
    while (trees.qsize() > 1):
        min1 = trees.get()
        min2 = trees.get()
        trees.put((min1[0] + min2[0], Node(None, None, min1[1], min2[1])))
        
    return trees.get()[1]

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).