Rangkuman: Huffman Coding

1. Pengertian

Huffman Coding adalah algoritma kompresi data lossless (tanpa kehilangan data) yang menggunakan pendekatan Greedy. Algoritma ini menghasilkan kode variabel-panjang untuk setiap karakter dalam sebuah pesan, di mana karakter yang paling sering muncul diberikan kode yang lebih pendek, dan karakter yang jarang muncul diberikan kode yang lebih panjang. Tujuannya adalah untuk meminimalkan panjang rata-rata dari kode yang dihasilkan, sehingga ukuran data keseluruhan dapat dikurangi.

2. Konsep Dasar & Pendekatan Greedy

Huffman Coding bekerja dengan membangun pohon biner khusus yang disebut Pohon Huffman. Pohon ini dibangun dari bawah ke atas (bottom-up) dengan menggabungkan node-node berfrekuensi terendah secara berulang.

Langkah-langkah Algoritma Greedy:

1. Hitung frekuensi kemunculan setiap karakter unik dalam data input.
2. Buat daftar node (daun) untuk setiap karakter, di mana setiap node berisi karakter dan frekuensinya.
3. Masukan semua node ini ke dalam Priority Queue (min-heap) yang diurutkan berdasarkan frekuensi (frekuensi terkecil di prioritas tertinggi).
4. Selama ada lebih dari satu node di Priority Queue:
   • Ambil dua node dengan frekuensi terkecil dari Priority Queue.
   • Buat node internal baru yang menjadi induk dari dua node yang diambil. Frekuensi node induk adalah jumlah frekuensi kedua anaknya.
   • Tambahkan node induk ini kembali ke Priority Queue.
5. Node terakhir yang tersisa di Priority Queue adalah akar dari Pohon Huffman.
6. Jelajahi Pohon Huffman dari akar ke daun untuk menetapkan kode biner: berikan '0' untuk tepi kiri dan '1' untuk tepi kanan. Jalur dari akar ke setiap daun membentuk kode Huffman untuk karakter tersebut.

3. Contoh Ilustrasi

Misalkan pesan "ABRACADABRA".

Langkah 1: Frekuensi Karakter:

• A: 5
• B: 2
• R: 2
• C: 1
• D: 1

Langkah 2-5: Pembangunan Pohon Huffman (ilustrasi singkat):

1. Ambil C(1), D(1) -> Gabung menjadi CD(2).
2. Ambil B(2), R(2) -> Gabung menjadi BR(4).
3. Ambil CD(2), BR(4) -> Gabung menjadi CDBR(6).
4. Ambil A(5), CDBR(6) -> Gabung menjadi Akar(11).

Langkah 6: Pemberian Kode (Contoh Hasil Kode):

• A: 0
• B: 100
• R: 101
• C: 110
• D: 111

Perhatikan bahwa 'A' (paling sering) mendapatkan kode terpendek.

4. Pseudocode Algoritma

CLASS HuffmanNode:
    character  // Karakter yang disimpan
    frequency  // Frekuensi kemunculan
    left_child // Anak kiri
    right_child // Anak kanan

FUNCTION BuildHuffmanTree(characters_with_frequencies):
    // Buat Priority Queue (min-heap)
    PQ = PriorityQueue()

    // Tambahkan setiap karakter sebagai node daun ke PQ
    FOR EACH (char, freq) IN characters_with_frequencies:
        node = new HuffmanNode(char, freq)
        PQ.INSERT(node)

    // Bangun pohon Huffman
    WHILE PQ.SIZE() > 1:
        left = PQ.EXTRACT_MIN() // Node dengan frekuensi terkecil
        right = PQ.EXTRACT_MIN() // Node kedua dengan frekuensi terkecil

        // Buat node internal baru
        parent = new HuffmanNode(NULL, left.frequency + right.frequency)
        parent.left_child = left
        parent.right_child = right

        PQ.INSERT(parent)

    RETURN PQ.EXTRACT_MIN() // Akar pohon Huffman

FUNCTION GenerateHuffmanCodes(root_node, current_code, codes_map):
    IF root_node IS NULL:
        RETURN

    IF root_node.character IS NOT NULL: // Jika ini adalah node daun
        codes_map[root_node.character] = current_code
        RETURN

    // Jelajahi anak kiri (tambahkan '0')
    GenerateHuffmanCodes(root_node.left_child, current_code + "0", codes_map)
    // Jelajahi anak kanan (tambahkan '1')
    GenerateHuffmanCodes(root_node.right_child, current_code + "1", codes_map)
                    

5. Kompleksitas Waktu & Ruang

• Kompleksitas Waktu:
  • Menghitung frekuensi: $O(N)$, di mana N adalah jumlah karakter dalam pesan.
  • Membangun pohon Huffman: Jika ada K karakter unik, dibutuhkan $O(K \log K)$ operasi pada Priority Queue.
  • Menghasilkan kode: $O(K \times \text{panjang_kode_maksimal})$.
  • Total: $O(N + K \log K)$. Jika $K \approx N$, maka $O(N \log N)$.
• Kompleksitas Ruang: $O(K)$ untuk menyimpan pohon Huffman dan tabel kode.

6. Aplikasi

• Kompresi File (misalnya, di format file seperti JPEG, MP3, ZIP).
• Encoding data untuk transmisi yang efisien (misalnya, fax).
• Digunakan sebagai bagian dari algoritma kompresi yang lebih besar.