গ্রিডি অ্যালগরিদম৮ মিনিট পড়া

হাফম্যান এনকোডিং (Huffman Encoding)

যে অক্ষরগুলো আপনি সবচেয়ে বেশি ব্যবহার করেন সেগুলোকে ছোট কোড দিন — ফাইলে জায়গা সাশ্রয় করুন

build tree:\(O(n \log n)\)space:\(O(n)\)optimality:প্রমাণিত এবং নিখুঁত প্রিফিক্স-ফ্রি (prefix-free) কোড

মোর্স কোড বা মোর্স সংকেতে, E অক্ষরটিকে একটি মাত্র ডট (·) দিয়ে প্রকাশ করা হয় কারণ ইংরেজি বর্ণমালার এটি সবচেয়ে বেশি ব্যবহৃত হয়। অন্যদিকে, Z কে ড্যাশ-ড্যাশ-ডট-ডট (−−··) দিয়ে প্রকাশ করা হয় কারণ এটি খুব কম ব্যবহৃত হয়। ঘন ঘন ব্যবহৃত অক্ষরগুলো ছোট কোড পায়; আর দুর্লভ অক্ষরগুলো পায় লম্বা কোড। এতে প্রতিটি অক্ষরই নির্ভুলভাবে চেনা যায়।

হাফম্যান এনকোডিং (Huffman encoding) এই একই ধারণার ওপর ভিত্তি করে তৈরি, যা গাণিতিকভাবে নিখুঁত। এটি প্রতিটি অক্ষরকে এমনভাবে বাইনারি কোড প্রদান করে যাতে একটি বার্তার মোট ব্যবহার হওয়া বিটের সংখ্যা সর্বনিম্ন হয় — এবং এটি এই নির্ভুলতা গাণিতিকভাবে নিশ্চিত করে।

প্রিফিক্স-ফ্রি কোড (Prefix-Free Codes)

এর মূল শর্তটি হলো: কোনো কোডওয়ার্ড অন্য কোনো কোডওয়ার্ডের প্রিফিক্স বা শুরু হতে পারবে না। যেমন যদি A-র কোড হয় ০১, তবে অন্য কোনো অক্ষর ০১ দিয়ে শুরু হতে পারবে না। এটি আমাদের ডিলিমিটার বা স্পেস ছাড়াই বিটের স্ট্রীম থেকে নির্ভুলভাবে অক্ষরগুলো পড়তে সাহায্য করে — যখনই আপনি একটি সম্পূর্ণ কোড হুবহু পাবেন, তখনই বুঝবেন যে অক্ষরটি শেষ হয়েছে। এতে ছোট কোডকে লম্বা কোডের শুরু বলে ভুল হওয়ার কোনো সম্ভাবনা থাকে না।

প্রতিটি প্রিফিক্স-ফ্রি কোড একটি পূর্ণ বাইনারি ট্রি (full binary tree)-র সাথে সাদৃশ্যপূর্ণ যেখানে প্রতিটি পাতা বা লিফ (leaf) হলো একটি অক্ষর। রুট থেকে পাতার পথটিই হলো সেই অক্ষরের কোডওয়ার্ড (বাম = ০, ডান = ১)। এনকোড করার খরচ হলো (অক্ষরের ফ্রিকোয়েন্সি × পাতার গভীরতা) এর সমষ্টি।

গ্রিডি অ্যালগরিদম (The Greedy Algorithm)

এর মূল ধারণাটি হলো: একটি নিখুঁত ট্রিতে, সবচেয়ে দুর্লভ বা কম ব্যবহৃত দুটি অক্ষর গাছের সবচেয়ে গভীর স্তরে এবং একে অপরের ভাই (siblings) হিসেবে থাকে। যদি তারা না থাকত, তবে আপনি সেগুলোকে অন্য যেকোনো গভীর পাতার সাথে বদল করে খরচ আরও কমাতে বা সমান রাখতে পারতেন।

এটি নিচে থেকে উপরে (bottom-up) ট্রি তৈরির একটি চমৎকার পদ্ধতি প্রদান করে:

১. প্রতিটি অক্ষরের জন্য একটি লিফ নোড তৈরি করুন এবং এদের ফ্রিকোয়েন্সি বা ব্যবহারের হার নির্ধারণ করুন। সব নোডকে একটি মিন-হিপ (min-heap)-এ রাখুন।
২. যতক্ষণ হিপে একের বেশি নোড থাকে: হিপ থেকে সবচেয়ে হালকা দুটি নোড A এবং B বের করুন। একটি নতুন ইন্টারনাল নোড তৈরি করুন যার ওজন হবে A.weight + B.weight এবং A ও B হবে এর দুই চাইল্ড। এই নতুন নোডটিকে আবার হিপে রাখুন।
৩. হিপে অবশিষ্ট শেষ নোডটিই হলো হাফম্যান ট্রির রুট (root)।

ট্রি তৈরি হয়ে গেলে, রুট থেকে বামে গেলে ০ এবং ডানে গেলে ১ ধরে প্রতিটি অক্ষরের কোড তৈরি করুন।

একটি উদাহরণ

ধরা যাক অক্ষরসমূহ: a(৫), b(৯), c(১২), d(১৩), e(১৬), f(৪৫)। ফ্রিকোয়েন্সির যোগফল ১০০ বিট। হাফম্যান ট্রি অনুযায়ী কোড হবে: f=০ (১ বিট), c=১০০ (৩ বিট), d=১০১ (৩ বিট), a=১১০০ (৪ বিট), b=১১০১ (৪ বিট), e=১১১ (৩ বিট)। এখন মোট ফাইলের আকার হবে = ৪৫×১ + ১২×৩ + ১৩×৩ + ৫×৪ + ৯×৪ + ১৬×৩ = ২২৪ বিট। সাধারণ ৩-বিট ফিক্সড কোড ব্যবহার করলে লাগত ৩০০ বিট। হাফম্যান এখানে প্রায় ২৫% জায়গা সাশ্রয় করেছে!

ডিকোডিং

ডিকোড করতে: বিটগুলো একে একে পড়ুন এবং ট্রি-র ওপর দিয়ে যাতায়াত করুন। ০ → বামে যান, ১ → ডানে যান। যখনই আপনি কোনো পাতায় পৌঁছাবেন, সেই অক্ষরটি লিখে আবার রুটে ফিরে যান। পরবর্তী বিটের জন্য একইভাবে শুরু করুন। প্রিফিক্স-ফ্রি হওয়ার কারণে এটি সব সময় একটি অনন্য বা ইউনিক ফলাফল দেয়।

Click chart to zoom

হাফম্যান ট্রি গঠন: গ্রিডি পদ্ধতিতে সবচেয়ে হালকা দুটি নোড মার্জ করে একটি রুট তৈরি করা

দ্রষ্টব্য: যেকোনো নিখুঁত হাফম্যান ট্রিতে সবচেয়ে কম ব্যবহৃত দুটি অক্ষর সবসময় একদম গভীর স্তরে একে অপরের ভাই (siblings) হিসেবে থাকে। এই জ্যামিতিক সত্য এবং নিচে-থেকে-উপরে মার্জ করার গ্রিডি পদ্ধতিই এই অ্যালগরিদমের মূল ভিত্তি। মিন-হিপ শুধু বারবার 'সবচেয়ে হালকা দুটিকে' খুঁজে বের করার কাজটিকে দ্রুত করে দেয়।

হাফম্যান ট্রি — গঠন এবং কোড জেনারেশন

import heapq
from collections import defaultdict

class Node:
    def __init__(self, ch, freq, left=None, right=None):
        self.ch, self.freq = ch, freq
        self.left, self.right = left, right
    def __lt__(self, other): return self.freq < other.freq

def build_huffman(freq):
    heap = [Node(ch, f) for ch, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        heapq.heappush(heap, Node(None, a.freq+b.freq, a, b))
    return heap[0]

def get_codes(root):
    codes = {}
    def dfs(node, code):
        if node.ch is not None:
            codes[node.ch] = code or '0'
            return
        dfs(node.left, code + '0')
        dfs(node.right, code + '1')
    dfs(root, '')
    return codes

freq = {'a':5,'b':9,'c':12,'d':13,'e':16,'f':45}
root = build_huffman(freq)
codes = get_codes(root)
for ch, code in sorted(codes.items()):
    print(f"  {ch}: {code} (freq {freq[ch]})")

original_bits = sum(freq[c] * 3 for c in freq)  # 3-bit fixed
huffman_bits = sum(freq[c] * len(codes[c]) for c in freq)
print(f"Fixed 3-bit: {original_bits} bits")
print(f"Huffman:     {huffman_bits} bits")

Output

  a: 1100 (freq 5)
  b: 1101 (freq 9)
  c: 100 (freq 12)
  d: 101 (freq 13)
  e: 111 (freq 16)
  f: 0 (freq 45)
Fixed 3-bit: 300 bits
Huffman:     224 bits