Huffman Coding
হাফম্যান কোডিং
Symbol frequency অনুযায়ী কম-বেশি bit-এর prefix-free code বানানো greedy algorithm — সবচেয়ে rare দুই symbol merge করে করে tree দাঁড়ায়।
also: huffman code, huffman tree, huffman compression
Prefix-free মানে কোনো codeword আরেকটার শুরু নয় — decode ambiguous হয় না, separator লাগে না।
Algorithm: প্রতিটা symbol এক leaf; priority queue থেকে lowest-frequency দুই tree তুলে parent-এর তলায় জোড়া, parent ফেরত ঢোকাও — শেষ পর্যন্ত। Root-to-leaf path-ই codeword।
Frequent symbol root-এর কাছে থাকে, rare গুলো গভীরে — total bits কমে। Fixed-length coding-এর চেয়ে entropy H(X)-এর খুব কাছাকাছি (প্রতি symbol-এ ≤ 1 bit extra) — greedy-র optimality proof এখানেই।
ZIP/GZIP (DEFLATE), JPEG, MP3 — ভেতরে সবাই হাফম্যান-জাতীয় stage ব্যবহার করে।