Penjelasan pengodean Huffman

Komputer biasanya menyimpan setiap huruf dalam jumlah bit yang sama, delapan dalam ASCII biasa. Cara itu sederhana tetapi boros, karena sebagian huruf jauh lebih umum daripada yang lain. Pada tahun 1951 seorang mahasiswa menemukan cara terbaik untuk memberi setiap simbol kode dengan panjangnya sendiri, pendek untuk simbol yang sering dan panjang untuk yang langka, dengan konstruksi yang begitu sederhana sehingga muat dalam beberapa baris. Kini pengodean Huffman ada di dalam hampir setiap berkas terkompresi, gambar, dan suara yang Anda buka.

Pohon Huffman dengan huruf-huruf ABRACADABRA sebagai daun, sisi bertanda 0 dan 1, dan kode pendek A disorot
Pohon Huffman dengan huruf-huruf ABRACADABRA sebagai daun, sisi bertanda 0 dan 1, dan kode pendek A disorot

Kode pendek untuk simbol yang umum

Kode Morse sudah memakai gagasan ini pada tahun 1830-an: E, huruf paling umum dalam bahasa Inggris, hanyalah satu titik, sedangkan Q adalah garis garis titik garis. Kode seperti itu menghemat waktu dan ruang setiap kali sebagian simbol muncul lebih sering daripada yang lain. Namun panjang yang berbeda-beda menimbulkan masalah yang dipecahkan Morse dengan jeda: bagaimana Anda tahu di mana satu kode berakhir dan kode berikutnya dimulai? Dan berapa panjang yang harus diberikan kepada setiap simbol agar totalnya sekecil mungkin?

Kode prefiks

Masalah pertama lenyap jika tidak ada kode yang menjadi awal kode lain. Dengan kode A = 0, B = 10, C = 110, dan D = 111, bit 0101100 hanya dapat dibaca sebagai A B C A: begitu bit yang telah dibaca membentuk sebuah kode, kode itu lengkap. Kode prefiks seperti ini bersesuaian tepat dengan pohon biner yang simbol-simbolnya berada di daun, dengan setiap cabang kiri berarti 0 dan setiap cabang kanan berarti 1. Memilih kode berarti memilih pohon.

Konstruksi Huffman

Mulailah dengan satu daun per simbol, berbobot seberapa sering simbol itu muncul. Ambil dua pohon teringan dan gabungkan di bawah simpul baru yang bobotnya adalah jumlah keduanya, lalu ulangi hingga tersisa satu pohon. Itulah seluruh algoritmanya. Simbol yang langka digabungkan lebih dulu dan berakhir jauh di dalam pohon, dengan kode panjang; simbol yang umum digabungkan terakhir dan tetap dekat puncak, dengan kode pendek. Dengan antrean prioritas, waktunya sebanding dengan n log n untuk n simbol.

Mengapa hasilnya optimal

Dalam pohon terbaik yang mungkin, dua simbol paling langka selalu dapat ditempatkan sebagai saudara di tingkat terdalam: menukarnya dengan apa pun yang ada di sana hanya bisa memperpendek totalnya. Gabungkan keduanya menjadi satu simbol dengan bobot gabungannya, maka sisanya adalah masalah yang sama dengan satu simbol lebih sedikit, sehingga langkah greedy itu tidak pernah menutup jalan menuju jawaban terbaik. Jumlah total bit yang dipakai sama dengan jumlah bobot semua simpul dalam, yang dijaga sekecil mungkin oleh penggabungan tersebut.

Makalah tugas sebagai pengganti ujian

Pada tahun 1951 David Huffman, mahasiswa pascasarjana di MIT, mengikuti mata kuliah teori informasi yang diajar Robert Fano. Fano memberi mahasiswanya pilihan: mengikuti ujian akhir atau menulis makalah tentang cara menemukan kode biner yang paling efisien. Huffman hampir menyerah dengan makalahnya, lalu menyadari bahwa membangun pohon dari bawah ke atas, alih-alih membaginya dari atas ke bawah seperti pada metode Shannon–Fano, selalu memberikan hasil terbaik. Ia menerbitkannya pada tahun 1952; metode sang mahasiswa mengungguli metode yang disusun profesornya bersama Claude Shannon.

David Huffman, difoto saat menjadi profesor di UC Santa Cruz. Sebagai mahasiswa pascasarjana MIT pada tahun 1951, ia menemukan kode optimalnya dalam makalah untuk mata kuliah Robert Fano.
David Huffman, difoto saat menjadi profesor di UC Santa Cruz. Sebagai mahasiswa pascasarjana MIT pada tahun 1951, ia menemukan kode optimalnya dalam makalah untuk mata kuliah Robert Fano.
Claude Shannon, yang pada 1948 di Bell Labs merinci berapa banyak informasi yang dikandung sebuah pesan dan mengukurnya dalam bit.
Claude Shannon, yang pada 1948 di Bell Labs merinci berapa banyak informasi yang dikandung sebuah pesan dan mengukurnya dalam bit.

Dekat dengan entropi

Claude Shannon menunjukkan bahwa tidak ada kode yang dapat memakai bit per simbol, secara rata-rata, lebih sedikit daripada entropi sumbernya. Kode Huffman mencapai entropi tepat ketika setiap probabilitas merupakan pangkat dari setengah, dan tidak pernah satu bit penuh per simbol di atasnya. Selisih itu penting ketika satu simbol sangat umum: simbol dengan porsi 99% tetap membutuhkan paling sedikit satu bit utuh, padahal ia hanya membawa sekitar 0,015 bit informasi. Pengodean aritmetika dan asymmetric numeral systems (ANS) pada kompresor yang lebih baru menghindari batas itu.

Kode Huffman di mana-mana

Pengodean Huffman jarang dipakai sendirian, tetapi menjadi tahap terakhir banyak format. Deflate, yang ada di dalam ZIP, gzip, dan PNG, mula-mula mengganti pengulangan dengan referensi lalu menuliskan hasilnya dengan kode Huffman. JPEG memakainya untuk angka-angka yang tersisa setelah transformasi gambarnya, MP3 untuk data audionya, dan mesin faks untuk panjang deretan hitam dan putih. Format biasanya mengirim kode Huffman kanonis, yang hanya perlu menyimpan panjang kodenya, karena kode-kodenya sendiri dapat dibangun ulang dari panjang tersebut.

Jelajahi sendiri

Buka pembangun kode Huffman untuk membangun pohon ABRACADABRA, MISSISSIPPI RIVER, kalimat Anda sendiri, atau teks lain apa pun, satu langkah demi satu langkah. Saksikan dua pohon teringan bergabung di setiap langkah, klik sebuah daun untuk melihat kodenya, ikuti sebuah simbol di sepanjang bit yang dikodekan, dan bandingkan totalnya dengan kode panjang tetap, UTF-8, dan entropi.

Pertanyaan yang sering diajukan

Apa perbedaan pengodean Huffman dan Shannon–Fano?

Pengodean Shannon–Fano membangun pohon dari atas, membagi simbol-simbol menjadi dua kelompok dengan bobot hampir sama, berulang-ulang. Hasilnya sering bagus, tetapi tidak selalu optimal. Huffman membangun pohon dari bawah dengan menggabungkan dua pohon teringan, dan selalu menghasilkan kode prefiks sependek mungkin.

Apakah dekoder membutuhkan pohonnya?

Ya, dekoder membutuhkan kode yang sama. Karena itu berkas terkompresi menyimpannya, biasanya sebagai daftar panjang kode untuk kode kanonis, yang hanya memakan beberapa puluh byte. Untuk teks pendek, tambahan itu bisa lebih besar daripada penghematannya; pembangun ini hanya menghitung bit yang dikodekan.

Bisakah pengodean Huffman membuat berkas lebih besar?

Simbol yang dikodekan tidak pernah memakai bit lebih banyak daripada kode panjang tetap untuk simbol yang sama. Namun tabel kodenya juga harus disimpan, sehingga untuk data yang sangat pendek atau hampir acak, hasilnya bisa sedikit lebih besar daripada aslinya.

Apa isi ketaksamaan Kraft?

Bahwa kode prefiks dengan panjang kode l₁, l₂, … ada tepat ketika jumlah 2 pangkat −l atas semua simbol paling besar 1. Untuk pohon lengkap, seperti setiap pohon Huffman dengan paling sedikit dua simbol, jumlahnya tepat 1.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka pembangun kode Huffman