“””Write a program to implement Huffman Encoding using a greedy strategy”””
import heapq
def huffman_encoding(text):
freq = {}
for ch in text:
freq[ch] = freq.get(ch, 0) + 1
heap = [[weight, [ch, “”]] for ch, weight in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = “0” + pair[1]
for pair in hi[1:]:
pair[1] = “1” + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
huff_codes = dict(sorted(heap[0][1:], key=lambda p: (len(p[-1]), p)))
encoded_text = “”.join(huff_codes[ch] for ch in text)
return huff_codes, encoded_text
def huffman_decoding(encoded_text, codes):
reverse_codes = {v: k for k, v in codes.items()}
decoded_text = “”
current = “”
for bit in encoded_text:
current += bit
if current in reverse_codes:
decoded_text += reverse_codes[current]
current = “”
return decoded_text
text = “huffman encoding”
codes, encoded = huffman_encoding(text)
decoded = huffman_decoding(encoded, codes)
print(“Original Text:”, text)
print(“Character Codes:”, codes)
print(“Encoded Text:”, encoded)
print(“Decoded Text:”, decoded)