হাফম্যান কোডিং

import heapq
import itertools
from collections import Counter

class Node:
    __slots__ = ("freq", "char", "left", "right", "order")
    def __init__(self, freq, char=None, left=None, right=None, order=0):
        self.freq = freq
        self.char = char       # leaf হলে ক্যারেক্টার, অভ্যন্তরীণ নোড হলে None
        self.left = left
        self.right = right
        self.order = order     # heapq-তে টাই ভাঙার জন্য (Node তুলনাযোগ্য করতে)

    def __lt__(self, other):
        if self.freq != other.freq:
            return self.freq < other.freq
        return self.order < other.order

def build_huffman_tree(freqs):
    counter = itertools.count()
    heap = [Node(f, ch, order=next(counter)) for ch, f in freqs.items()]
    heapq.heapify(heap)          # সত্যিকারের min-heap তৈরি
    if len(heap) == 1:
        only = heap[0]
        return Node(only.freq, left=only, right=None, order=next(counter))
    while len(heap) > 1:
        a = heapq.heappop(heap)  # সবচেয়ে কম ফ্রিকোয়েন্সির নোড
        b = heapq.heappop(heap)  # দ্বিতীয় সবচেয়ে কম
        merged = Node(a.freq + b.freq, left=a, right=b, order=next(counter))
        heapq.heappush(heap, merged)
    return heap[0]

def build_codes(node, prefix="", codes=None):
    if codes is None:
        codes = {}
    if node is None:
        return codes
    if node.char is not None:
        codes[node.char] = prefix if prefix else "0"
        return codes
    build_codes(node.left, prefix + "0", codes)
    build_codes(node.right, prefix + "1", codes)
    return codes

def is_prefix_free(codes):
    # প্রতিটি জোড়া কোডের উপর সরাসরি চেক -- কোনোটি অন্যটির প্রিফিক্স কি না
    items = list(codes.values())
    for i in range(len(items)):
        for j in range(len(items)):
            if i != j and items[j].startswith(items[i]):
                return False
    return True

def encode(text, codes):
    return "".join(codes[ch] for ch in text)

def decode(bits, root):
    result = []
    node = root
    for b in bits:
        node = node.left if b == "0" else node.right
        if node.char is not None:
            result.append(node.char)
            node = root
    return "".join(result)

text = "abracadabra_huffman_coding_example"
freqs = Counter(text)
tree = build_huffman_tree(freqs)
codes = build_codes(tree)

print("ফ্রিকোয়েন্সি:", dict(freqs))
print("হাফম্যান কোড:", codes)

assert is_prefix_free(codes), "কোডগুলো প্রিফিক্স-ফ্রি নয়!"
print("\nপ্রিফিক্স-ফ্রি চেক পাস করেছে (সব কোড-জোড়া পরীক্ষা করে)")

encoded = encode(text, codes)
decoded = decode(encoded, tree)
assert decoded == text, "রাউন্ড-ট্রিপ ব্যর্থ!"
print("এনকোড -> ডিকোড রাউন্ড-ট্রিপ সফল, মূল স্ট্রিং হুবহু ফিরে এসেছে:", decoded == text)

original_bits = len(text) * 8
compressed_bits = len(encoded)
print(f"\nমূল আকার (৮ বিট/ক্যারেক্টার ধরে): {original_bits} বিট")
print(f"হাফম্যান-এনকোডেড আকার: {compressed_bits} বিট")
print(f"সংকোচনের অনুপাত: {compressed_bits / original_bits:.2f}x আসল আকারের")