Prefix code আর Huffman coding

১ · Code কী — fixed, variable আর unique decodability

লগের ছয়টি অবস্থার সংক্ষিপ্ত নাম ধরি: N (নতুন), P (প্যাক), S (পথে, shipped), D (পৌঁছেছে, delivered), C (বাতিল, cancelled), R (ফেরত, returned). প্রতি ১০০টি লগ-লাইনে এদের গড় সংখ্যা (কাল্পনিক, উদাহরণের জন্য) D 36, S 24, P 15, N 12, C 8, R 5.

সব codeword সমান দৈর্ঘ্যের হলে তা fixed-length code. ছয়টি চিহ্নের জন্য অন্তত ⌈log₂ 6⌉ = 3 bit লাগে, কারণ 2 bit দিয়ে মাত্র 2² = 4টি আলাদা string হয় (পর্ব ৩১-এর গুণের নিয়ম)। দৈর্ঘ্য আলাদা হতে পারলে তা variable-length code; লাভের আশা এখানে: ঘন ঘন আসা D-কে ছোট codeword দিলে মোট বিট কমে। টেলিগ্রাফের Morse code এই বুদ্ধিতেই বেশি ব্যবহৃত E-কে একটি ডট দেয়।

কিন্তু variable length-এর একটি ঝুঁকি আছে। ধরুন c(a) = 0, c(b) = 1, c(c) = 01. তাহলে “01” মানে “ab” না “c”? দুটোই হতে পারে, অর্থাৎ বার্তা হারিয়ে যায়।

তিনটি ছোট উদাহরণ সম্পর্কগুলো স্পষ্ট করে:

দ্বিতীয় সারির code-টি UD, কারণ কোনো codeword অন্যটির শেষাংশ (suffix) নয়: বার্তাটি শেষ থেকে পড়লে প্রতিবার একটি codeword নিশ্চিতভাবে চেনা যায়। কিন্তু সামনে থেকে পড়তে গেলে “0” দেখেই বলা যায় না সেটি একা 0 না 01-এর শুরু; অপেক্ষা করতে হয়, কখনো পুরো বার্তার শেষ পর্যন্ত। Prefix code-এ এই অপেক্ষা নেই: একটি codeword শেষ হওয়ামাত্র চেনা যায়। তাই prefix code-কে instantaneous code-ও বলে।

1. ধরুন দুটি আলাদা বার্তা u₁⋯u_j আর v₁⋯v_k-এর encoding একই string w. প্রথম যে স্থানে চিহ্ন আলাদা, তার আগের অংশ বাদ দিলেও encoding সমান থাকে, তাই ধরে নেওয়া যায় u₁ ≠ v₁ (একটি বার্তা অন্যটির শুরু হলে বাকি অংশের encoding ফাঁকা string হতো, যা অসম্ভব, কারণ codeword অশূন্য)। — সাধারণ অংশ ছাঁটা
2. w শুরু হয় c(u₁) দিয়ে, আবার c(v₁) দিয়েও। দুটির যেটি ছোট (বা সমান), সেটি অন্যটির prefix. — একই string-এর দুটি শুরু
3. u₁ ≠ v₁ বলে দুটি আলাদা codeword, আর একটি অন্যটির prefix: prefix code-এর সংজ্ঞার বিরোধ। ∎

উল্টোটা সত্য নয়, টেবিলের দ্বিতীয় সারিই প্রমাণ। তবু §৩-এ দেখবেন, codeword-এর দৈর্ঘ্যের দিক থেকে UD code prefix code-এর চেয়ে বেশি কিছু দিতে পারে না।

২ · Prefix code আর binary tree — leaf মানে codeword

একটি binary tree নিন, যার প্রতিটি node-এর বাঁ দিকের edge-এ 0 আর ডান দিকের edge-এ 1 লেখা। Root থেকে কোনো node পর্যন্ত পথের লেবেলগুলো পরপর পড়লে একটি bit string পাওয়া যায়, যার দৈর্ঘ্য সেই node-এর গভীরতা; ইংরেজিতে একে depth বলে। নিচের ছবিটি বাজারঘরের লগের জন্য §৪-এ বানানো Huffman code-এর code tree.

1. (⇒) প্রতিটি codeword-এর সব prefix নিয়ে একটি tree বানান: root ফাঁকা string, আর string x-এর সন্তান x0 ও x1, তবে কেবল সেগুলোই রাখুন যেগুলো কোনো codeword-এর prefix. কোনো codeword w যদি internal node হতো, তবে w-এর একটি সন্তান অন্য কোনো codeword-এর prefix, অর্থাৎ w নিজেই সেই codeword-এর prefix, যা নিষেধ। তাই প্রতিটি codeword leaf, আর প্রতিটি leaf কোনো codeword (কারণ leaf নিজেই কোনো codeword-এর prefix, আর আর বাড়ে না)। — prefix-এর tree
2. (⇐) দুটি leaf u, v-এর একটি অন্যটির prefix হলে tree-তে u থেকে v-তে নামার পথ থাকত, তখন u-এর সন্তান থাকত, অর্থাৎ u leaf নয়। বিরোধ। ∎ — leaf-এর সংজ্ঞা

Decoding এই ছবিতে হাঁটার মতো: root থেকে শুরু করে প্রতিটি বিট পড়ে বাঁয়ে বা ডানে যান; leaf-এ পৌঁছালে সেই চিহ্ন লিখুন আর root-এ ফিরুন। Tree-র height h হলে প্রতিটি চিহ্নে বড়জোর h ধাপ। একটি পর্যবেক্ষণ পরে কাজে লাগবে।

প্রমাণ: কোনো internal node v-এর একটিমাত্র সন্তান থাকলে সেই সন্তানের subtree-টিকে তুলে v-এর জায়গায় বসান। v-এর নিচের প্রতিটি leaf-এর গভীরতা এক কমে, বাকিরা বদলায় না, আর leaf-গুলো তখনো prefix-free. ধনাত্মক সম্ভাবনার অন্তত একটি leaf v-এর নিচে আছে, তাই গড় দৈর্ঘ্য কঠোরভাবে কমে; সর্বোত্তম code-এ তাই এমন v থাকতে পারে না। ∎ Full binary tree-র recursive সংজ্ঞা আর “leaf = internal + 1”-এর ধরনের হিসাব পর্ব ১২-এ দেখেছেন; rooted আর m-ary tree-র গণনা পর্ব ৬৫ “Tree — ধর্ম, rooted tree আর m-ary tree-এর হিসাব”-এ।

৩ · Kraft-এর অসমতা, তার বিপরীত আর McMillan

কোন দৈর্ঘ্যগুলো একসঙ্গে সম্ভব? চারটি চিহ্নকে দৈর্ঘ্য 1, 1, 1, 2 দেওয়া যায় না: দৈর্ঘ্য 1-এর string মাত্র দুটি, 0 আর 1. এই “জায়গার হিসাব” একটি সুন্দর অসমতায় ধরা পড়ে।

প্রতিটি পদ 2^−l-কে ভাবুন codeword-টি সব সম্ভাব্য দীর্ঘ string-এর কত ভাগ “দখল” করে: দৈর্ঘ্য 1-এর codeword অর্ধেক, দৈর্ঘ্য 2-এর এক-চতুর্থাংশ। মোট দখল এক-এর বেশি হতে পারে না।

প্রমাণ (prefix ⇒ অসমতা): ধরুন m = max l_i.

1. দৈর্ঘ্য l_i-এর codeword w_i-কে prefix হিসেবে রাখে এমন দৈর্ঘ্য m-এর string ঠিক 2^m−l_iটি: বাকি m − l_iটি বিট যেকোনো। — গুণের নিয়ম
2. আলাদা i আর j-এর এই দুই সেট disjoint: একটি string x দুটিতেই থাকলে w_i আর w_j দুটিই x-এর prefix, তাই ছোটটি বড়টির prefix, যা নিষেধ। — prefix-free
3. সব সেট দৈর্ঘ্য m-এর 2^mটি string-এর ভেতরে, তাই ∑ 2^m−l_i ≤ 2^m. দুই দিককে 2^m দিয়ে ভাগ করলে অসমতা। ∎ — disjoint সেটের যোগ

প্রমাণ (বিপরীত, নির্মাণসহ): দৈর্ঘ্যগুলো সাজান l₁ ≤ l₂ ≤ ⋯ ≤ l_n, আর a_j = ∑_i<j 2^−l_i (a₁ = 0 ধরে)। Codeword w_j হলো a_j-এর binary বিস্তারের দশমিক-বিন্দুর পরের প্রথম l_jটি বিট।

1. i < j হলে l_i ≤ l_j, তাই a_j হলো 2^−l_j-এর পূর্ণ গুণিতক; ফলে প্রথম l_jটি বিটই a_j-কে হুবহু ধরে, কিছু ছাঁটা পড়ে না। — ছোট ভগ্নাংশ বড় ঘাতের গুণিতক
2. a_j ≤ 1 − 2^−l_j < 1, কারণ মোট যোগ ≤ 1 আর a_j-এ j-তম পদটি নেই। তাই l_jটি বিটে জায়গা হয়। — Kraft-এর শর্ত
3. w_i দিয়ে শুরু হয় এমন সব বিস্তারের সংখ্যা ঠিক ব্যবধি [a_i, a_i + 2^−l_i)-এ পড়ে। — binary বিস্তার
4. i < j হলে a_j ≥ a_i + 2^−l_i, তাই a_j সেই ব্যবধির বাইরে: w_i হলো w_j-এর prefix নয়। আর l_j ≥ l_i বলে w_j-ও w_i-এর prefix হতে পারে না (সমান দৈর্ঘ্যে দুটি আলাদা)। ∎ — ব্যবধি পরপর, ওভারল্যাপ নেই

1lengths = 1, 2, 3, 32j = 1: a = 03j = 2: a = 1/24j = 3: a = 3/45j = 4: a = 7/86sum = 1: tree full

Prefix code-এ সীমাবদ্ধ থাকলে কি আমরা কিছু হারাই? UD code-এর দৈর্ঘ্য কি Kraft ভেঙে আরও ছোট হতে পারে? না, এবং প্রমাণটি গণনার একটি চমৎকার কৌশল।

1. S = ∑ 2^−l_i, m = max l_i, আর k যেকোনো ধনাত্মক পূর্ণসংখ্যা। S^k গুণ করে খুললে প্রতিটি পদ এক একটি k-চিহ্নের বার্তার জন্য 2^{−(বার্তার encoding-এর দৈর্ঘ্য)}. — বিস্তার
2. দৈর্ঘ্য অনুযায়ী জড়ো করুন: S^k = ∑_t=k..km A_t 2^−t, যেখানে A_t = যেসব k-চিহ্নের বার্তার encoding দৈর্ঘ্য t, তাদের সংখ্যা। — পদ জড়ো করা
3. Code UD, তাই আলাদা বার্তার encoding আলাদা string; দৈর্ঘ্য t-এর string মাত্র 2^tটি, তাই A_t ≤ 2^t. — one-to-one, পর্ব ৩২-এর যুক্তি
4. অতএব S^k ≤ ∑_t=k..km 1 ≤ km, সব k-এর জন্য। — যোগ
5. S > 1 হলে S^k ঘাতের হারে বাড়ে আর km শুধু রৈখিক হারে, তাই বড় k-তে S^k > km. বিরোধ, তাই S ≤ 1. ∎ — ঘাত বনাম রৈখিক

দুই উপপাদ্য মিলিয়ে: যেকোনো UD code-এর দৈর্ঘ্য দিয়ে একটি prefix code বানানো যায় (Kraft-এর বিপরীত)। তাই গড় দৈর্ঘ্য কমানোর প্রশ্নে prefix code-ই যথেষ্ট। এই জুটিকে Kraft–McMillan অসমতা বলে। নিচের ব্লক এর তিনটি কাজ করে: Kraft যোগ গোনে, বিপরীত নির্মাণ চালায়, আর বাজারঘরের code-এর tree ধরে একটি bit string decode করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from fractions import Fraction
def kraft(lengths):
    return sum(Fraction(1, 2 ** l) for l in lengths)
def code_from_lengths(lengths):          # converse of Kraft: build a prefix code
    words, acc = [], Fraction(0)
    for l in sorted(lengths):
        words.append(format(int(acc * 2 ** l), f"0{l}b"))  # first l bits of acc
        acc += Fraction(1, 2 ** l)
    return words
for ls in [(1, 2, 3, 3), (2, 2, 2, 3), (1, 2, 2, 3)]:
    k = kraft(ls)
    print(ls, "Kraft sum", k, "->", code_from_lengths(ls) if k <= 1 else "impossible")
def build_tree(codes):                   # binary trie as nested dicts
    root = {}
    for sym, word in codes.items():
        node = root
        for bit in word[:-1]:
            node = node.setdefault(bit, {})
        node[word[-1]] = sym             # the leaf holds the symbol
    return root
def decode(bits, root):
    out, node = [], root
    for bit in bits:
        node = node[bit]
        if isinstance(node, str):        # reached a leaf: emit, restart at root
            out.append(node); node = root
    assert node is root, "bits ended inside a codeword"
    return "".join(out)
codes = {"P": "00", "S": "01", "D": "11", "N": "100", "R": "1010", "C": "1011"}
tree = build_tree(codes)
print(decode("1000111101011", tree))
print(decode("1111001010", tree))

(1, 2, 3, 3) Kraft sum 1 -> ['0', '10', '110', '111']
(2, 2, 2, 3) Kraft sum 7/8 -> ['00', '01', '10', '110']
(1, 2, 2, 3) Kraft sum 9/8 -> impossible
NSDRD
DDPR

৪ · গড় দৈর্ঘ্য আর Huffman-এর algorithm

চিহ্ন a_i-এর সম্ভাবনা p_i (এখানে গণনা/১০০) আর codeword-দৈর্ঘ্য l_i হলে প্রতি চিহ্নে গড় বিট

L(c) = ∑_i p_i l_i,

যা আসলে random চিহ্নের codeword-দৈর্ঘ্যের expected value (পর্ব ৪০)। একে expected codeword length বলে। সমস্যাটি তাহলে: Kraft মানে এমন ধনাত্মক পূর্ণসংখ্যা l_i বেছে ∑ p_i l_i সবচেয়ে কম করা। পূর্ণসংখ্যার এই অপ্টিমাইজেশন দেখতে কঠিন, কিন্তু David Huffman ১৯৫২ সালে একটি সরল greedy উত্তর দেন।

“সবচেয়ে কম ওজনের দুটি” বারবার তোলার কাজ একটি priority queue (min-heap) দিয়ে O(n log n) সময়ে হয়; বাস্তবায়ন আর জটিলতার বিস্তারিত DSA কোর্সের পর্ব ৫১-এ আর heap DSA কোর্সের পর্ব ২৩-এ। আমরা এখানে হাতে চালাই, তারপর প্রমাণ করি কেন এটি সেরা।

1R5 C8 N12 P15 S24 D362R5 + C8 → 133N12 + 13 → 254P15 + S24 → 39525 + D36 → 61639 + 61 → 100 (root)7বাঁয়ে 0, ডানে 1: পড়া

নিচের ব্লক heapq দিয়ে একই কাজ করে, codeword ছাপে, আর গড় দৈর্ঘ্যকে entropy (§৬) আর fixed-length-এর সঙ্গে তুলনা করে।

import heapq, math
from fractions import Fraction
freq = {"D": 36, "S": 24, "P": 15, "N": 12, "C": 8, "R": 5}   # per 100 statuses
heap = [(w, i, s) for i, (s, w) in enumerate(freq.items())]
heapq.heapify(heap); nxt = len(heap)
while len(heap) > 1:
    a = heapq.heappop(heap)              # least frequent tree
    b = heapq.heappop(heap)              # second least
    print("merge", a[0], "+", b[0], "=", a[0] + b[0])
    heapq.heappush(heap, (a[0] + b[0], nxt, (a[2], b[2]))); nxt += 1
codes = {}
def walk(t, path):                       # left edge 0, right edge 1
    if isinstance(t, str):
        codes[t] = path
    else:
        walk(t[0], path + "0"); walk(t[1], path + "1")
walk(heap[0][2], "")
print(sorted(codes.items(), key=lambda kv: (len(kv[1]), kv[1])))
total = sum(freq.values())
L = sum(freq[s] * len(codes[s]) for s in freq) / total
H = -sum(w / total * math.log2(w / total) for w in freq.values())
print(f"Huffman L = {L:.2f} bits, entropy H = {H:.4f}, fixed = 3 bits")
print("Kraft sum:", sum(Fraction(1, 2 ** len(c)) for c in codes.values()))
words = list(codes.values())
print("prefix-free:", not any(u != v and v.startswith(u) for u in words for v in words))
print("1000 statuses:", round(L * 1000), "bits instead of", 3 * 1000)

merge 5 + 8 = 13
merge 12 + 13 = 25
merge 15 + 24 = 39
merge 25 + 36 = 61
merge 39 + 61 = 100
[('P', '00'), ('S', '01'), ('D', '11'), ('N', '100'), ('R', '1010'), ('C', '1011')]
Huffman L = 2.38 bits, entropy H = 2.3100, fixed = 3 bits
Kraft sum: 1
prefix-free: True
1000 statuses: 2380 bits instead of 3000

একটি বার্তা encode আর decode করে পুরো চক্রটি দেখা যাক। বার্তা: N, S, D, R, D (একটি অর্ডারের নতুন থেকে ফেরত পর্যন্ত কয়েকটি লগ-লাইন)।

1N 100 · S 01 · D 11 · R 10102encode: 10001111010113decode 1, 0, 0 → N4decode 0, 1 → S5decode 1, 1 → D6decode 1, 0, 1, 0 → R7decode 1, 1 → D, শেষ

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

Greedy পদ্ধতি সবসময় সেরা উত্তর দেয় না (DSA কোর্সের পর্ব ৫০-এ coin change-এর উদাহরণ)। তাই Huffman-এর জন্য প্রমাণ লাগবে। ধরে নিন n ≥ 2, প্রতিটি p_i > 0, আর x, y দুটি সবচেয়ে কম সম্ভাবনার চিহ্ন: p_x ≤ p_y ≤ বাকি সবার সম্ভাবনা। সর্বোত্তম code অবশ্যই আছে: Lemma ২.২ অনুযায়ী সর্বোত্তম tree full, আর n leaf-এর full binary tree সসীম সংখ্যক।

1. যেকোনো সর্বোত্তম tree T নিন; সবচেয়ে বেশি গভীরতা d. গভীরতা d-এর একটি leaf a নিন। T full বলে a-এর parent-এর আরেকটি সন্তান b আছে, আর b-ও leaf, কারণ b-এর নিচে কিছু থাকলে গভীরতা d ছাড়াত। — Lemma ২.২
2. নাম এমনভাবে দিন যাতে p_a ≤ p_b. x আর y সবচেয়ে বিরল, তাই p_x ≤ p_a আর p_y ≤ p_b. — x, y-এর সংজ্ঞা
3. T-তে x আর a-এর জায়গা বদল করুন। গড় দৈর্ঘ্যের পরিবর্তন = p_xd + p_al_x − p_xl_x − p_ad = −(p_a − p_x)(d − l_x) ≤ 0, কারণ p_a ≥ p_x আর d ≥ l_x. — exchange argument
4. একইভাবে y আর b বদল করুন; পরিবর্তন −(p_b − p_y)(d − l_y) ≤ 0. (x = b বা y = a হলে বিশেষ ক্ষেত্র: তখন একটি বদলেই x, y ওই দুই জায়গায় চলে আসে, বা কোনো বদলই লাগে না।) — একই হিসাব
5. নতুন tree-র গড় দৈর্ঘ্য T-এর চেয়ে বেশি নয়, আর T সর্বোত্তম, তাই নতুনটিও সর্বোত্তম; তাতে x, y গভীরতা d-তে ভাই। ∎

প্রমাণ: z-এর গভীরতা l_z হলে x আর y-এর গভীরতা l_z + 1, বাকি সবার অপরিবর্তিত। তাই L(T) − L(T′) = p_x(l_z + 1) + p_y(l_z + 1) − (p_x + p_y)l_z = p_x + p_y. ∎

প্রমাণ n-এর ওপর induction দিয়ে।

1. ভিত্তি n = 2: প্রতিটি codeword অন্তত 1 bit, তাই L ≥ p₁ + p₂ = 1; Huffman দেয় 0 আর 1, L = 1. — base case
2. Hypothesis: n − 1টি চিহ্নের প্রতিটি alphabet-এ Huffman সর্বোত্তম। — inductive hypothesis
3. n চিহ্নে Huffman প্রথমে x আর y জোড়া দেয়, তারপর বাকি কাজটি ঠিক A′-এর ওপর Huffman চালানোর মতো, যেখানে z-এর ওজন p_x + p_y. সেই tree H′; শেষে z খুলে x, y বসালে Huffman-এর tree H. Lemma ৫.২: L(H) = L(H′) + p_x + p_y. — algorithm-এর গঠন
4. Lemma ৫.১ থেকে একটি সর্বোত্তম tree T, যাতে x, y ভাই। তাদের parent-কে leaf z বানালে A′-এর একটি tree T′, আর L(T′) = L(T) − p_x − p_y. — Lemma ৫.১ আর ৫.২
5. Hypothesis অনুযায়ী L(H′) ≤ L(T′). তাই L(H) = L(H′) + p_x + p_y ≤ L(T′) + p_x + p_y = L(T). T সর্বোত্তম, তাই H-ও সর্বোত্তম। ∎ — তুলনা

প্রমাণ থেকে একটি দরকারি সূত্রও আসে। Lemma ৫.২ বারবার প্রয়োগ করলে, প্রতিটি জোড়ায় নতুন node-এর ওজন একবার করে L-এ যোগ হয়:

Huffman-এর মোট খরচ ∑ w_i l_i = সব জোড়ায় তৈরি node-এর ওজনের যোগ।

বাজারঘরে 13 + 25 + 39 + 61 + 100 = 238, যা stepper-এ দেখেছেন। হাতে অঙ্ক করার সময় codeword না পড়েই L বের করার এটি দ্রুত পথ।

Tie আর একাধিক Huffman tree

দুটি ওজন সমান হলে কোনটি আগে তুলবেন, algorithm তা বলে না। ওজন a 1, b 1, c 2, d 2 (মোট 6) নিন। প্রথমে a + b = 2. তখন তিনটি 2: c, d আর নতুন node. যদি c আর d জোড়া দেন, সব codeword-এর দৈর্ঘ্য 2: দৈর্ঘ্য-ভেক্টর (2, 2, 2, 2). যদি নতুন node আর c জোড়া দেন, তবে দৈর্ঘ্য a 3, b 3, c 2, d 1. দুটি tree আলাদা, দৈর্ঘ্যও আলাদা, এমনকি height-ও (2 বনাম 3), অথচ খরচ একই: 1·2 + 1·2 + 2·2 + 2·2 = 12 আর 1·3 + 1·3 + 2·2 + 2·1 = 12. এটি কাকতালীয় নয়: উপপাদ্য ৫.৩-এর প্রমাণে কোনো tie-ভাঙার নিয়ম ব্যবহার হয়নি, তাই যেকোনো পছন্দেই ফল সর্বোত্তম, আর সব সর্বোত্তমের খরচ সমান। তাই Huffman tree “অনন্য” নয়, কিন্তু তার গড় দৈর্ঘ্য অনন্য। বাস্তবের ফরম্যাটে encoder আর decoder-কে একই tree মানতে হয়, তাই canonical Huffman code শুধু দৈর্ঘ্য থেকে একটি নির্দিষ্ট নিয়মে codeword বানায়, ঠিক Kraft-এর নির্মাণের মতো।

প্রমাণে বিশ্বাস আছে, তবু যাচাই করা যাক। নিচের ব্লক ১৫০টি এলোমেলো ছোট alphabet-এ (২ থেকে ৬টি চিহ্ন) Kraft মানে এমন প্রতিটি দৈর্ঘ্য-ভেক্টর পরীক্ষা করে সবচেয়ে কম খরচ বের করে, আর Huffman-এর খরচের সঙ্গে মেলায়। দৈর্ঘ্য 1 থেকে n − 1 পর্যন্ত দেখাই যথেষ্ট, কারণ n leaf-এর full tree-র কোনো leaf n − 1-এর বেশি গভীর নয়।

import heapq, math, random
from itertools import product
def huffman_cost(w):                     # sum of all merged weights = sum w*l
    h = list(w); heapq.heapify(h); cost = 0
    while len(h) > 1:
        a, b = heapq.heappop(h), heapq.heappop(h)
        cost += a + b; heapq.heappush(h, a + b)
    return cost
def best_by_kraft(w):                    # try every length vector, Kraft <= 1
    n = len(w); m = n - 1; best = None
    for ls in product(range(1, n), repeat=n):
        if sum(2 ** (m - l) for l in ls) <= 2 ** m:
            c = sum(x * l for x, l in zip(w, ls))
            if best is None or c < best:
                best = c
    return best
random.seed(68); gap = 0; trials = 150
for t in range(trials):
    w = [random.randint(1, 20) for _ in range(random.randint(2, 6))]
    cost = huffman_cost(w)
    assert cost == best_by_kraft(w)      # Huffman is optimal
    L = cost / sum(w)
    H = -sum(x / sum(w) * math.log2(x / sum(w)) for x in w)
    assert H <= L < H + 1                # source coding bounds
    gap = max(gap, L - H)
print(trials, "random alphabets: Huffman = brute-force optimum")
print("H <= L < H + 1 held; largest L - H:", round(gap, 4))
print("weights 1,1,2,2: Huffman cost", huffman_cost([1, 1, 2, 2]))
print("lengths (2,2,2,2) cost", 1*2 + 1*2 + 2*2 + 2*2,
      "| lengths (3,3,2,1) cost", 1*3 + 1*3 + 2*2 + 2*1)

150 random alphabets: Huffman = brute-force optimum
H <= L < H + 1 held; largest L - H: 0.7136
weights 1,1,2,2: Huffman cost 12
lengths (2,2,2,2) cost 12 | lengths (3,3,2,1) cost 12

৬ · Entropy — কোনো code যার নিচে নামতে পারে না

Huffman সর্বোত্তম, কিন্তু সেই সর্বোত্তম মান কত? একটি সরল সূত্র প্রায় ঠিক উত্তর দেয়। সম্ভাবনা p-এর একটি ঘটনা ঘটলে তার information content −log₂ p bit: ঘটনা যত বিরল, তত বেশি “খবর”। গড় নিলে

H(p) = −∑_i p_i log₂ p_i

যাকে Shannon-এর entropy বলে (log ভিত্তি 2, তাই একক bit ধরা হয়)। বাজারঘরে D-এর −log₂ 0.36 ≈ 1.474 আর R-এর −log₂ 0.05 ≈ 4.322, আর H ≈ 2.3100. Entropy-র ধারণা আর অনুভব AI Foundations কোর্সের পর্ব ৩৮-এ আছে; এখানে আমরা code-এর সঙ্গে তার সম্পর্ক প্রমাণ করি।

1. সব x > 0-এর জন্য ln x ≤ x − 1, সমতা শুধু x = 1-এ (y = ln x বক্ররেখা x = 1-এ তার স্পর্শক y = x − 1-এর নিচে থাকে)। — ln-এর concavity
2. x = q_i/p_i বসিয়ে p_i দিয়ে গুণ করে যোগ করুন: ∑ p_i ln(q_i/p_i) ≤ ∑ (q_i − p_i) = ∑ q_i − 1 ≤ 0. — যোগ
3. বাঁ দিক = ∑ p_i ln q_i − ∑ p_i ln p_i; ln 2 দিয়ে ভাগ করে সাজালে দাবিটি আসে। সমতার জন্য ধাপ ১-এ প্রতিটি q_i/p_i = 1 লাগে। ∎

1. (ক) q_i = 2^−l_i নিন। McMillan অনুযায়ী ∑ q_i ≤ 1, তাই Gibbs থেকে H ≤ −∑ p_i log₂ 2^−l_i = ∑ p_i l_i = L. সমতা ⇔ p_i = q_i. — Lemma ৬.১
2. (খ) l_i = ⌈−log₂ p_i⌉ নিন (Shannon-এর দৈর্ঘ্য)। তাহলে l_i ≥ −log₂ p_i, তাই 2^−l_i ≤ p_i, আর ∑ 2^−l_i ≤ ∑ p_i = 1. Kraft-এর বিপরীত এই দৈর্ঘ্যের prefix code দেয়। — উপপাদ্য ৩.১
3. ⌈t⌉ < t + 1, তাই L = ∑ p_i l_i < ∑ p_i(−log₂ p_i + 1) = H + 1. Huffman সর্বোত্তম, তাই L_Huff ≤ এই L < H + 1. ∎ — উপপাদ্য ৫.৩

বাজারঘরে Shannon-এর দৈর্ঘ্য D 2, S 3, P 3, N 4, C 4, R 5, আর তার L = 2.94: সীমার ভেতরে, কিন্তু Huffman-এর 2.38-এর চেয়ে অনেক খারাপ। তাই Shannon-এর দৈর্ঘ্য প্রমাণের হাতিয়ার, সেরা code নয়। সমতার শর্তটি দেখার মতো: সম্ভাবনা (1/2, 1/4, 1/8, 1/8) হলে Huffman দেয় 0, 10, 110, 111, আর L = H = 1.75 ঠিক সমান। সম্ভাবনা 2-এর ঘাত না হলে কিছু ফাঁক থাকবেই।

৭ · বাস্তবে Huffman — block, সীমা আর ফরম্যাট

L < H + 1-এর “+1” বিরল-ঘটনা-ভরা উৎসে বড় সমস্যা। ধরুন বাজারঘরের একটি লগ-কলামে 90% লাইনে x (“ঠিক আছে”) আর 10% লাইনে y (“সমস্যা”)। H ≈ 0.4690 bit, কিন্তু অক্ষর-ধরে যেকোনো code-এ প্রতিটি চিহ্ন অন্তত 1 bit, তাই L = 1, entropy-র দ্বিগুণের বেশি। প্রতিকার block coding: দুটি চিহ্ন একসঙ্গে একটি নতুন “চিহ্ন” ধরুন (xx, xy, yx, yy; সম্ভাবনা 0.81, 0.09, 0.09, 0.01) আর তার ওপর Huffman চালান। scratch-এ হিসাব: জোড়ায় প্রতি মূল চিহ্নে 0.645 bit, তিনটির block-এ 0.5327 bit. স্বাধীন চিহ্নের উৎসে k-এর block-এ উপপাদ্য ৬.২ দেয় kH ≤ L_k < kH + 1, তাই প্রতি চিহ্নে

H ≤ L_k/k < H + 1/k,

আর k বাড়লে গড় দৈর্ঘ্য entropy-র যত কাছে চান তত কাছে আসে। এটাই Claude Shannon-এর ১৯৪৮ সালের “A Mathematical Theory of Communication” প্রবন্ধের source coding উপপাদ্যের সরল রূপ: entropy হলো lossless সংকোচনের মৌলিক সীমা। দাম হলো code table-এর আকার, যা k-এর সঙ্গে ঘাতের হারে বাড়ে (দুই চিহ্নের উৎসে 2^kটি সম্ভাব্য block থাকে)। এই কারণে arithmetic coding আর ANS-এর মতো পদ্ধতি পুরো বার্তাকে একসঙ্গে code করে, বিশাল table ছাড়াই ভগ্নাংশ-বিটের দক্ষতা পায়।

আরেকটি সীমা গণনার। পর্ব ৩২-এ প্রমাণ করেছেন: কোনো lossless compression প্রতিটি ফাইল ছোট করতে পারে না। Huffman এর ব্যতিক্রম নয়: সব চিহ্ন সমান সম্ভাবনার হলে (যেমন ইতিমধ্যে সংকুচিত বা এলোমেলো ডেটা) কোনো লাভ নেই, আর code table পাঠানোর খরচে ফাইল বড়ও হতে পারে। Huffman লাভ দেয় শুধু তখন, যখন চিহ্নের সম্ভাবনা অসমান।

বাস্তবের ফরম্যাটে Huffman প্রায়ই অন্য কৌশলের সঙ্গে বসে। ব্যাপকভাবে নথিভুক্ত উদাহরণ DEFLATE (RFC 1951, ১৯৯৬), যা zip, gzip আর PNG-এর সংকোচন: আগে LZ77 দিয়ে পুনরাবৃত্ত অংশকে “কত পেছনে, কত লম্বা” দিয়ে বদলায়, তারপর ফলাফলকে canonical Huffman code-এ লেখে, আর ফাইলে শুধু codeword-দৈর্ঘ্য পাঠায়। ওই নির্দেশিকায় codeword-দৈর্ঘ্য সর্বোচ্চ 15 bit-এ সীমিত, তাই encoder-কে কখনো “দৈর্ঘ্য-সীমিত” code বানাতে হয়, যা খাঁটি Huffman-এর চেয়ে সামান্য খারাপ হতে পারে। প্রচলিত JPEG ছবির baseline রূপেও শেষ ধাপে Huffman coding ব্যবহৃত হয় বলে মানদণ্ডে বর্ণিত (arithmetic coding সেখানে ঐচ্ছিক বিকল্প)। বিস্তারিত বাস্তবায়ন DSA কোর্সের পর্ব ৫১-এ।

৮ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: হাতে Huffman

পাঁচটি চিহ্নের গণনা a 10, b 15, c 30, d 16, e 29, মোট 100. Huffman code, গড় দৈর্ঘ্য, আর fixed-length-এর তুলনায় সাশ্রয় বের করুন।

1. জোড়া: a 10 + b 15 = 25; d 16 + 25 = 41; e 29 + c 30 = 59; 41 + 59 = 100.
2. দৈর্ঘ্য: d, e, c → 2; a, b → 3. একটি code: d 00, a 010, b 011, e 10, c 11 (Kraft: 3/4 + 2/8 = 1).
3. খরচ: জোড়ার যোগ 25 + 41 + 59 + 100 = 225, তাই L = 2.25 bit. Fixed-length-এ ⌈log₂ 5⌉ = 3 bit, সাশ্রয় 25%. Entropy H ≈ 2.2047, সীমা মেলে (scratch-এ heapq দিয়ে মেলানো)।

অঙ্ক ২: Kraft দিয়ে সম্ভব-অসম্ভব

(ক) দৈর্ঘ্য 1, 2, 3, 3, 3-এর binary prefix code আছে কি? (খ) 1, 3, 3, 3, 3?

1. (ক) 1/2 + 1/4 + 3/8 = 9/8 > 1, তাই নেই; McMillan অনুযায়ী এমন UD code-ও নেই।
2. (খ) 1/2 + 4/8 = 1, তাই আছে: Kraft-এর নির্মাণে 0, 100, 101, 110, 111 (scratch-এ code_from_lengths দিয়ে মেলানো)।

অঙ্ক ৩: সমতার ক্ষেত্র

সম্ভাবনা 1/2, 1/4, 1/8, 1/16, 1/32, 1/32. Huffman-এর দৈর্ঘ্য 1, 2, 3, 4, 5, 5, আর L = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + 5/32 = 1.9375 = H, কারণ প্রতিটি সম্ভাবনা 2-এর ঋণাত্মক ঘাত (উপপাদ্য ৬.২-এর সমতা)।

প্রমাণের ভুল ধরুন: “Kraft মানলেই prefix code”

একজন লিখলেন: “Code {0, 01}-এর দৈর্ঘ্য 1 আর 2, Kraft যোগ 1/2 + 1/4 = 3/4 ≤ 1. Kraft-এর উপপাদ্য অনুযায়ী তাই এটি একটি prefix code.”

ভুল কোথায়: Kraft-এর বিপরীত বলে, এই দৈর্ঘ্যের কোনো একটি prefix code আছে (যেমন {0, 10}); প্রদত্ত নির্দিষ্ট code-টি prefix কি না, সে বিষয়ে কিছু বলে না। এখানে 0 হলো 01-এর prefix, তাই {0, 01} prefix code নয় (যদিও UD, কারণ কোনো codeword অন্যটির শেষাংশ নয়)। অসমতা দৈর্ঘ্যের শর্ত, codeword-এর নয়; “অস্তিত্ব” আর “এটিই সেটি” গুলিয়ে ফেলা একটি পরিচিত যুক্তির ভুল।

৯ · AI-এর যুগে — Huffman-এর হিসাব আর প্রমাণ যাচাই

AI সহকারী Huffman-এর ধাপ সাধারণত ঠিক বর্ণনা করে, কিন্তু হাতের হিসাবে, শর্তে আর প্রমাণের দিকনির্ণয়ে ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি জোড়ার ধাপে নতুন node-ও heap-এ ফিরেছে, আর সবচেয়ে হালকা দুটিই তোলা হয়েছে
• Codeword prefix-free, Kraft যোগ ভগ্নাংশে গুনে দেখেছি
• ∑ w·l আর জোড়ার ওজনের যোগ মিলেছে, আর L ≥ H
• প্রমাণে উপপাদ্যের শর্ত (prefix/UD, ধনাত্মক সম্ভাবনা) স্পষ্ট, আর converse গুলিয়ে যায়নি
• ছোট উদাহরণে brute force দিয়ে সর্বোত্তম মান নিজে চালিয়ে মিলিয়েছি
• নাম, সাল আর ফরম্যাটের দাবি বিশ্বস্ত পাঠ্যবই বা মূল নির্দেশিকায় মিলিয়েছি

Huffman-এর উত্তর যাচাই সহজ, কারণ তিনটি স্বাধীন সংখ্যা মিলতে হয়: ∑ w·l, জোড়ার ওজনের যোগ, আর brute force-এর সর্বনিম্ন। তিনটি না মিললে উত্তরে ভুল আছে।