| Simbol | Jumlah | Kode | Bit | Total bit |
|---|
Pembangun kode Huffman
Mengapa huruf yang umum seperti a harus memakai bit sebanyak huruf langka seperti q? Pengodean Huffman memberi simbol yang sering muncul kode pendek dan simbol yang langka kode panjang, dan melakukannya dengan cara terbaik yang mungkin. Ketik teks atau pilih contoh, lalu bangun pohon Huffman-nya satu langkah demi satu langkah: dua pohon teringan bergabung di bawah simpul baru, berulang-ulang, hingga tersisa satu pohon. Kemudian setiap jalur dari puncak membentuk sebuah kode, dan Anda dapat mengikuti setiap simbol di sepanjang bit yang dikodekan. Ketik teks atau pilih contoh. Setiap simbol berawal sebagai daun dengan jumlah kemunculannya. Jalankan pembangunan langkah demi langkah: setiap langkah menggabungkan dua pohon teringan di bawah simpul baru yang bobotnya adalah jumlah keduanya, hingga tersisa satu pohon. Lalu jalur dari puncak ke sebuah daun memberikan kodenya, 0 untuk kiri dan 1 untuk kanan. Klik sebuah daun, baris, atau potongan bit untuk mengikuti satu simbol, lalu bandingkan totalnya dengan kode panjang tetap dan dengan entropi.
Cara kerjanya
- Ketik atau tempel teks, atau pilih contoh seperti ABRACADABRA atau MISSISSIPPI RIVER.
- Jalankan pembangunan langkah demi langkah dengan “Langkah berikutnya”, atau tekan “Putar”: setiap langkah menggabungkan dua pohon teringan di bawah simpul yang bobotnya adalah jumlah keduanya.
- Setelah pohon lengkap, klik sebuah daun, baris tabel, atau potongan bit untuk mengikuti satu simbol, lalu bandingkan total di kotak-kotak ringkasan.
Cara pohon dibangun
Hitung seberapa sering setiap simbol muncul dan jadikan masing-masing pohon berisi satu daun, berbobot jumlah kemunculannya. Lalu ulangi satu langkah sederhana: ambil dua pohon dengan bobot terkecil dan gantungkan di bawah simpul baru yang bobotnya adalah jumlah keduanya. Setiap langkah mengurangi satu pohon, sehingga setelah n − 1 langkah untuk n simbol tersisa satu pohon. Simbol yang langka digabungkan lebih dulu dan berada jauh di bawah; simbol yang umum digabungkan belakangan dan berada dekat puncak.
Membaca kodenya
Telusuri ke bawah dari puncak: langkah ke kiri menambahkan 0, langkah ke kanan menambahkan 1. Jalur menuju sebuah daun adalah kode simbol itu. Karena simbol hanya berada di daun, tidak ada kode yang menjadi awal kode lain, sehingga deretan bit dapat didekodekan tanpa pemisah apa pun: ikuti bit-bit itu menuruni pohon, dan setiap kali Anda tiba di sebuah daun, tuliskan simbolnya lalu mulai lagi dari puncak. Untuk ABRACADABRA, Huffman membutuhkan 23 bit, dibandingkan 33 bit untuk kode tetap 3 bit per huruf.
Pertanyaan yang sering diajukan
Mengapa kode Huffman adalah yang terbaik?
Di antara semua kode yang memberi setiap simbol deretan bit bulatnya sendiri, tidak ada yang totalnya lebih pendek untuk jumlah kemunculan yang sama. Buktinya mengikuti konstruksinya: dalam kode optimal, dua simbol paling langka selalu dapat dijadikan saudara di tingkat terdalam, dan menggabungkan keduanya menyisakan masalah yang lebih kecil dari jenis yang sama. Jumlah total bit sama dengan jumlah bobot semua simpul dalam pohon.
Apa itu kode prefiks?
Kode yang tidak satu pun kata kodenya menjadi awal kata kode lain, seperti 0, 10, 110, dan 111. Sifat ini memungkinkan dekoder membaca aliran bit tanpa pemisah, karena ia selalu tahu di mana sebuah kata kode berakhir. Setiap kode Huffman adalah kode prefiks: simbol-simbolnya hanya berada di daun pohon.
Apakah pohon Huffman itu unik?
Tidak sepenuhnya: bila dua pohon memiliki bobot yang sama, yang mana pun boleh diambil lebih dulu, dan kiri serta kanan dapat ditukar. Pilihan yang berbeda menghasilkan kode yang berbeda, tetapi jumlah total bitnya selalu sama. Pembangun ini selalu memutuskan bobot yang seri dengan cara yang sama, sehingga sebuah teks selalu menghasilkan pohon yang sama.
Seberapa dekat Huffman dengan entropi?
Panjang kode rata-rata paling sedikit sama dengan entropi dan kurang dari satu bit di atasnya. Panjang itu sama dengan entropi bila setiap probabilitas merupakan pangkat dari setengah, seperti pada contoh jumlah yang terus separuh. Pengodean aritmetika dan range coder modern menghindari batas bit bulat dan bisa lebih dekat lagi.
Apakah teks saya dikirim ke suatu tempat?
Tidak. Pohon dan kodenya dihitung di browser Anda, dan teks Anda tetap tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor