HUFFMAN CODING
HUFFMAN CODING
Pengantar
Apa itu Huffman Coding?
Huffman coding adalah algoritma kompresi data lossless yang dikembangkan oleh David A. Huffman pada tahun 1952.
Digunakan untuk mengurangi ukuran data dengan mengganti simbol sering muncul dengan kode bit yang lebih pendek.
Biasa digunakan dalam format kompresi seperti ZIP, JPEG, MP3.
Konsep Dasar
- Berdasarkan frekuensi karakter dalam data
- Karakter frekuensi tinggi → kode pendek
- Karakter frekuensi rendah → kode panjang
- Representasi data menggunakan pohon biner
Proses Pembuatan Kode
- Hitung frekuensi tiap karakter.
- Buat simpul untuk setiap karakter.
- Gabungkan dua simpul dengan frekuensi terkecil.
- Ulangi hingga terbentuk pohon Huffman.
- Tentukan kode biner tiap karakter (0: kiri, 1: kanan).
Contoh Kasus
String: “ABBCCCDDDD”
Frekuensi:
A: 1, B: 2, C: 3, D: 4
Hasil Huffman Code:
D = 0, C = 10, B = 110, A = 111
Output Kompresi: Lebih pendek dari representasi asli.
Simulasi
Pesan: BCCABBDDAECCBBAEDDCC
- Panjang asli: 20 huruf
- ASCII: 8 bit per huruf × 20 = 160 bit
Langkah:
- Urutkan huruf berdasarkan frekuensi
- Gabungkan dua simpul terkecil secara berurutan
- Tandai kiri dengan 0 dan kanan dengan 1
- Hitung traversal dan panjang bit per huruf
- Total bit setelah kompresi = 45 bit
Implementasi
Pseudo Code & Kompleksitas:
- Kompleksitas Waktu: O(N log N), N = jumlah karakter unik
Kelebihan dan Kekurangan
Kelebihan:
✅ Lossless (tidak ada data yang hilang)
✅ Efisien untuk data distribusi tidak merata
✅ Banyak digunakan dalam sistem kompresi file
Kekurangan:
❌ Kurang optimal untuk data dengan distribusi karakter merata
❌ Butuh tabel kode saat dekompresi