🌳Huffman Coding

Huffman Coding adalah algoritma kompresi data lossless yang dikembangkan oleh David A. Huffman pada tahun 1952. Algoritma ini menggunakan prinsip variable-length encoding dimana karakter yang sering muncul diberi kode yang lebih pendek, sedangkan karakter yang jarang muncul diberi kode yang lebih panjang.

🎯 Tujuan Utama

🗜️ Kompresi Data: Mengurangi ukuran file tanpa kehilangan informasi ⚡ Efisiensi: Mengoptimalkan penggunaan bit untuk setiap karakter 📊 Optimal: Menghasilkan kode dengan panjang rata-rata minimum

🔍 Konsep Dasar

💡 Prinsip Kerja Huffman Coding bekerja berdasarkan frekuensi kemunculan karakter dalam teks:

📈 Karakter Sering → Kode Pendek (misal: 0, 10) 📉 Karakter Jarang → Kode Panjang (misal: 1101, 11100)

🌳 Huffman Tree

Algoritma ini membangun sebuah binary tree dimana:

🍃 Leaf nodes = karakter asli 🌿 Internal nodes = gabungan frekuensi 👈 Left edge = bit 0 👉 Right edge = bit 1

🔢 Algoritma Huffman Coding

📋 Langkah-Langkah Pembentukan Tree mermaidgraph TD

1. Hitung frekuensi setiap karakter
2. Buat priority queue berdasarkan frekuensi.
3. Ambil 2 node dengan frekuensi terkecil
4. Buat parent node baru
5. Masukkan kembali ke queue

🔧 Detail Algoritma

• 📊 Hitung Frekuensi Scan seluruh teks Hitung kemunculan setiap karakter

• 🏗️ Buat Priority Queue Masukkan semua karakter sebagai node Urutkan berdasarkan frekuensi (ascending)

• 🌳 Bangun Tree Ambil 2 node dengan frekuensi terkecil Buat parent baru dengan frekuensi = sum kedua child Ulangi sampai hanya tersisa 1 node (root)

• 🔤 Generate Kode Traversal tree dari root ke leaf Left = 0, Right = 1 Path dari root ke leaf = kode karak

🎯 Keunggulan dan Kekurangan

1. ✅ Keunggulan
   • 🎯 Optimal: Menghasilkan kode dengan panjang rata-rata minimum
   • 🔒 Lossless: Tidak ada kehilangan data
   • ⚡ Efisien: Algoritma greedy yang cepat
   • 🌐 Universal: Dapat digunakan untuk berbagai jenis data
   • 📈 Adaptif: Menyesuaikan dengan distribusi frekuensi
2. ⚠️ Kekurangan
   • 📊 Perlu Statistik: Memerlukan informasi frekuensi sebelumnya
   • 💾 Overhead: Perlu menyimpan tree/table untuk decoding
   • 🔄 Tidak Cocok untuk Data Seragam: Kurang efektif jika semua karakter frekuensinya sama
   • 📏 Fixed Length: Tidak cocok untuk streaming data

🌍 Aplikasi di Dunia Nyata

💼 Implementasi Praktis

1. 📁 Kompresi File
   • ZIP/RAR: Menggunakan variasi Huffman Coding
   • JPEG: Huffman coding untuk kompresi gambar
   • MP3: Bagian dari algoritma kompresi audio
2. 📡 Transmisi Data
   • Fax Machines: Kompresi dokumen sebelum transmisi
   • Modem: Optimasi bandwidth komunikasi Satellite Communication: Efisiensi penggunaan channel
3. 💾 Penyimpanan Data
   • Database Compression: Optimasi storage
   • Backup Systems: Mengurangi ukuran backup
   • Cloud Storage: Efisiensi penyimpanan

Huffman Coding membuktikan bahwa pendekatan greedy dapat menghasilkan solusi global optimal, dengan memanfaatkan karakteristik unik dari masalah prefix-free encoding.