Apa itu Huffman Coding?
Huffman Coding adalah algoritma kompresi data yang menggunakan pendekatan greedy untuk membuat kode biner dengan panjang variabel. Algoritma ini menghasilkan kode prefiks yang optimal untuk menyandikan karakter berdasarkan frekuensi kemunculannya, sehingga karakter yang lebih sering muncul memiliki kode yang lebih pendek.
Huffman Coding memiliki aplikasi luas dalam berbagai bidang, seperti:
- Kompresi file: Digunakan dalam format seperti ZIP dan JPEG
- Komunikasi data: Mengurangi ukuran data yang dikirim melalui jaringan
- Penyimpanan data: Mengoptimalkan penggunaan ruang penyimpanan
- Kriptografi: Dasar untuk beberapa algoritma penyandian
Cara Kerja Huffman Coding
Algoritma Huffman Coding bekerja dengan membangun pohon biner (Huffman Tree) berdasarkan frekuensi karakter. Berikut langkah-langkahnya:
- Hitung frekuensi:
- Hitung frekuensi kemunculan setiap karakter dalam data masukan
- Buat simpul daun untuk setiap karakter dengan frekuensinya
- Bangun pohon Huffman:
- Masukkan semua simpul daun ke dalam antrian prioritas (min-heap)
- Selama antrian memiliki lebih dari satu simpul:
- Ambil dua simpul dengan frekuensi terendah
- Buat simpul induk baru dengan frekuensi total kedua simpul
- Tambahkan simpul induk kembali ke antrian
- Hasilkan kode:
- Telusuri pohon Huffman dari akar ke setiap daun
- Tetapkan 0 untuk cabang kiri dan 1 untuk cabang kanan
- Catat kode biner untuk setiap karakter
Hasilnya adalah tabel kode yang digunakan untuk menyandikan dan mendekode data dengan efisien.
Contoh Permasalahan
Misalkan kita ingin menyandikan string "AABBCC" menggunakan Huffman Coding. Berikut langkah-langkahnya:
Langkah-langkah:
- Frekuensi: A=2, B=2, C=2
- Buat min-heap: [A:2, B:2, C:2]
- Ambil dua simpul (A:2, B:2), buat induk (AB:4), masukkan kembali: [C:2, AB:4]
- Ambil dua simpul (C:2, AB:4), buat induk (ABC:6)
- Hasilkan kode: A=00, B=01, C=1
- Sandikan "AABBCC": 00 00 01 01 1 1 = 000001011
String asli membutuhkan 6×8=48 bit (ASCII). Dengan Huffman Coding, hanya 9 bit diperlukan.
Implementasi Kode (Python)
Berikut implementasi Huffman Coding menggunakan Python:
import heapq
from collections import Counter
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(data):
# Hitung frekuensi
freq = Counter(data)
# Buat min-heap
heap = [Node(char, freq) for char, freq in freq.items()]
heapq.heapify(heap)
# Bangun pohon
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
internal = Node(None, left.freq + right.freq)
internal.left = left
internal.right = right
heapq.heappush(heap, internal)
return heap[0]
def generate_codes(root, current_code="", codes={}):
if root is None:
return
if root.char is not None:
codes[root.char] = current_code or "0"
generate_codes(root.left, current_code + "0", codes)
generate_codes(root.right, current_code + "1", codes)
return codes
def huffman_coding(data):
if not data:
return "", {}
# Bangun pohon dan hasilkan kode
root = build_huffman_tree(data)
codes = generate_codes(root)
# Sandikan data
encoded = "".join(codes[char] for char in data)
return encoded, codes
# Contoh penggunaan
data = "AABBCC"
encoded, codes = huffman_coding(data)
print("Kode Huffman:", codes)
print("Data tersandi:", encoded)
</pre>
<p className="mt-4 leading-relaxed">
Output akan menampilkan tabel kode Huffman dan data yang telah disandikan.
</p>
</section>
{/* Implementasi Kode (JavaScript) */}
<section className="mb-10 p-6 rounded-lg bg-lightBlue shadow-lg">
<h2 className="text-3xl font-semibold text-accentBlue mb-4">
Implementasi Kode (JavaScript)
</h2>
<p className="mb-4 leading-relaxed">
Berikut implementasi Huffman Coding dalam JavaScript:
</p>
<pre className="bg-darkBlue text-textLight p-4 rounded-md overflow-x-auto text-sm">
class Node {
constructor(char, freq) {
this.char = char;
this.freq = freq;
this.left = null;
this.right = null;
}
}
function huffmanCoding(data) {
if (!data) return { encoded: "", codes: {} };
// Hitung frekuensi
const freq = {};
for (let char of data) {
freq[char] = (freq[char] || 0) + 1;
}
// Buat min-heap
const heap = Object.entries(freq).map(([char, freq]) => new Node(char, freq));
heap.sort((a, b) => a.freq - b.freq);
// Bangun pohon
while (heap.length > 1) {
const left = heap.shift();
const right = heap.shift();
const internal = new Node(null, left.freq + right.freq);
internal.left = left;
internal.right = right;
heap.push(internal);
heap.sort((a, b) => a.freq - b.freq);
}
// Hasilkan kode
const codes = {};
function generateCodes(node, currentCode = "") {
if (!node) return;
if (node.char !== null) {
codes[node.char] = currentCode || "0";
}
generateCodes(node.left, currentCode + "0");
generateCodes(node.right, currentCode + "1");
}
generateCodes(heap[0]);
// Sandikan data
const encoded = data.split("").map(char => codes[char]).join("");
return { encoded, codes };
}
// Contoh penggunaan
const data = "AABBCC";
const { encoded, codes } = huffmanCoding(data);
console.log("Kode Huffman:", codes);
console.log("Data tersandi:", encoded);
Kompleksitas dan Optimasi
Kompleksitas Waktu:
Kompleksitas waktu adalah O(n log n), di mana n adalah jumlah karakter unik. Ini karena pembuatan min-heap dan pengurutan berulang membutuhkan O(log n) untuk setiap operasi.
Kompleksitas Ruang:
Kompleksitas ruang adalah O(n) untuk menyimpan pohon Huffman dan tabel kode.
Optimasi:
- Min-heap efisien: Menggunakan struktur heap bawaan untuk performa lebih baik
- Cache frekuensi: Menyimpan hasil frekuensi untuk data yang sering diulang
- Paralelisasi: Memproses pembangunan pohon secara paralel untuk data besar
Kelebihan dan Kekurangan
Kelebihan Huffman Coding:
- Efisien: Menghasilkan kompresi optimal untuk data dengan frekuensi karakter tidak seragam
- Prefiks kode: Tidak memerlukan pemisah, sehingga dekoding lebih sederhana
- Fleksibel: Dapat digunakan untuk berbagai jenis data
Kekurangan Huffman Coding:
- Overhead: Memerlukan penyimpanan pohon atau tabel kode
- Data kecil: Kurang efisien untuk data dengan distribusi frekuensi seragam
- Kompleksitas: Lebih rumit dibandingkan metode kompresi sederhana
Kesimpulan
Huffman Coding adalah algoritma kompresi data yang efisien dan banyak digunakan, terutama untuk data dengan distribusi frekuensi karakter yang bervariasi. Dengan memanfaatkan pohon biner dan kode prefiks, algoritma ini meminimalkan ukuran data tanpa kehilangan informasi. Meskipun memiliki beberapa keterbatasan, Huffman Coding tetap menjadi dasar penting dalam kompresi data dan memiliki aplikasi luas dalam teknologi modern.