Cara Memampatkan Data Menggunakan Pengekodan Huffman: 10 Langkah

Isi kandungan:

Cara Memampatkan Data Menggunakan Pengekodan Huffman: 10 Langkah
Cara Memampatkan Data Menggunakan Pengekodan Huffman: 10 Langkah

Video: Cara Memampatkan Data Menggunakan Pengekodan Huffman: 10 Langkah

Video: Cara Memampatkan Data Menggunakan Pengekodan Huffman: 10 Langkah
Video: Cara Cepat Merubah Ukuran Gambar Menjadi Sama di Microsoft Word | Trik Microsoft Word 2024, Mac
Anonim

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

Memampatkan Data Menggunakan Pengekodan Huffman Langkah 1
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 1

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

Memampatkan Data Menggunakan Pengekodan Huffman Langkah 2
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 2

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}
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 3
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 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}

Memampatkan Data Menggunakan Pengekodan Huffman Langkah 4
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 4

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.
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 5
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 5

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"}.
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 6
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 6

Langkah 6. Dalam fail output, sertakan peta pengekodan sebagai tajuk

Ini akan membolehkan fail disahkod.

Memampatkan Data Menggunakan Pengekodan Huffman Langkah 7
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 7

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

Memampatkan Data Menggunakan Pengekodan Huffman Langkah 8
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 8

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.

Memampatkan Data Menggunakan Pengekodan Huffman Langkah 9
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 9

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

Memampatkan Data Menggunakan Pengekodan Huffman Langkah 10
Memampatkan Data Menggunakan Pengekodan Huffman Langkah 10

Langkah 3. Ulangi sehingga anda mencapai EOF

Tahniah! Anda telah menyahkod fail.

Disyorkan: