Python Challenges: Get a dictionary mapping keys to huffman codes for a frequency table mapping keys to frequencies

Last update on December 21 2024 07:49:50 (UTC/GMT +8 hours)

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.