Huffman Coding

Setiap kali kita mengompres file teks dengan gzip atau mengirim gambar PNG, kemungkinan besar algoritma di balik layar adalah turunan Huffman coding. Diperkenalkan David Huffman pada 1952, algoritma ini membangun prefix code optimal — kode di mana tidak ada simbol yang merupakan prefix dari simbol lain — berdasarkan frekuensi kemunculan. Simbol yang sering muncul mendapat kode pendek, simbol yang jarang mendapat kode panjang. Pada Chapter ini kita akan membedah mekanisme Huffman coding, membangun pohon Huffman dengan min-heap, dan menghitung rasio kompresi yang dihasilkan.

Aturan: Kode Prefix Optimal berdasarkan Frekuensi #

Diberikan n simbol dengan frekuensi freq[i]. Tujuan: bangun kode biner prefix-free sehingga total panjang stream terkompresi minimum. Total panjang = Σ freq[i] · length(code[i]).

Strategi greedy Huffman:

1. Buat leaf node untuk setiap simbol dengan bobot = frekuensi.
2. Masukkan semua leaf ke min-heap.
3. Selama heap berisi lebih dari satu node:
   • Pop dua node dengan frekuensi terkecil.
   • Buat internal node baru dengan frekuensi = jumlah keduanya.
   • Jadikan dua node tadi sebagai anak kiri dan kanan.
   • Push internal node ke heap.
4. Node yang tersisa adalah root pohon Huffman.

Greedy choice = dua frekuensi terkecil. Mengapa? Dua simbol paling jarang harus berada paling dalam di pohon agar kodenya paling panjang — penalti-nya paling kecil karena frekuensinya rendah.

Mekanisme: Min-Heap + Merge Berulang #

Setiap iterasi menggabungkan dua node terkecil. Setiap internal node merepresentasikan sub-pohon dengan total frekuensi tertentu. Total panjang kode terkompresi = jumlah bobot semua internal node (atau ekuivalen: Σ freq[i] · depth(i)).

Contoh Klasik CLRS #

Mari kita pakai contoh dari CLRS: 6 karakter dengan frekuensi sebagai berikut.

Total karakter = 100. Dengan fixed-length encoding 3 bit (karena ceil(log2(6)) = 3), total panjang = 100 × 3 = 300 bit. Huffman coding mampu mengompresi hingga 224 bit — penghematan ~25%.

Implementasi C++ #

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

struct HuffmanNode {
    char ch;
    int freq;
    int id;                 // tiebreaker untuk determinisme
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(char c, int f, int tag)
        : ch(c), freq(f), id(tag), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(const HuffmanNode* a, const HuffmanNode* b) const {
        if (a->freq != b->freq) return a->freq > b->freq;
        return a->id > b->id; // lexicographic order by id
    }
};

void generateCodes(HuffmanNode* root, const std::string& code,
                   std::vector<std::pair<char,std::string>>& table) {
    if (!root) return;
    if (!root->left && !root->right) {
        table.push_back({root->ch, code.empty() ? "0" : code});
        return;
    }
    generateCodes(root->left,  code + "0", table);
    generateCodes(root->right, code + "1", table);
}

void freeTree(HuffmanNode* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int main() {
    // Input: pasangan (karakter, frekuensi)
    std::vector<std::pair<char,int>> input = {
        {'f', 5}, {'e', 9}, {'c', 12},
        {'b', 13}, {'d', 16}, {'a', 45}
    };

    // Bangun min-heap berisi leaf node
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
    int idCounter = 0;
    for (auto [ch, fr] : input) {
        pq.push(new HuffmanNode(ch, fr, idCounter++));
    }

    // Iteratif: gabungkan dua node terkecil sampai tersisa satu
    while (pq.size() > 1) {
        HuffmanNode* a = pq.top(); pq.pop();
        HuffmanNode* b = pq.top(); pq.pop();
        auto* merged = new HuffmanNode('\0', a->freq + b->freq, idCounter++);
        merged->left = a;
        merged->right = b;
        pq.push(merged);
    }

    HuffmanNode* root = pq.top();
    std::vector<std::pair<char,std::string>> table;
    generateCodes(root, "", table);

    // Sort table by frequency descending untuk tampilan
    std::vector<std::pair<char,int>> freqs(input.begin(), input.end());
    std::sort(freqs.begin(), freqs.end(),
              [](const auto& x, const auto& y) { return x.second > y.second; });

    std::cout << "Karakter | Freq | Kode Huffman | Bit\n";
    std::cout << "---------+------+--------------+----\n";
    int totalBits = 0;
    int totalChars = 0;
    for (auto [ch, fr] : freqs) {
        std::string code;
        for (auto& p : table) if (p.first == ch) { code = p.second; break; }
        std::cout << "   " << ch << "    | "
                  << fr << "   | " << code
                  << std::string(14 - code.size(), ' ')
                  << " | " << (fr * (int)code.size()) << '\n';
        totalBits += fr * (int)code.size();
        totalChars += fr;
    }

    int fixedBits = totalChars * 3; // ceil(log2(6)) = 3
    std::cout << "\nTotal bit terkompresi  : " << totalBits << '\n';
    std::cout << "Total bit fixed 3-bit  : " << fixedBits << '\n';
    std::cout << "Rasio kompresi         : "
              << (double)(fixedBits - totalBits) / fixedBits * 100 << "%\n";

    freeTree(root);
    return 0;
}

Output yang Dihasilkan:

Karakter | Freq | Kode Huffman | Bit
---------+------+--------------+----
   a    | 45   | 0             | 45
   d    | 16   | 111           | 48
   b    | 13   | 101           | 39
   c    | 12   | 100           | 36
   e    | 9    | 1101          | 36
   f    | 5    | 1100          | 20

Total bit terkompresi  : 224
Total bit fixed 3-bit  : 300
Rasio kompresi         : 25.3333%

Bedah Kode Baris-per-Baris #

1. struct HuffmanNode { char ch; int freq; int id; HuffmanNode* left; HuffmanNode* right; };: node pohon Huffman. Leaf punya ch valid; internal node punya ch = '\0'. Field id menjamin urutan pop deterministik saat ada tie frekuensi.
2. struct Compare { bool operator()(...) const { ... } };: komparator min-heap. Pop node dengan frekuensi terkecil; bila tie, pop dengan id terkecil. Tanpa tiebreaker, hasil bisa non-deterministik antar run.
3. for (auto [ch, fr] : input) pq.push(new HuffmanNode(...));: bangun leaf untuk setiap karakter dan masukkan ke min-heap. Kompleksitas O(n) untuk membangun heap.
4. while (pq.size() > 1): loop hingga tersisa satu node (root). Tiap iterasi mengurangi ukuran heap sebesar satu.
5. HuffmanNode* a = pq.top(); pq.pop();: ambil dua node terkecil. Inilah greedy choice Huffman.
6. auto* merged = new HuffmanNode('\0', a->freq + b->freq, idCounter++);: buat internal node dengan frekuensi = jumlah dua anak. Inilah cara Huffman membangun total: jumlah semua frekuensi mengalir ke root.
7. merged->left = a; merged->right = b; pq.push(merged);: jadikan dua node tadi anak kiri dan kanan, lalu push kembali. Konvensi: kiri = bit 0, kanan = bit 1.
8. generateCodes(root, "", table): traverse pohon untuk membangun kode tiap leaf. Kode leaf = path dari root, di mana 0 untuk kiri dan 1 untuk kanan.
9. if (!root->left && !root->right): deteksi leaf. Hanya leaf yang punya kode valid — internal node tidak punya kode sendiri.
10. Output: karakter a (paling sering, 45 kali) dapat kode 0 (1 bit). Karakter f (paling jarang, 5 kali) dapat kode 1100 (4 bit). Pola ini mencerminkan greedy: frekuensi tinggi → kode pendek.
11. Total 224 bit: 45·1 + 16·3 + 13·3 + 12·3 + 9·4 + 5·4 = 224. Bandingkan dengan fixed 3-bit 100·3 = 300. Penghematan 76 bit = 25.33%.

Visualisasi Pohon Huffman #

Pohon yang dibangun dari contoh di atas:

Daun paling dalam (f dan e, depth 4) adalah dua karakter dengan frekuensi terendah. Daun paling dangkal (a, depth 1) adalah karakter dengan frekuensi tertinggi. Inilah inti optimalitas Huffman.

Trace Step-by-Step #

Min-heap awal: [f(5), e(9), c(12), b(13), d(16), a(45)].

Setelah 5 iterasi, tersisa satu node = root. Total frekuensi root = 5+9+12+13+16+45 = 100, sama dengan total karakter input.

Kompleksitas #

Huffman optimal di antara semua prefix code biner untuk distribusi frekuensi yang diketahui. Pembuktian optimality menggunakan exchange argument.

Komparasi dengan Encoding Lain #

Aplikasi Nyata #

• gzip / zlib / DEFLATE: kombinasi LZ77 + Huffman — basis dari HTTP compression.
• PNG: filter + DEFLATE.
• JPEG: Huffman coding setelah DCT dan quantization.
• MP3: Huffman coding untuk quantized spectral coefficients.
• Barcode: code 39, code 128 menggunakan varian prefix code.
• Telekomunikasi: PSTN modem menggunakan adaptif Huffman.

Variasi dan Penerapan #

• Canonical Huffman: kode dihasilkan dengan struktur khusus sehingga tabel decode ringkas. Dipakai di JPEG dan deflate.
• Adaptive Huffman: tabel diperbarui saat stream berjalan, cocok untuk streaming data.
• Length-limited Huffman: batasi panjang kode maksimum L (mis. L = 15 untuk DEFLATE). Pakai package-merge algorithm.
• Ternary Huffman: gunakan base-3 (kode trits) — berguna bila channel bisa mengirim 3 simbol.

Ringkasan #

• Huffman coding membangun prefix code optimal berdasarkan frekuensi simbol.
• Greedy choice: gabungkan dua node dengan frekuensi terkecil pada setiap iterasi.
• Implementasi klasik memakai min-heap dengan kompleksitas O(n log n).
• Karakter sering → kode pendek; karakter jarang → kode panjang.
• Contoh CLRS: 6 karakter total 100, fixed 300 bit → Huffman 224 bit (penghematan 25%).
• Aplikasi luas: gzip, PNG, JPEG, MP3, telekomunikasi.

Chapter berikutnya akan membahas Job Scheduling — penjadwalan tugas dengan deadline dan profit, di mana greedy memanfaatkan Disjoint Set Union untuk menemukan slot kosong tercepat.