Huffman Compression (Python) Given a dict with its keys being symbols from a tex

Question

Huffman Compression (Python)

Given a dict with its keys being symbols from a text and the values being how often the symbol appears, how do I create a codebook assigning a binary character to each symbol without using a tree? (i.e., all within one method without importing any new collections)

Below is the starter method. The arg "symbol_probs" is the aforementioned dict.

def generate_codebook(symbol_probs):

# initialize codebook with the same symbols as symbol_probs

codebook = {}
for symbol in symbol_probs.keys():
codebook[symbol] = ""

# TODO: use the probabilities is symbol_probs to generate a
# code for each character.

return codebook

def generate_codebook(symbol_probs):

# initialize codebook with the same symbols as symbol_probs

codebook = {}
for symbol in symbol_probs.keys():
codebook[symbol] = ""

# TODO: use the probabilities is symbol_probs to generate a
# code for each character.

return codebook

Explanation / Answer

import queue class HuffmanNode(object): def __init__(self, left=None, right=None, root=None): self.left = left self.right = right self.root = root # Why? Not needed for anything. def children(self): return((self.left, self.right)) freq = [ (8.167, 'a'), (1.492, 'b'), (2.782, 'c'), (4.253, 'd'), (12.702, 'e'),(2.228, 'f'), (2.015, 'g'), (6.094, 'h'), (6.966, 'i'), (0.153, 'j'), (0.747, 'k'), (4.025, 'l'), (2.406, 'm'), (6.749, 'n'), (7.507, 'o'), (1.929, 'p'), (0.095, 'q'), (5.987, 'r'), (6.327, 's'), (9.056, 't'), (2.758, 'u'), (1.037, 'v'), (2.365, 'w'), (0.150, 'x'), (1.974, 'y'), (0.074, 'z') ] def create_tree(frequencies): p = queue.PriorityQueue() for value in frequencies: # 1. Create a leaf node for each symbol p.put(value) # and add it to the priority queue while p.qsize() > 1: # 2. While there is more than one node l, r = p.get(), p.get() # 2a. remove two highest nodes node = HuffmanNode(l, r) # 2b. create internal node with children p.put((l[0]+r[0], node)) # 2c. add new node to queue return p.get() # 3. tree is complete - return root node node = create_tree(freq) print(node) # Recursively walk the tree down to the leaves, # assigning a code value to each symbol def walk_tree(node, prefix="", code={}): return(code) code = walk_tree(node)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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