Appreciate a well commented working algorithm in PYTHON for the following proble

Question

Appreciate a well commented working algorithm in PYTHON for the following problem. Please, no pseudocode.

Write a working program in python to implement the Huffman coding algorithm. For details on Huffman encoding, please see section 5.2 in this book http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf Remember that the decoding could be ambiguous, so to avoid this problem, we have to use the prefix-free property- no codeword can be a prefix of another codeword.

Using the text document below, you have to encode the document in an optimal binary code. The program

should input a text file

and output the Huffman code for each character

the total length of the encoding

and the encoded text

Ex: If the input is "mississippi", the Huffman code will be:
s - 0
p - 100
m - 101
i - 11

The total length of coding will be: 1x4 + 3x2 + 3x1 + 2x4 = 21

The encoded string is: 101110011001110010011

You have to test your code on "mississippi", and then show your output on the following input file

Input file is given below:

The Bellman looked uffish, and wrinkled his brow.

   "If only you'd spoken before!

It's excessively awkward to mention it now,

   With the Snark, so to speak, at the door!

"We should all of us grieve, as you well may believe,

   If you never were met with again—

But surely, my man, when the voyage began,

   You might have suggested it then?

"It's excessively awkward to mention it now—

   As I think I've already remarked."

And the man they called "Hi!" replied, with a sigh,

   "I informed you the day we embarked.

"You may charge me with murder—or want of sense—

   (We are all of us weak at times):

But the slightest approach to a false pretence

   Was never among my crimes!

"I said it in Hebrew—I said it in Dutch—

   I said it in German and Greek:

But I wholly forgot (and it vexes me much)

   That English is what you speak!"

Explanation / Answer

class InvalidTree(Exception): pass class BinaryTree(object): def __init__(self, root=None, left=None, right=None, leaf=False, **kwargs): """ Basic binary tree (with insertion, no deletion). """ self.root = root self.parent = None self._left = None self._right = None if not leaf: self.left = left self.right = right else: if left or right: raise InvalidTree("Leaves have no children!") # use kwargs to store additional data on the root node for k, v in kwargs.iteritems(): setattr(self, k, v) def __iter__(self): """ Does *in-order* iteration. """ if self.left: for node in self.left: yield node yield self if self.right: for node in self.right: yield node def __eq__(self, other): return self.root == other def __nonzero__(self): return self.root is not None def __repr__(self): return "".format(self) def __str__(self): return str(self.root or "Empty") def __int__(self): return int(self.root) def _insert(self, side, value): """ This is just a convenient way to not have to write both an insert_left and insert_right function that do the same thing. """ b_tree_value = BinaryTree(value, leaf=True) return self._attach(side, b_tree_value) def _attach(self, side, tree): current_value = getattr(self, side) if not current_value: setattr(self, side, tree) else: setattr(tree, side, current_value) setattr(self, side, tree) current_value.parent = tree tree.parent = self @property def height(self): if not self: return 0 elif not self.left and not self.right: return 1 else: return 1 + max(getattr(self.left, "height", 0), getattr(self.right, "height", 0)) @property def left(self): return self._left @left.setter def left(self, value): return self._insert("_left", value) @property def right(self): return self._right @right.setter def right(self, value): return self._insert("_right", value) @property def leaves(self): return [node for node in self if not node.left and not node.right] def iter_in_order(self): """ Does *in-order* iteration. """ return iter(self) def iter_pre_order(self): yield self if self.left: for node in self.left.iter_pre_order(): yield node if self.right: for node in self.right.iter_pre_order(): yield node def iter_post_order(self): if self.left: for node in self.left.iter_post_order(): yield node if self.right: for node in self.right.iter_post_order(): yield node yield self def attach_left(self, tree): """ Attach an existing tree to a node. """ return self._attach("_left", tree) def attach_right(self, tree): return self._attach("_right", tree) def count(text, sort=False, reverse=False): counted = ((letter, text.count(letter)) for letter in set(text)) if sort: counted = sorted(counted, key=itemgetter(1), reverse=reverse) return counted def get_huffman_tree(text, do_count=False): """ O(n) Huffman coding implementation using two (de)queues. (Direct translation from algorithm to Python code.) """ if do_count: text = count(text, sort=True) # construct a deque containing leaves out of the frequencies returned by # count. store the letter in an attr of each node initial_weights = deque([BinaryTree(l[1], leaf=True, letter=l[0]) for l in text]) combined_weights = deque() while len(initial_weights) + len(combined_weights) > 1: least_two_nodes = [] # (for loop over range(2) = do this twice) for _ in range(2): if not initial_weights or not combined_weights: least_two_nodes.append( (initial_weights or combined_weights).popleft()) elif initial_weights[0].root

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.