Algoritma Huffman digunakan untuk memampatkan atau mengekod data. Biasanya, setiap watak dalam fail teks disimpan sebagai lapan bit (digit, 0 atau 1) yang memetakan watak tersebut menggunakan pengekodan yang disebut ASCII. Fail yang dikodkan oleh Huffman memecah struktur 8-bit yang kaku sehingga watak yang paling sering digunakan disimpan hanya dalam beberapa bit ('a' mungkin "10" atau "1000" dan bukannya ASCII, yaitu "01100001"). Oleh itu, watak yang paling kurang biasa akan memakan masa lebih daripada 8 bit ('z' mungkin "00100011010"), tetapi kerana ia jarang sekali berlaku, pengekodan Huffman secara keseluruhannya menghasilkan fail yang jauh lebih kecil daripada yang asli.
Langkah-langkah
Bahagian 1 dari 2: Pengekodan
Langkah 1. Hitung frekuensi setiap watak dalam fail yang akan dikodkan
Sertakan watak palsu untuk menandakan akhir fail - ini akan menjadi penting kemudian. Buat masa ini, namakan EOF (akhir fail) dan tandakan sebagai mempunyai frekuensi 1.
Sebagai contoh, jika anda ingin menyandikan fail teks yang berbunyi "ab ab cab," anda akan mempunyai 'a' dengan frekuensi 3, 'b' dengan frekuensi 3, '' (ruang) dengan frekuensi 2, 'c' dengan frekuensi 1, dan EOF dengan kekerapan 1
Langkah 2. Simpan watak sebagai simpul pokok dan masukkannya ke dalam barisan keutamaan
Anda akan membina pokok biner besar dengan setiap watak sebagai daun, jadi anda harus menyimpan watak-watak tersebut dalam format yang boleh menjadi simpul pokok. Letakkan nod ini ke dalam barisan keutamaan dengan frekuensi setiap watak sebagai keutamaan nodnya.
- Pokok binari adalah format data di mana setiap bahagian data adalah simpul yang boleh memuatkan satu ibu bapa dan dua anak. Ia sering digambarkan sebagai pohon bercabang, oleh itu namanya.
- Antrian adalah pengumpulan data yang dinamakan dengan tepat di mana perkara pertama yang masuk ke dalam barisan juga merupakan perkara pertama yang keluar (seperti menunggu dalam barisan). Dalam barisan keutamaan, data disimpan mengikut urutan keutamaannya, sehingga perkara pertama yang keluar adalah perkara yang paling mendesak, perkara dengan keutamaan terkecil, dan bukan perkara pertama yang dimuat.
- Dalam contoh "ab ab cab", barisan keutamaan anda akan kelihatan seperti ini: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Langkah 3. Mulakan membina pokok anda
Keluarkan (atau dequeue) dua perkara paling mendesak dari barisan keutamaan. Buat simpul pokok baru untuk menjadi induk kedua nod ini, simpan simpul pertama sebagai anak kirinya dan kedua sebagai anak kanannya. Keutamaan simpul baru mestilah jumlah keutamaan anaknya. Kemudian masukkan simpul baru ini dalam barisan keutamaan.
Baris keutamaan kini kelihatan seperti ini: {'': 2, simpul baru: 2, 'a': 3, 'b': 3}
Langkah 4. Selesaikan pembinaan pokok anda:
ulangi langkah di atas sehingga hanya terdapat satu simpul dalam barisan. Perhatikan bahawa sebagai tambahan kepada node yang anda buat untuk watak dan frekuensi mereka, anda juga akan menyusun semula, bertukar menjadi pokok, dan mengaktifkan semula nod induk, nod yang sudah menjadi pokok.
- Apabila anda selesai, simpul terakhir dalam barisan akan menjadi akar pokok pengekodan, dengan semua nod lain bercabang daripadanya.
- Karakter yang paling kerap digunakan adalah daun yang paling dekat dengan bahagian atas pokok, sementara watak yang jarang digunakan akan diletakkan di bahagian bawah pokok, lebih jauh dari akar.
Langkah 5. Buat peta pengekodan. Berjalan melalui pokok untuk mencapai setiap watak. Setiap kali anda melawat anak kiri nod, itu adalah '0'. Setiap kali anda melawat anak kanan simpul, itu adalah '1'. Apabila anda mencapai watak, simpan watak dengan urutan 0 dan 1s yang diperlukan untuk sampai ke sana. Urutan ini adalah watak yang akan dikodkan seperti dalam fail yang dimampatkan. Simpan watak dan urutannya dalam peta.
- Contohnya, mulakan dari akar. Lawati anak kiri akar, dan kemudian lawati anak kiri simpul itu. Oleh kerana node anda sekarang tidak mempunyai anak, anda telah mencapai watak. Ini adalah ' '. Oleh kerana anda berjalan ke kiri dua kali untuk sampai ke sini, pengekodan untuk '' adalah "00".
- Untuk pokok ini, peta akan kelihatan seperti ini: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Langkah 6. Dalam fail output, sertakan peta pengekodan sebagai tajuk
Ini akan membolehkan fail disahkod.
Langkah 7. Encode fail
Untuk setiap watak dalam fail yang akan dikodkan, tulis urutan binari yang anda simpan di peta. Setelah selesai mengekod fail, pastikan untuk menambahkan EOF hingga akhir.
- Untuk fail "ab ab cab", fail yang dikodkan akan kelihatan seperti ini: "1011001011000101011011".
- Fail disimpan sebagai bait (8 bit, atau 8 digit binari). Oleh kerana algoritma Pengekodan Huffman tidak menggunakan format 8-bit, fail yang dikodkan selalunya tidak akan mempunyai panjang yang berlipat ganda 8. Angka yang selebihnya akan diisi dengan 0s. Dalam kes ini, dua 0 akan ditambahkan pada akhir fail, yang kelihatan seperti ruang lain. Ini boleh menjadi masalah: bagaimana penyahkod mengetahui kapan berhenti membaca? Walau bagaimanapun, kerana kami memasukkan watak akhir fail, penyahkod akan sampai ke ini dan kemudian berhenti, mengabaikan perkara lain yang telah ditambahkan selepasnya.
Bahagian 2 dari 2: Penyahkodan
Langkah 1. Baca dalam fail yang dikodkan Huffman
Pertama, baca pengepala, yang seharusnya menjadi peta pengekodan. Gunakan ini untuk membina pokok penyahkodan dengan cara yang sama anda membina pokok yang anda gunakan untuk mengekod fail. Kedua-dua pokok itu harus sama.
Langkah 2. Baca dalam perduaan satu digit pada satu masa
Melintasi pokok semasa anda membaca: jika anda membaca di '0', pergi ke anak kiri nod yang anda berada, dan jika anda membaca dengan '1', pergi ke anak kanan. Apabila anda mencapai daun (simpul tanpa anak-anak), anda akan menemui watak. Tulis watak ke dalam fail yang disahkod.
Kerana cara watak disimpan di pohon, kod untuk setiap watak mempunyai sifat awalan, sehingga tidak ada pengekodan binari watak yang dapat terjadi pada permulaan pengekodan watak lain. Pengekodan untuk setiap watak benar-benar unik. Ini menjadikan penyahkodan lebih mudah
Langkah 3. Ulangi sehingga anda mencapai EOF
Tahniah! Anda telah menyahkod fail.