Huffman coding — greedy দিয়ে ডেটা ছোট করা

১ · ডেটা ছোট করা কেন — SMS, ফাইল আর ধীর ইন্টারনেট

মোবাইলে একটি ইংরেজি SMS-এ ১৬০টি অক্ষর ধরে, কিন্তু বাংলায় লিখলে মাত্র ৭০টি। কারণ ইংরেজি SMS প্রতিটি অক্ষরে ৭ বিট খরচ করে, আর বাংলা অক্ষরের জন্য ফোন ১৬ বিটের Unicode ব্যবহার করে। জায়গা একই — ১৪০ byte — শুধু প্রতি অক্ষরে কত বিট লাগছে, সেটাই পার্থক্য গড়ে দেয়। একই প্রশ্ন সবখানে: গ্রামে ধীর মোবাইল ইন্টারনেটে একটি ওয়েবপেজ কত দ্রুত খুলবে, অফিসের ব্যাকআপ কত জায়গা নেবে, ইমেইলে ছবি কত বড় যাবে।

তথ্য না হারিয়ে কম বিটে লেখার বিদ্যার নাম data compression (ডেটা সংকোচন)। এর দুটি ধরন আছে। Lossless সংকোচনে খুললে হুবহু আগের ডেটা ফেরত আসে — লেখা, প্রোগ্রাম, ব্যাংকের হিসাবে এটাই লাগে; একটি অঙ্ক বদলালেও সর্বনাশ। Lossy সংকোচনে চোখ-কানে ধরা পড়ে না এমন খুঁটিনাটি ফেলে দেওয়া হয় — ছবি, গান, ভিডিও। এই পর্বের Huffman coding একটি lossless পদ্ধতি, আর মজার ব্যাপার হলো lossy JPEG-এর ভেতরেও শেষ ধাপে এটি বসে থাকে।

মূল পর্যবেক্ষণটি সহজ: লেখায় সব অক্ষর সমানভাবে আসে না। ইংরেজিতে e, t, a অনেক বেশি; z, q খুব কম। বাজারের ফর্দে “চাল”, “ডাল” বারবার আসে, “জাফরান” কালেভদ্রে। তাহলে প্রতিটি অক্ষরে সমান জায়গা দেব কেন? বেশি আসা অক্ষরকে ছোট নাম দিন, কম আসাকে লম্বা — গড়ে খরচ কমবে। প্রশ্ন শুধু দুটি: (১) পাঠক কীভাবে বুঝবে কোথায় এক অক্ষর শেষ আর পরেরটা শুরু, আর (২) কোন অক্ষরকে ঠিক কত লম্বা নাম দিলে মোট খরচ সবচেয়ে কম? প্রথম প্রশ্নের উত্তর prefix-free code (অংশ ৩), দ্বিতীয়টির উত্তর Huffman coding — পর্ব ৫০-এর greedy কৌশলের সবচেয়ে বিখ্যাত সফল উদাহরণগুলোর একটি।

২ · Fixed-length বনাম variable-length code — Morse-এর বুদ্ধি

কম্পিউটারে সাধারণ ইংরেজি লেখা থাকে ASCII-তে: প্রতিটি অক্ষর ৮ বিটের একটি byte. এটি একটি fixed-length code — সব অক্ষরের code সমান লম্বা। সুবিধা হলো পড়া সহজ: প্রতি ৮ বিট কেটে নিলেই একটি অক্ষর। কিন্তু একটি বার্তায় যদি মাত্র k টি আলাদা অক্ষর থাকে, তাহলে ৮ বিটের দরকারই নেই — ⌈log₂ k⌉ বিটই যথেষ্ট। ৬টি অক্ষরের জন্য ৩ বিট (2³ = 8 ≥ 6), ১৪টির জন্য ৪ বিট।

এই পর্বের চলমান উদাহরণ: একটি ৪০ অক্ষরের বার্তায় ছয়টি অক্ষর আছে, এই হারে —

ASCII-তে লাগত 40 × 8 = 320 বিট, ৩-বিটের fixed code-এ 120, আর ডান কলামের variable-length code-এ 96 — fixed code-এর চেয়েও ২০% কম। A সবচেয়ে বেশি আসে, তাই তার code মাত্র দুই বিট; H সবচেয়ে কম, তাই চার বিট। এই টেবিলের code কোথা থেকে এল, অংশ ৫-এ নিজেই বানাবেন।

৩ · Prefix-free code আর code tree

Variable-length code-এর বিপদ দেখুন। ধরুন a = 0, b = 01, c = 10. বিটের স্রোত 010 পেলেন। এটি কি 0 | 10 = “ac”, নাকি 01 | 0 = “ba”? দুটোই বৈধ — বার্তা দ্ব্যর্থক। সমস্যার মূল: a-এর code 0 হলো b-এর code 01-এর শুরু (prefix). Morse code-এও একই সমস্যা: E (·) হলো I (··)-এর শুরু। তাই Morse-এ অক্ষরের মাঝে একটি বিরতি দিতে হয় — আসলে বিরতিটিই তৃতীয় একটি চিহ্ন। কম্পিউটারের বিটে তো শুধু 0 আর 1; আলাদা বিরতির চিহ্ন রাখলে সেটিও বিট খায়।

সমাধান: এমন code নিন যেখানে কোনো code অন্য কোনো code-এর শুরুর অংশ নয়. একে বলে prefix-free code (অনেক বই সংক্ষেপে “prefix code” বলে — নামটি বিভ্রান্তিকর, কিন্তু অর্থ একই)। ওপরের টেবিলের code দেখুন: 11, 01, 00, 101, 1001, 1000 — কোনোটি অন্যটির শুরু নয়। তাই বিটের স্রোত বাঁ থেকে পড়তে পড়তে যেই একটি পূর্ণ code মিলে যায়, সেখানেই নিশ্চিন্তে কাটা যায় — সামনে তাকানোর দরকার নেই। ফোন নম্বরও এভাবে কাজ করে: 999 ডায়াল করলেই কল চলে যায়, কারণ কোনো সাধারণ নম্বর 999 দিয়ে শুরু হয় না।

প্রতিটি prefix-free code একটি binary tree

একটি binary tree আঁকুন: root থেকে বাঁ দিকের edge-এর নাম 0, ডানের নাম 1. প্রতিটি অক্ষর একটি leaf-এ বসে, আর root থেকে সেই leaf পর্যন্ত পথের 0/1 পড়লেই তার code. একে বলে code tree. অক্ষর শুধু leaf-এ থাকে বলেই code prefix-free: কোনো অক্ষরের পথ অন্য অক্ষরে পৌঁছানোর আগে থামে না। উল্টোটাও সত্য — যেকোনো prefix-free code থেকে এমন tree আঁকা যায়। তাই “সেরা prefix-free code খোঁজা” আর “সেরা code tree খোঁজা” একই সমস্যা।

একটি code-এর দৈর্ঘ্য = সেই leaf-এর depth. আরেকটি জরুরি তথ্য: সর্বোত্তম tree সবসময় full binary tree — প্রতিটি internal node-এর ঠিক দুটি সন্তান। কারণ কোনো node-এর একটিই সন্তান থাকলে সেই এক-সন্তানের পুরো subtree এক ধাপ ওপরে তুলে আনা যায়: ওই subtree-র সব code এক বিট ছোট হয়, তবু prefix-free থাকে। তাই n টি অক্ষরের সর্বোত্তম tree-তে n টি leaf আর ঠিক n − 1 টি internal node.

৪ · খরচ মাপা — গড় code length

একটি code tree T-এর খরচ হলো বার্তা লিখতে মোট কত বিট লাগে। অক্ষর c যদি f(c) বার আসে আর তার depth d(c) হয়, তাহলে

এর নাম weighted path length — প্রতিটি leaf-এর পথের দৈর্ঘ্যকে তার ওজন (frequency) দিয়ে গুণ করে যোগ। f-কে সম্ভাবনা p(c) = f(c)/মোট ধরলে L হলো প্রতি অক্ষরে প্রত্যাশিত বিট (expected code length). উদাহরণে B = 96, L = 96/40 = 2.4 বিট — fixed code-এর ৩ বিটের চেয়ে কম।

একটি সুন্দর অভেদ. প্রতিটি internal node-এর ওজন ধরুন তার নিচের সব leaf-এর frequency-র যোগফল। তাহলে B(T) = সব internal node-এর ওজনের যোগফল। কেন? একটি leaf c-এর frequency ঠিক ততবার যোগ হয়, যতগুলো internal node তার পূর্বপুরুষ — অর্থাৎ d(c) বার। ফলে Huffman-এ প্রতিটি জোড়ার যোগফল লিখে রাখলেই খরচ পাওয়া যায়; উদাহরণে 5 + 11 + 15 + 25 + 40 = 96. ইন্টারভিউর “দড়ি জোড়ার সর্বনিম্ন খরচ” (দুটি দড়ি জুড়তে খরচ = দুটির দৈর্ঘ্যের যোগ) প্রশ্নটি আসলে হুবহু এই হিসাব।

সমস্যাটি এখন স্পষ্ট: n টি অক্ষর আর তাদের frequency দেওয়া; এমন full binary tree খুঁজুন যার leaf-গুলো এই অক্ষর আর B(T) সবচেয়ে কম। সম্ভাব্য tree-এর সংখ্যা n-এর সাথে বিস্ফোরকভাবে বাড়ে (Catalan সংখ্যা গুণ n! রকম লেবেল), তাই সব দেখে বাছাই অসম্ভব। দরকার একটি চতুর নিয়ম।

৫ · Huffman-এর অ্যালগরিদম — সবচেয়ে বিরল দুটিকে জোড়া

স্বাভাবিক ভাবনা হলো ওপর থেকে শুরু করা: অক্ষরগুলোকে প্রায় সমান ওজনের দুই দলে ভাগ করুন, এক দল 0, অন্যটি 1, তারপর প্রতিটি দলে আবার একই কাজ। এটিই Shannon-Fano পদ্ধতি — কিন্তু এটি সবসময় সর্বোত্তম নয় (ভাবনার প্রশ্ন ১)। David Huffman উল্টো দিক থেকে ভাবলেন: নিচ থেকে ওপরে. সবচেয়ে কম আসা দুটি অক্ষর নিশ্চয়ই সবচেয়ে লম্বা code পাবে — তাই তাদের সবচেয়ে গভীরে ভাইবোন বানিয়ে দিন। জোড়া দুটিকে এখন একটি “নতুন অক্ষর” হিসেবে দেখুন, যার frequency দুটির যোগফল। বাকি কাজ একই সমস্যা, শুধু একটি অক্ষর কম।

প্রতিবার “সবচেয়ে কম frequency-র দুটি” বের করা আর নতুনটি ঢোকানো — এটি ঠিক পর্ব ২৩-এর min-heap বা priority queue-এর কাজ।

Pseudocode — Huffman (C = n symbols, f = frequencies; n >= 2)

Huffman(C):
    Q = min-heap of leaves, key = f            // ties: smaller node id first
    repeat n - 1 times:
        x = Q.extractMin()                     // least frequent
        y = Q.extractMin()                     // second least frequent
        z = new node: left = x, right = y, f(z) = f(x) + f(y)
        Q.insert(z)
    return Q.extractMin()                      // the root of the code tree
// code of a symbol = labels on the path from the root: left edge 0, right edge 1

উদাহরণের ছয়টি অক্ষরে চালিয়ে দেখুন। লাল/সবুজ রঙের সংখ্যাটি এই ধাপে বানানো নতুন node:

এবার একই অ্যালগরিদম আসল লেখায়। জাতীয় সংগীতের প্রথম লাইন, ইংরেজি অক্ষরে: amar sonar bangla ami tomay bhalobashi. প্রোগ্রামটি অক্ষর গোনে, heap দিয়ে tree বানায়, প্রতিটি অক্ষরের code ছাপে, পুরো লেখা encode করে, তারপর tree ধরে decode করে মিলিয়ে দেখে। Tie ভাঙার নিয়ম স্থির রাখা হয়েছে — heap-এর key (frequency, node id), আর leaf-এর id অক্ষরের ক্রমে, নতুন node-এর id তার পরে — তাই C++ আর Python হুবহু এক উত্তর দেয়।

#include <cstdio>
#include <functional>
#include <map>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main() {
    const string text = "amar sonar bangla ami tomay bhalobashi";
    map<char, int> freq;                          // leaves sorted by character
    for (char c : text) ++freq[c];
    vector<char> sym; vector<int> f, L, R;        // node arrays, leaves first
    for (auto [c, k] : freq) { sym.push_back(c); f.push_back(k); L.push_back(-1); R.push_back(-1); }
    using P = pair<int, int>;                     // (frequency, node id): id breaks ties
    priority_queue<P, vector<P>, greater<P>> pq;
    for (int i = 0; i < (int)f.size(); ++i) pq.push({f[i], i});
    while (pq.size() > 1) {
        auto [fa, a] = pq.top(); pq.pop();        // the two least frequent nodes
        auto [fb, b] = pq.top(); pq.pop();
        sym.push_back(0); f.push_back(fa + fb); L.push_back(a); R.push_back(b);
        pq.push({fa + fb, (int)f.size() - 1});
    }
    const int root = pq.top().second;
    map<char, string> code;
    function<void(int, const string&)> walk = [&](int v, const string& s) {
        if (L[v] < 0) { code[sym[v]] = s.empty() ? "0" : s; return; }
        walk(L[v], s + "0"); walk(R[v], s + "1");  // left edge 0, right edge 1
    };
    walk(root, "");
    for (auto [c, k] : freq) printf("'%c' freq %2d code %s\n", c, k, code[c].c_str());
    string bits, out;
    for (char c : text) bits += code[c];      // encode
    for (int v = root; char b : bits) {           // decode: walk down from the root
        v = (b == '0') ? L[v] : R[v];
        if (L[v] < 0) { out += sym[v]; v = root; }
    }
    printf("first 24 bits: %s\n", bits.substr(0, 24).c_str());
    printf("fixed 8-bit: %zu bits, huffman: %zu bits\n", 8 * text.size(), bits.size());
    printf("average: %.3f bits per char\n", (double)bits.size() / text.size());
    printf("decoded matches: %s\n", out == text ? "True" : "False");
}

' ' freq  5 code 101
'a' freq  9 code 01
'b' freq  3 code 1100
'g' freq  1 code 10010
'h' freq  2 code 11111
'i' freq  2 code 0000
'l' freq  2 code 0001
'm' freq  3 code 1101
'n' freq  2 code 0010
'o' freq  3 code 1110
'r' freq  2 code 0011
's' freq  2 code 1000
't' freq  1 code 10011
'y' freq  1 code 11110
first 24 bits: 011101010011101100011100
fixed 8-bit: 304 bits, huffman: 134 bits
average: 3.526 bits per char
decoded matches: True

import heapq
from collections import Counter

text = "amar sonar bangla ami tomay bhalobashi"
freq = sorted(Counter(text).items())            # leaves sorted by character
sym = [c for c, _ in freq]
f = [k for _, k in freq]
L, R = [-1] * len(f), [-1] * len(f)
pq = [(k, i) for i, k in enumerate(f)]          # (frequency, node id): id breaks ties
heapq.heapify(pq)
while len(pq) > 1:
    fa, a = heapq.heappop(pq)                   # the two least frequent nodes
    fb, b = heapq.heappop(pq)
    sym.append(""); f.append(fa + fb); L.append(a); R.append(b)
    heapq.heappush(pq, (fa + fb, len(f) - 1))
root = pq[0][1]
code = {}
def walk(v, s):                                 # left edge = 0, right edge = 1
    if L[v] < 0:
        code[sym[v]] = s or "0"
        return
    walk(L[v], s + "0"); walk(R[v], s + "1")
walk(root, "")
for c, k in freq:
    print(f"'{c}' freq {k:2d} code {code[c]}")
bits = "".join(code[c] for c in text)
out, v = [], root
for b in bits:                                  # decode: walk down from the root
    v = L[v] if b == "0" else R[v]
    if L[v] < 0:
        out.append(sym[v]); v = root
print("first 24 bits:", bits[:24])
print(f"fixed 8-bit: {8 * len(text)} bits, huffman: {len(bits)} bits")
print(f"average: {len(bits) / len(text):.3f} bits per char")
print("decoded matches:", "".join(out) == text)

' ' freq  5 code 101
'a' freq  9 code 01
'b' freq  3 code 1100
'g' freq  1 code 10010
'h' freq  2 code 11111
'i' freq  2 code 0000
'l' freq  2 code 0001
'm' freq  3 code 1101
'n' freq  2 code 0010
'o' freq  3 code 1110
'r' freq  2 code 0011
's' freq  2 code 1000
't' freq  1 code 10011
'y' freq  1 code 11110
first 24 bits: 011101010011101100011100
fixed 8-bit: 304 bits, huffman: 134 bits
average: 3.526 bits per char
decoded matches: True

৬ · Decoding — tree ধরে হাঁটা

Encode করা সহজ: প্রতিটি অক্ষরের code পাশাপাশি বসান। Decode-এ বিটের স্রোত আর tree হাতে নিয়ে root থেকে হাঁটুন — 0 পেলে বাঁয়ে, 1 পেলে ডানে। Leaf-এ পৌঁছালেই একটি অক্ষর লিখুন আর root-এ ফিরে যান। Prefix-free বলেই leaf-এ পৌঁছানো মাত্র সিদ্ধান্ত নেওয়া যায়। উদাহরণের code দিয়ে বাংলা শব্দ “নাটক”-এর ইংরেজি বানান NATAK encode করলে পাই 01110011101 — মাত্র ১১ বিট (ASCII-তে ৪০)। এবার উল্টো পথে:

বিট শেষ হলে আমরা root-এ ফিরে আছি — এটিই বৈধ বার্তার চিহ্ন। মাঝপথে বিট ফুরালে (কোনো internal node-এ আটকে থাকলে) বার্তা কাটা পড়েছে। বাস্তবের দ্রুত decoder বিট ধরে হাঁটে না; তারা একসাথে কয়েকটি বিট নিয়ে একটি lookup টেবিলে দেখে নেয় কোন অক্ষর আর কত বিট খরচ হলো — একই ফল, অনেক কম ধাপে।

নিজে চালিয়ে দেখুন — আপনার লেখার Huffman code

নিচের টুলে “চালিয়ে দেখুন” চাপুন, তারপর বক্সে যেকোনো লেখা দিন — ইংরেজি বা বাংলা। টুলটি প্রতিটি অক্ষরের frequency আর code দেখাবে, আর তিনটি সংখ্যা তুলনা করবে: Huffman-এ মোট বিট, প্রতি অক্ষরে ৮ বিট ধরলে, আর UTF-8-এ আসলে কত বিট। বাংলা লিখে দেখুন — UTF-8-এ প্রতিটি বাংলা অক্ষর ৩ byte = ২৪ বিট, তাই সাশ্রয় আরও নাটকীয়।

const $ = id => document.getElementById(id);
const esc = s => s.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/ /g, "space");
function huffman(text) {
  const cnt = new Map();
  for (const ch of text) cnt.set(ch, (cnt.get(ch) || 0) + 1);       // code points, so Bangla works
  const sym = [...cnt.keys()].sort(), f = sym.map(s => cnt.get(s));
  const L = sym.map(() => -1), R = sym.map(() => -1);
  const pq = f.map((k, i) => [k, i]);                                   // (frequency, node id)
  while (pq.length > 1) {
    pq.sort((a, b) => a[0] - b[0] || a[1] - b[1]);                      // simple stand-in for a min-heap
    const [[fa, a], [fb, b]] = pq.splice(0, 2);
    f.push(fa + fb); L.push(a); R.push(b); sym.push("");
    pq.push([fa + fb, f.length - 1]);
  }
  const code = new Map();
  const walk = (v, s) => { if (L[v] < 0) code.set(sym[v], s || "0"); else { walk(L[v], s + "0"); walk(R[v], s + "1"); } };
  if (pq.length) walk(pq[0][1], "");
  return { cnt, code };
}
function show() {
  const t = $("tx").value, { cnt, code } = huffman(t), n = [...t].length;
  let bits = 0, rows = "<tr><th>char</th><th>freq</th><th>code</th></tr>";
  for (const c of [...cnt.keys()].sort()) {
    bits += cnt.get(c) * code.get(c).length;
    rows += `<tr><td>${esc(c)}</td><td>${cnt.get(c)}</td><td>${code.get(c)}</td></tr>`;
  }
  const utf8 = new TextEncoder().encode(t).length * 8;
  const msg = `${n} chars, ${cnt.size} distinct: huffman ${bits} bits, 8-bit ${8 * n}, UTF-8 ${utf8}`;
  $("hm").textContent = msg; $("ht").innerHTML = rows; console.log(msg);
}
$("go").onclick = show; $("tx").oninput = show; show();

38 chars, 14 distinct: huffman 134 bits, 8-bit 304, UTF-8 304

৭ · কেন সর্বোত্তম — দুটি lemma আর induction

Greedy অ্যালগরিদম প্রায়ই ভুল উত্তর দেয় (পর্ব ৫০), তাই প্রমাণ ছাড়া Huffman-কে বিশ্বাস করার কারণ নেই। প্রমাণের দুটি ধাপ — পর্ব ৫০-এর exchange argument আর পর্ব ০৩-এর induction.

Lemma ১ (greedy পছন্দ নিরাপদ). x আর y সবচেয়ে কম frequency-র দুটি অক্ষর হলে এমন একটি সর্বোত্তম tree আছে, যেখানে x আর y ভাইবোন এবং সবচেয়ে গভীর স্তরে।

প্রমাণ. যেকোনো সর্বোত্তম tree T নিন। এটি full, তাই সবচেয়ে গভীর স্তরে অন্তত দুটি ভাইবোন leaf আছে, ধরুন a আর b. x-কে a-এর সাথে জায়গা বদল করুন। খরচের পরিবর্তন

কারণ f(a) ≥ f(x) (x সবচেয়ে বিরল) আর d(x) ≤ d(a) (a সবচেয়ে গভীরে)। খরচ বাড়েনি, তাই নতুন tree-ও সর্বোত্তম। একইভাবে y-কে b-এর সাথে বদলান। এখন x, y সবচেয়ে গভীরে ভাইবোন। ∎

Lemma ২ (জোড়া দিলে সমস্যা ছোট হয়). C থেকে x, y সরিয়ে একটি নতুন অক্ষর z বসান, f(z) = f(x) + f(y); নতুন বর্ণমালা C′. C′-এর যেকোনো tree T′-এ z-এর leaf ভেঙে দুই সন্তান x, y বসালে C-এর একটি tree T পাই, আর B(T) = B(T′) + f(x) + f(y) — কারণ x আর y z-এর চেয়ে এক স্তর গভীরে, বাকিরা অপরিবর্তিত।

উপপাদ্য. Huffman সর্বোত্তম tree দেয়। Induction অক্ষরের সংখ্যা n-এর ওপর। n = 2 হলে একমাত্র full tree — দুই leaf, প্রত্যেকে এক বিট। ধরুন n − 1 অক্ষরে সত্য। n অক্ষরে Huffman প্রথমে x, y জোড়ে, তারপর C′-তে Huffman চালায় — induction অনুযায়ী সেই T′ C′-এর জন্য সর্বোত্তম। বিপরীতে ধরুন C-এর কোনো tree U আছে যার B(U) < B(T). Lemma ১ অনুযায়ী U-কে এমনভাবে নিতে পারি যেখানে x, y ভাইবোন। তাদের জুড়ে z বানালে C′-এর tree U′, আর B(U′) = B(U) − f(x) − f(y) < B(T) − f(x) − f(y) = B(T′) — T′ সর্বোত্তম, তাই এটি অসম্ভব। ∎

উদাহরণে প্রমাণটি সংখ্যা দিয়ে দেখুন। শুরু একটি ইচ্ছাকৃত খারাপ tree থেকে — Huffman tree-তে শুধু A আর H-এর জায়গা উল্টে দেওয়া:

৮ · Complexity — heap দিয়ে O(n log n), সাজানো থাকলে O(n)

ধরুন লেখার দৈর্ঘ্য m আর আলাদা অক্ষর n টি। খরচ ধাপে ধাপে:

• গোনা: প্রতিটি অক্ষর একবার দেখা — O(m); ASCII-তে ২৫৬ ঘরের একটি অ্যারেই যথেষ্ট।
• Tree বানানো: heapify O(n), তারপর n − 1 বার merge — প্রতিবার দুটি extract আর একটি insert, প্রতিটি O(log n). মোট O(n log n).
• Code পড়া: tree-র ২n − 1 টি node একবার করে দেখা — O(n) (প্রতিটি code string বানালে মোট code দৈর্ঘ্যের সমান বাড়তি)।
• Encode আর decode: আউটপুটের বিট সংখ্যা B ধরে O(m + B); decode-এ প্রতি বিটে এক ধাপ।
• জায়গা: tree আর heap O(n), এর বাইরে ইনপুট ও আউটপুট।

সাধারণত n ছোট (byte হলে সর্বোচ্চ ২৫৬), তাই আসল খরচ লেখা পড়া আর বিট লেখায়। তবে অনেক অক্ষরের বর্ণমালায় (যেমন শব্দভিত্তিক coding) tree বানানোর অংশ গুরুত্বপূর্ণ।

দুটি queue-এর কৌশল — O(n)

frequency যদি আগে থেকেই ছোট থেকে বড় সাজানো থাকে, heap-ও লাগে না। দুটি সাধারণ queue নিন: Q1-এ সাজানো leaf-গুলো, Q2 শুরুতে খালি — নতুন বানানো node এখানে পেছনে যোগ হবে। প্রতিবার দুই queue-এর সামনের মধ্যে ছোটটি নিন, দুবার; জোড়া দিয়ে Q2-এর পেছনে রাখুন। চাবিকাঠি হলো: নতুন node-গুলো নিজেরাই বাড়তে থাকা ক্রমে তৈরি হয়, কারণ প্রতিবার আমরা অবশিষ্টদের মধ্যে সবচেয়ে ছোট দুটি নিই, আর অবশিষ্টরা আগের বাছাইয়ের চেয়ে ছোট হতে পারে না। তাই Q2 সবসময় সাজানো, আর “সবচেয়ে ছোট” মানে শুধু দুটি সামনের ঘর তুলনা — O(1). মোট O(n). উদাহরণে Q1 = 2 3 6 7 8 14; Q2-তে ক্রমে আসে 5, 11, 15, 25, 40 — সত্যিই বাড়তে থাকা। (এই কৌশলের কৃতিত্ব সাধারণত Jan van Leeuwen-কে দেওয়া হয়, ১৯৭৬.) সাজানো না থাকলে প্রথমে সাজাতে O(n log n) — তাই সার্বিক নিম্নসীমা বদলায় না।

৯ · Tie, canonical code, entropy আর বাস্তবের Huffman

Tie — একাধিক সঠিক উত্তর

দুটি node-এর frequency সমান হলে কাকে আগে নেবেন? যেকোনোটি নিলেই Huffman-এর খরচ সর্বোত্তম থাকে — প্রমাণে কোথাও “একমাত্র” দরকার হয়নি। কিন্তু tree-র আকার, এমনকি code-এর দৈর্ঘ্যও বদলাতে পারে। যেমন frequency 1, 1, 2, 2: একভাবে দৈর্ঘ্য 2, 2, 2, 2 (খরচ 12), আরেকভাবে 3, 3, 2, 1 (খরচ 1·3 + 1·3 + 2·2 + 2·1 = 12). মোট সমান, আকার আলাদা। তার ওপর যেকোনো internal node-এর বাঁ-ডান (0/1) অদলবদল করলে code বদলায়, খরচ নয়। তাই পরীক্ষার খাতায় আপনার code বইয়ের সাথে না মিললেও ভুল নয় — মোট বিট মিলিয়ে দেখুন। এই কারণেই এই পর্বের প্রোগ্রামে tie-breaking নিয়ম স্থির করা: (frequency, id). আমাদের নিয়মে পুরোনো node আগে বের হয়; এতে code-এর দৈর্ঘ্যের পার্থক্য কম থাকে, যা বাস্তবে সুবিধাজনক।

Canonical Huffman code — শুধু দৈর্ঘ্য পাঠালেই চলে

Decoder-কে code জানাতে হয়। পুরো tree পাঠানো ব্যয়বহুল আর জটিল। পর্যবেক্ষণ: খরচ নির্ভর করে শুধু প্রতিটি অক্ষরের code দৈর্ঘ্যের ওপর, আসল 0/1-এর ওপর নয়। তাই একটি নিয়ম ঠিক করুন যা দৈর্ঘ্য থেকেই code বানায় — canonical Huffman code: অক্ষরগুলোকে (দৈর্ঘ্য, অক্ষর) ক্রমে সাজান, প্রথমটিকে সব-শূন্য code দিন, পরেরটি আগেরটির +1, আর দৈর্ঘ্য বাড়লে ডানে 0 যোগ (বাঁয়ে shift).

এখন encoder শুধু প্রতিটি অক্ষরের দৈর্ঘ্য পাঠায় (অক্ষরের ক্রমে: A2 H4 K3 N2 S4 T2), decoder একই নিয়মে হুবহু একই code বানিয়ে নেয়। DEFLATE (zip, gzip, PNG) ঠিক এভাবেই কাজ করে, আর দৈর্ঘ্যের তালিকাটিকেও আবার Huffman দিয়ে ছোট করে। দৈর্ঘ্য বৈধ কি না, তা একটি সরল শর্তে ধরা যায় — Kraft inequality: Σ 2^−l ≤ 1. এখানে 3·¼ + ⅛ + 2·1/16 = 1 — tree পুরো ভরা (full).

Entropy — কত ছোট করা সম্ভব

Huffman সেরা prefix-free code দেয় — কিন্তু সেই সেরাটি কত ভালো? ১৯৪৮ সালে Claude Shannon তাঁর “A Mathematical Theory of Communication” প্রবন্ধে উত্তর দেন। অক্ষরগুলো p₁, …, p_n সম্ভাবনায় এলে উৎসটির entropy

— অর্থাৎ বার্তায় আসলে কতটা “অনিশ্চয়তা” বা নতুন তথ্য আছে। যে অক্ষর প্রায় নিশ্চিত, সে প্রায় কোনো তথ্য দেয় না; বিরল অক্ষর অনেক তথ্য দেয় (log₂(1/p) বিট)। Shannon-এর source coding theorem বলে, অক্ষর-ধরে লেখা যেকোনো lossless code-এর গড় দৈর্ঘ্য L ≥ H, আর Huffman-এর জন্য

উদাহরণে H ≈ 2.341, L = 2.4. জাতীয় সংগীতের লাইনে H ≈ 3.500, L = 134/38 ≈ 3.526 — সীমার একদম কাছে। সব p যদি ½-এর ঘাত হয় (½, ¼, ⅛, …), তাহলে L = H হুবহু।

বাস্তবে Huffman — zip থেকে JPEG, আর তার সীমা

Huffman-এর সীমাগুলো মনে রাখুন। (১) প্রতিটি অক্ষরে পূর্ণসংখ্যা বিট — অতি সাধারণ অক্ষরে অপচয় (ওপরের 0.9/0.1 উদাহরণ)। (২) Frequency আগে জানতে হয়: হয় পুরো ফাইল দুবার পড়া (একবার গোনা, একবার লেখা), নয় চলতে চলতে tree বদলানো — adaptive Huffman. (৩) শুধু প্রতিটি অক্ষরের হার দেখে, পাশাপাশি অক্ষরের সম্পর্ক দেখে না: “ক্ষ”-এর পরে কী আসে, বা একই শব্দ বারবার — এগুলো ধরে LZ77-এর মতো পদ্ধতি বা context model. তাই বাস্তব compressor Huffman-কে একা নয়, অন্য কৌশলের সাথে জুড়ে ব্যবহার করে। (৪) Code table পাঠাতেও বিট লাগে; খুব ছোট বার্তায় সেটিই লাভ খেয়ে ফেলতে পারে।

১০ · AI-এর যুগে Huffman — tree ঠিক, খরচ ভুল

“Huffman coding-এর কোড লিখে দাও” — AI মুহূর্তেই লিখবে, আর বেশিরভাগ সময় tree ঠিকই বানাবে। ভুলগুলো লুকিয়ে থাকে কিনারায়: একটিমাত্র অক্ষরের লেখা, tie-এর কারণে প্রতিবার ভিন্ন code, বিটকে অক্ষর হিসেবে রেখে “সংকোচন” দাবি, বা code table না রেখেই ফাইল লেখা। আর ব্যাখ্যায় AI প্রায়ই নিজের code-কে “একমাত্র সঠিক” বলে, বা Shannon-Fano-র মতো ওপর থেকে ভাগ করা পদ্ধতিকে Huffman বলে চালিয়ে দেয়।

Huffman-এর কোডে AI সাধারণত যেসব ভুল করে

Huffman-এর কোড যাচাইয়ের চেকলিস্ট

• ছোট একটি frequency তালিকায় হাতে tree বানিয়ে মোট বিট মিলিয়েছি (merge-এর যোগফল = Σ f·d)
• Encode করে decode করলে হুবহু আগের লেখা ফেরে — এলোমেলো হাজারটি লেখায় stress testing করেছি
• ছোট বর্ণমালায় সব সম্ভাব্য দৈর্ঘ্যের সমন্বয় দেখে (brute force) সর্বনিম্ন খরচ Huffman-এর সাথে মিলিয়েছি
• Edge case চালিয়েছি: খালি লেখা, একটিমাত্র অক্ষর, সব সমান frequency, খুব বিরল অক্ষর
• Tie-এর নিয়ম স্থির, তাই একই ইনপুটে বারবার আর দুই ভাষায় একই code পাই
• প্রতিটি code অন্য কোনো code-এর শুরু নয় — একটি ছোট ফাংশনে যাচাই করেছি