Algoritma Huffman digunakan untuk mengompresi atau mengkodekan data. Biasanya, setiap karakter dalam file teks disimpan sebagai delapan bit (digit, baik 0 atau 1) yang dipetakan ke karakter tersebut menggunakan pengkodean yang disebut ASCII. File yang dikodekan Huffman memecah struktur 8-bit yang kaku sehingga karakter yang paling umum digunakan disimpan hanya dalam beberapa bit ('a' bisa menjadi "10" atau "1000" daripada ASCII, yaitu "01100001"). Karakter yang paling tidak umum, kemudian, akan sering mengambil lebih dari 8 bit ('z' mungkin "00100011010"), tetapi karena mereka jarang terjadi, pengkodean Huffman, secara keseluruhan, membuat file yang jauh lebih kecil daripada aslinya.
Langkah
Bagian 1 dari 2: Pengkodean
Langkah 1. Hitung frekuensi setiap karakter dalam file yang akan dikodekan
Sertakan karakter tiruan untuk menandai akhir file -- ini akan menjadi penting nanti. Untuk saat ini, sebut saja EOF (end of file) dan tandai memiliki frekuensi 1.
Misalnya, jika Anda ingin menyandikan file teks yang membaca "ab ab cab," Anda akan memiliki 'a' dengan frekuensi 3, 'b' dengan frekuensi 3, ' ' (spasi) dengan frekuensi 2, 'c' dengan frekuensi 1, dan EOF dengan frekuensi 1
Langkah 2. Simpan karakter sebagai simpul pohon dan masukkan ke dalam antrian prioritas
Anda akan membangun pohon biner besar dengan setiap karakter sebagai daun, jadi Anda harus menyimpan karakter dalam format sedemikian rupa sehingga bisa menjadi simpul pohon. Tempatkan node ini ke dalam antrian prioritas dengan frekuensi masing-masing karakter sebagai prioritas node-nya.
- Pohon biner adalah format data di mana setiap bagian data adalah simpul yang dapat memiliki hingga satu orang tua dan dua anak. Ini sering digambar sebagai pohon bercabang, karena itulah namanya.
- Antrian adalah kumpulan data yang dinamai dengan tepat di mana hal pertama yang masuk ke dalam antrian juga merupakan hal pertama yang keluar (seperti menunggu dalam antrean). Dalam antrian prioritas, data disimpan dalam urutan prioritasnya, sehingga hal pertama yang keluar adalah hal yang paling mendesak, hal dengan prioritas terkecil, bukan hal pertama yang diantrikan.
- Dalam contoh "ab ab cab", antrian prioritas Anda akan terlihat seperti ini: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
Langkah 3. Mulailah membangun pohon Anda
Hapus (atau dequeue) dua hal yang paling mendesak dari antrian prioritas. Buat simpul pohon baru untuk menjadi induk dari dua simpul ini, simpan simpul pertama sebagai anak kirinya dan yang kedua sebagai anak kanannya. Prioritas node baru harus merupakan jumlah dari prioritas anaknya. Kemudian enqueue node baru ini dalam antrian prioritas.
Antrian prioritas sekarang terlihat seperti ini: {' ':2, node baru:2, 'a':3, 'b':3}
Langkah 4. Selesaikan pembuatan pohon Anda:
ulangi langkah di atas sampai hanya ada satu node dalam antrian. Perhatikan bahwa selain node yang Anda buat untuk karakter dan frekuensinya, Anda juga akan melakukan dequeuing, berubah menjadi pohon, dan mengantre ulang node induk, node yang sudah menjadi pohon itu sendiri.
- Setelah selesai, simpul terakhir dalam antrian akan menjadi akar dari pohon penyandian, dengan semua simpul lain bercabang darinya.
- Karakter yang paling sering digunakan adalah daun yang paling dekat dengan bagian atas pohon, sedangkan karakter yang jarang digunakan akan ditempatkan di bagian bawah pohon, lebih jauh dari akar.
Langkah 5. Buat peta penyandian. Berjalan melalui pohon untuk mencapai setiap karakter. Setiap kali Anda mengunjungi anak kiri simpul, itu adalah '0'. Setiap kali Anda mengunjungi anak kanan simpul, itu adalah '1'. Saat Anda mendapatkan karakter, simpan karakter dengan urutan 0 dan 1 yang diperlukan untuk sampai ke sana. Urutan ini adalah karakter yang akan dikodekan seperti pada file terkompresi. Simpan karakter dan urutannya di peta.
- Misalnya, mulai dari root. Kunjungi anak kiri root, lalu kunjungi anak kiri simpul itu. Karena simpul Anda sekarang tidak memiliki anak, Anda telah mencapai karakter. Ini adalah ' '. Karena Anda berjalan ke kiri dua kali untuk sampai ke sini, penyandian untuk ' ' adalah "00".
- Untuk pohon ini, petanya akan terlihat seperti ini: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
Langkah 6. Dalam file output, sertakan peta pengkodean sebagai header
Ini akan memungkinkan file untuk didekodekan.
Langkah 7. Encode file
Untuk setiap karakter dalam file yang akan dikodekan, tulis urutan biner yang telah Anda simpan di peta. Setelah Anda selesai menyandikan file, pastikan untuk menambahkan EOF di akhir.
- Untuk file "ab ab cab", file yang dikodekan akan terlihat seperti ini: "1011001011000101011011".
- File disimpan sebagai byte (8 bit, atau 8 digit biner). Karena algoritma Huffman Encoding tidak menggunakan format 8-bit, file yang dikodekan seringkali tidak memiliki panjang yang kelipatan 8. Digit yang tersisa akan diisi dengan 0s. Dalam hal ini, dua 0s akan ditambahkan di akhir file, yang terlihat seperti ruang lain. Ini bisa menjadi masalah: bagaimana decoder tahu kapan harus berhenti membaca? Namun, karena kami menyertakan karakter akhir file, dekoder akan sampai ke ini dan kemudian berhenti, mengabaikan apa pun yang ditambahkan setelahnya.
Bagian 2 dari 2: Dekode
Langkah 1. Baca dalam file yang dikodekan Huffman
Pertama, baca tajuk, yang seharusnya merupakan peta penyandian. Gunakan ini untuk membangun pohon decoding dengan cara yang sama seperti Anda membangun pohon yang Anda gunakan untuk menyandikan file. Kedua pohon harus identik.
Langkah 2. Baca dalam biner satu digit pada satu waktu
Lintasi pohon saat Anda membaca: jika Anda membaca di '0', pergi ke anak kiri dari simpul tempat Anda berada, dan jika Anda membaca di '1', pergi ke anak kanan. Saat Anda mencapai daun (simpul tanpa anak), Anda telah sampai pada sebuah karakter. Tulis karakter ke dalam file yang didekodekan.
Karena cara karakter disimpan di pohon, kode untuk setiap karakter memiliki properti awalan, sehingga tidak ada pengkodean biner karakter yang dapat terjadi pada awal pengkodean karakter lain. Pengkodean untuk setiap karakter benar-benar unik. Ini membuat decoding jauh lebih mudah
Langkah 3. Ulangi sampai Anda mencapai EOF
Selamat! Anda telah memecahkan kode file.
