w3resource

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 Flowchart: Get a dictionary mapping keys to huffman codes for a frequency table mapping keys to frequencies.

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.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

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