Python Challenges: Get a dictionary mapping keys to huffman codes for a frequency table mapping keys to frequencies
Python Challenges - 1: Exercise-58 with Solution
From Wikipedia,
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".
Write a Python program to get a dictionary mapping keys to huffman codes for a frequency table mapping keys to frequencies.
Sample Solution:
Python Code:
def huffman(freqtable):
# Ref.: https://bit.ly/3cWJD22
from collections import defaultdict
from heapq import heappush, heappop, heapify
# mapping of letters to codes
code = defaultdict(list)
# Using a heap makes it easy to pull items with lowest frequency.
# Items in the heap are tuples containing a list of letters and the
# combined frequencies of the letters in the list.
heap = [ ( freq, [ ltr ] ) for ltr,freq in freqtable.items() ]
heapify(heap)
# Reduce the heap to a single item by combining the two items
# with the lowest frequencies.
while len(heap) > 1:
freq0,letters0 = heappop(heap)
for ltr in letters0:
code[ltr].insert(0,'0')
freq1,letters1 = heappop(heap)
for ltr in letters1:
code[ltr].insert(0,'1')
heappush(heap, ( freq0+freq1, letters0+letters1))
for k,v in code.items():
code[k] = ''.join(v)
return code
freqtable = dict(a=45, b=13, c=12, d=16, e=9, f=5)
print(sorted(huffman(freqtable).items()))
Sample Output:
[('a', '0'), ('b', '101'), ('c', '100'), ('d', '111'), ('e', '1101'), ('f', '1100')]
Flowchart:
Python Code Editor:
Contribute your code and comments through Disqus.
Previous: Write a Python program to generate list with 'width'-bit gray code.
Next: Write a Python program to compute the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://198.211.115.131/python-exercises/challenges/1/python-challenges-1-exercise-58.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics