PYTHON 3.x Huffman Trees

This is what needs to be completed HuffmanHeap.py:

# Defines a data structure that allows Huffman codes to # be computed efficiently. # # A Huffman Heap is a queue to store HuffmanTree objects. # The word "heap" implies that the dequeue operation will always # remove and return the HuffmanTree object with the lowest frequency. class HuffmanHeap(object): def __init__(self, leafs): """  Purpose:  Creates a new HuffmanHeap object.  Pre-conditions:  leafs: a list of HuffmanTree leaf nodes.  Post-conditions:  The heap is created and initialized.  Return:  None  """  pass def enqueue(self, tree): """  Purpose:  Adds the tree to the Heap.  This is an O(1) operation.  Pre-conditions:  tree is a HuffmanTree object  Post-conditions:  the heap increases in size by 1  Return:  None  """  return None HuffmanTree.py:

# Defines the Huffman Tree data structure # # A Huffman tree-node has a character and a frequency. # some strings to avoid long lines later _INIT_ASSERT_MESSAGE_NONLEAF = 'Invalid Huffman tree construction attempted.' _GETCH_ASSERT_MESSAGE_NONLEAF = 'Method get_char() called on non-leaf node' class HuffmanTree(object): def __init__(self, freq=0, char=None, left=None, right=None): """  Purpose:  Initializes the HuffmanTree object.  To create a leaf node  aleaf = HuffmanTree(freq=10, char='A')  bleaf = HuffmanTree(freq=15, char='E')  To create an internal node:  node = HuffmanTree(left=aleaf,right=bleaf)   Pre-conditions:  :param freq: a positive integer  :param char: a character  :param left: another Huffman Tree  :param right: another HuffmanTree  """  self.__char = char self.left = left self.right = right if left is None and right is None: # leaf node: assign the frequency as given self.__freq = freq else: assert left is not None and right is not None, _INIT_ASSERT_MESSAGE_NONLEAF # non-leaf node: calculate the frequency from the given subtrees self.__freq = left.__freq + right.__freq def is_leaf(self): """  Purpose:  Check if the node is a leaf.  Simplifies some of the other methods with an abstraction.  Return:  True if the node is a leaf node  """  return self.left is None and self.right is None def get_freq(self): """  Purpose:  Return the frequency data stored in the node.  Return:  :return: the frequency  """  return self.__freq def get_char(self): """  Purpose:  Return the character stored at a leaf node.  Return:  :return: the character at a leaf node  """  assert self.is_leaf(), _GETCH_ASSERT_MESSAGE_NONLEAF return self.__char def display(self, level=0): """  Purpose:  For debugging, display the tree.  The structure of the tree is represented by indentation  No other real purpose.  Preconditions:  :param level: indentation amount for subtrees.  Return  :return: None  """  if self.is_leaf(): print(' '*level+'Leaf:', self.__char, self.__freq) else: print(' '*level+'Node:', self.__freq, 'Children:') self.left.display(level+1) self.right.display(level+1) def build_codec(self): """  Purpose:  Build a dictionary of char-code pairs from the Huffman tree.  Return:  :return: a dictionary with character as key, code as value  """  codes = {} def encoder(tree, code): if tree.is_leaf(): codes[tree.get_char()] = code else: encoder(tree.left, code+'0') encoder(tree.right, code+'1') if self.is_leaf(): codes[self.__char] = '0' else: encoder(self,'') return codes def __lt__(self, other): return self.__freq  
Encoder.py
 
import sys as sys import HuffmanTree as HT import HuffmanHeap as HH DEFAULT_OUTPUT_FILE = 'encoded.txt' def main(): """  Purpose:  Application to read and encode a file using Huffman codes.  Usage: python3 Encoder.py   Sends output to DEFAULT_OUTPUT_FILE  Return:  :return: None  """  if len(sys.argv) != 2: print('Usage: python3', sys.argv[0], '') print('-- sends output to', DEFAULT_OUTPUT_FILE, '-- ') return fname = sys.argv[1] lines = read_file(fname) freqs = count_characters(lines) codec = build_codec(freqs) coded = encode(lines, codec) write_file(DEFAULT_OUTPUT_FILE, coded) def read_file(fname): """  Purpose:  Read a file and return contents in a list of strings.  Preconditions:  :param fname: the name of a text file  Return:  :return: a list of strings, one string for each line  """  tfile = open(fname) lines = [l.rstrip() for l in tfile] tfile.close() return lines def write_file(fname, lines): """  Purpose:  Write the data in lines to the named file.  Warning: this will over-write any data in the named file!  Preconditions:  :param fname: the name of a text file  :param lines: a list of strings  Post-condition:  The named file is created or over-written.  Return:  :return: None  """  tfile = open(fname, 'w') for line in lines: tfile.write(line + ' ') tfile.close() def count_characters(contents): """  Purpose:  Count the characters in the contents.  Pre-conditions:  :param contents: a list of strings.  Return:  :return: a list of (character,frequency) tuples  """  freqs = dict() for line in contents: for char in line: if char in freqs: freqs[char] += 1 else: freqs[char] = 1 return list(freqs.items()) def build_codec(freq_list): """  Purpose:  Build a codec from the frequency list.  Pre-conditions:  :param freq_list: A list of (char,frequency) tuples.  Return:  :return: a dictionary mapping characters to codes  """  freq_list.sort(key=lambda p: p[1]) hq = HH.HuffmanHeap([HT.HuffmanTree(freq=f,char=c) \ for c,f in freq_list]) while len(hq) > 1: t1 = hq.dequeue() t2 = hq.dequeue() hq.enqueue(HT.HuffmanTree(left=t1, right=t2)) survivor = hq.dequeue() return survivor.build_codec() def encode(strings, codec): """  Purpose:  Use the codec to create the data to be sent to the output file.  Pre-conditions:  :param strings: A list of strings to encode.  :param codec: A dictionary containing character-code pairs  Return:  :return: a list of strings including:  the number of codes the number of coded lines,  the codes  the coded lines  """  output = [] output.append(str(len(codec)) + ' ' + str(len(strings))) for char in codec: output.append(codec[char] + ':' + "'" + char + "'") for s in strings: encoded = [] for char in s: encoded.append(codec[char]) output.append(''.join(encoded)) return output if __name__ == '__main__': main()
  Question 1 (17 points) Purpose: To implement an ADT to support efficient execution of a HuffmanTree encoder. Degree of Difficulty: Easy to Moderate Phoenix Wright, ace attorney, loves being lazy - erm, efficient. Phoenix is also short on money. He has heard of text compression, and thinks it might be a good idea to compress all his text files to save on valuable disk space (disk space is expensive for him!). Larry Butz, his useless IT friend, wrote most of the code for text compression using Huffman trees, but did not finish the job (surprising no one). On the Assignment 10 Moodle page, you'll find a program named Encoder.py. The program follows a simple design, and is well-documented. All the pieces should be familiar to you, as they are similar to discussion in class. The Encoder.py program imports two supporting ADTs Huf fmanTree.py Defines the HuffmanTree class Huf fmanHeap.py Defines the HuffmanHeap class. The HuffmanTree class was discussed in lecture, and its definition should be familiar. There is one change that you should note: the function build_codec() that builds the codec from a HuffmanTree object is now a method in the HuffmanTree class. The ADT HuffmanHeap, was also discussed in lecture, though the code was not given. A heap is a kind of queue that guarantees that the dequeue operation always removes and returns the smallest value in the queue (this is not the FIFO protoco). The Huffman Heap stores HuffmanTree objects, and has the following methods: ..init..(self, leafs): Creates a new HuffmanHeap object. enqueue(self, tree): Adds the given HuffmanTree to the heap