How to encode a String in Huffman Coding Using Python

In this tutorial, we are going to see how to encode a string in Huffman coding in Python.

Encode a String in Huffman Coding:

In order to encode a string first, we need to build a min-heap tree So, we are using a Module called heapq in Python. This method is used to build a min-heap tree.

Defaultdict is used to generate the frequency for each character in the string. It is available under the collections packages.

Now we are using a user-defined method called encode and we are passing frequency as the parameter.

Then we are using a while loop to find the low and high values in the heap that we have already declared.

Inside the loop, we are using two separate for loops which are used to assign the values as ‘0’ and ‘1’ for the left and the right nodes which are here referred to as the low and high.

Finally, we use the sorted function to sort the obtained heap It is noted that in the code we use the lambda keyword which is used to mention an unnamed function as for the key value.

Now we need to give the input string for encoding.

In which the frequency for each character in the string is automatically generated by the defaultdict as we mentioned before.

We use the for loop here to store each unique frequency value of the characters.

Now we call the encode function to pass each of the frequency of the characters present in the string to the user-defined function encode and it is returned to the dictionary huff.

Finally, we print the encoded values with the help of the for a loop.

Python program:  Hoffman coding in Python

import heapq
from collections import defaultdict
def encode(frequency):
    heap = [[weight, [symbol, '']] for symbol, weight in frequency.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        low = heapq.heappop(heap)

        high = heapq.heappop(heap)

        for value in low[1:]:

            value[1] = '0' + value[1]

        for value in high[1:]:

            value[1] = '1' +value[1]

        heapq.heappush(heap, [low[0] + high[0]] + low[1:] + high[1:])

    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))


string=input("Enter the string to be encoded:")

frequency = defaultdict(int)

for character in string:

    frequency[character] += 1

huff = encode(frequency)

print("character".ljust(10) + "Weight".ljust(10) + "Huffman Code")

for i in huff:

    print(i[0].ljust(10) + str(frequency[i[0]]).ljust(10) + i[1])

 

Output:

Enter the string to be encoded:maran
character Weight Huffman Code
 a           2        11
 m           1        00
 n           1        01
 r           1        10

You may also read:

• Python Program to Add all the digits of a given number