Huffman kodlash yordamida ma'lumotlarni qanday siqish kerak: 10 qadam

Mundarija:

Huffman kodlash yordamida ma'lumotlarni qanday siqish kerak: 10 qadam
Huffman kodlash yordamida ma'lumotlarni qanday siqish kerak: 10 qadam

Video: Huffman kodlash yordamida ma'lumotlarni qanday siqish kerak: 10 qadam

Video: Huffman kodlash yordamida ma'lumotlarni qanday siqish kerak: 10 qadam
Video: Telefonda rasm montaj qilish 2024, Qadam tashlamoq
Anonim

Xaffman algoritmi ma'lumotlarni siqish yoki kodlash uchun ishlatiladi. Odatda, matnli fayldagi har bir belgi sakkiz bitli (0 yoki 1 raqamli) saqlanadi, bu belgi ASCII deb nomlangan kod yordamida ishlatiladi. Huffman tomonidan kodlangan fayl qattiq 8 bitli tuzilmani buzadi, shuning uchun eng ko'p ishlatiladigan belgilar bir necha bitda saqlanadi ("a" ASCII o'rniga "10" yoki "1000" bo'lishi mumkin, ya'ni "01100001")). Eng kam uchraydigan belgilar, odatda, 8 bitdan oshadi ("z" "00100011010" bo'lishi mumkin), lekin ular juda kamdan -kam hollarda bo'lgani uchun, Xuffman kodlashi, umuman, asl nusxadan ancha kichikroq faylni yaratadi.

Qadamlar

2 -qismning 1 -qismi: Kodlash

Huffman kodlash yordamida ma'lumotlarni siqish 1 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 1 -qadam

Qadam 1. Kodlangan fayldagi har bir belgining chastotasini hisoblang

Faylning oxirini belgilash uchun qo'g'irchoq belgisini qo'shing - bu keyinroq muhim bo'ladi. Hozircha uni EOF (fayl oxiri) deb nomlang va 1 chastotali deb belgilang.

Misol uchun, agar siz "ab ab cab" matnli faylni kodlashni xohlasangiz, sizda "a" chastotasi 3, "b" chastotasi 3, "chastota" 2 chastotali, "c" chastotasi 1 bo'ladi. va 1 -chastotali EOF

Huffman kodlash yordamida ma'lumotlarni siqish 2 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 2 -qadam

Qadam 2. Belgilarni daraxt tugunlari sifatida saqlang va ularni ustuvor navbatga qo'ying

Siz har bir belgi bilan bargli katta ikkilik daraxt qurasiz, shuning uchun siz ularni daraxt tuguniga aylanadigan formatda saqlashingiz kerak. Bu tugunlarni har bir belgining chastotasi ustuvor navbatga joylashtiring.

  • Ikkilik daraxt - bu ma'lumotlar formati, bu erda har bir ma'lumotlar bitta ota -ona va ikkita bolaga ega bo'lishi mumkin bo'lgan tugun hisoblanadi. U tez -tez dallanadigan daraxt sifatida chizilgan, shuning uchun ham shunday nomlangan.
  • Navbat - bu aniq nomlangan ma'lumotlar to'plami bo'lib, unda navbatga birinchi bo'lib chiqish kerak bo'lgan narsa (navbat kutish kabi). Birinchi navbatda ma'lumotlar birinchi navbatda saqlanadi, shuning uchun birinchi navbatda birinchi narsa emas, balki eng muhim narsa, eng muhim narsa bo'ladi.
  • "Ab ab cab" misolida sizning ustuvor navbatingiz quyidagicha bo'ladi: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Huffman kodlash yordamida ma'lumotlarni siqish 3 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 3 -qadam

Qadam 3. Daraxtingizni qurishni boshlang

Birinchi navbatdagi ikkita eng shoshilinch narsani olib tashlang (yoki bekor qiling). Bu ikki tugunning ota -onasi bo'lish uchun yangi daraxt tugunini yarating, birinchi tugunni chap, ikkinchisini o'ng bola sifatida saqlang. Yangi tugunning ustuvorligi uning farzandining ustuvorliklari yig'indisi bo'lishi kerak. Keyin bu yangi tugunni ustuvor navbatda navbatga qo'ying.

Endi ustuvor navbat quyidagicha ko'rinadi: {'': 2, yangi tugun: 2, 'a': 3, 'b': 3}

Huffman kodlash yordamida ma'lumotlarni siqish 4 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 4 -qadam

Qadam 4. Daraxt qurishni tugating:

navbatda faqat bitta tugun bo'lmaguncha yuqoridagi amalni takrorlang. E'tibor bering, siz belgilar va ularning chastotalari uchun yaratgan tugunlardan tashqari, siz dequeue, daraxtlarga aylanasiz va ota-ona tugunlari, o'zlari allaqachon daraxt bo'lgan tugunlarni qaytarasiz.

  • Tugatganingizdan so'ng, navbatdagi oxirgi tugun kodlash daraxtining ildizi bo'ladi va boshqa barcha tugunlar undan bo'linadi.
  • Eng ko'p ishlatiladigan belgilar daraxt tepasiga eng yaqin barglar bo'ladi, kamdan -kam ishlatiladigan belgilar esa daraxt tagida, ildizdan uzoqroqda joylashadi.
Huffman kodlash yordamida ma'lumotlarni siqish 5 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 5 -qadam

Qadam 5. Kodlash xaritasini yarating. Har bir belgiga erishish uchun daraxt bo'ylab yuring. Har safar tugunning chap bolasiga tashrif buyurganingizda, bu "0". Har safar tugunning to'g'ri bolasiga tashrif buyurganingizda, bu "1". Qachonki siz belgi bilan tanishsangiz, u erga borish uchun zarur bo'lgan 0 va 1 sonlar ketma -ketligini saqlang. Bu ketma -ketlik, siqilgan faylda bo'lgani kabi, belgi kodlangan bo'ladi. Belgilar va ularning ketma -ketligini xaritada saqlang.

  • Masalan, ildizdan boshlang. Ildizning chap bolasiga, so'ng tugunning chap bolasiga tashrif buyuring. Siz turgan tugunning bolalari bo'lmaganligi sababli, siz belgiga yetdingiz. Bu ' '. Siz bu erga kelish uchun ikki marta chapga yurganingiz uchun '' kodlashi "00" dir.
  • Bu daraxt uchun xarita shunday bo'ladi: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Huffman kodlash yordamida ma'lumotlarni siqish 6 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 6 -qadam

Qadam 6. Chiqish fayliga kodlash xaritasini sarlavha sifatida kiriting

Bu faylni dekodlash imkonini beradi.

Huffman kodlash yordamida ma'lumotlarni siqish 7 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 7 -qadam

Qadam 7. Faylni kodlash

Fayldagi har bir belgi kodlanishi uchun siz xaritada saqlagan ikkilik ketma -ketlikni yozing. Faylni kodlashni tugatganingizdan so'ng, EOFni oxirigacha qo'shganingizga ishonch hosil qiling.

  • "Ab ab cab" fayli uchun kodlangan fayl shunday bo'ladi: "1011001011000101011011".
  • Fayllar bayt sifatida saqlanadi (8 bit yoki 8 ikkilik raqam). Huffman kodlash algoritmi 8-bitli formatni ishlatmaganligi uchun, kodlangan fayllar ko'pi bilan 8 uzunliklarga ega bo'lmaydi. Qolgan raqamlar 0 sonlar bilan to'ldiriladi. Bunday holda, fayl oxiriga ikkita 0 qo'shiladi, bu boshqa bo'shliqqa o'xshaydi. Bu muammo bo'lishi mumkin: dekoder o'qishni to'xtatishni qachon biladi? Ammo, biz faylning oxirigacha bo'lgan belgini kiritganimiz uchun, dekoder bunga erishadi va keyin qo'shilgan boshqa narsalarga e'tibor bermay to'xtaydi.

2 -qismning 2 -qismi: Dekodlash

Huffman kodlash yordamida ma'lumotlarni siqish 8 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 8 -qadam

Qadam 1. Huffman kodlangan faylda o'qing

Birinchidan, sarlavhani o'qing, bu kodlash xaritasi bo'lishi kerak. Faylni kodlash uchun ishlatilgan daraxtni qurganingizdek, dekodlash daraxtini yaratish uchun buni ishlating. Ikkita daraxt bir xil bo'lishi kerak.

Huffman kodlash yordamida ma'lumotlarni siqish 9 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 9 -qadam

Qadam 2. Bir vaqtning o'zida bitta raqamni ikkilik o'qing

Siz o'qiyotganingizda daraxtni aylantiring: agar siz "0" da o'qigan bo'lsangiz, siz turgan tugunning chap bolasiga, agar "1" da o'qigan bo'lsangiz, o'ng bolaga o'ting. Bargga (bolasiz tugunga) yetganingizda, siz bir belgiga yetdingiz. Belgini dekodlangan faylga yozing.

Belgilar daraxtda saqlanganligi sababli, har bir belgining kodlari prefiks xususiyatiga ega, shuning uchun boshqa belgining kodlashining boshida hech qanday belgining ikkilik kodlanishi sodir bo'lmaydi. Har bir belgi uchun kodlash mutlaqo o'ziga xosdir. Bu dekodlashni ancha osonlashtiradi

Huffman kodlash yordamida ma'lumotlarni siqish 10 -qadam
Huffman kodlash yordamida ma'lumotlarni siqish 10 -qadam

Qadam 3. EOFga yetguncha takrorlang

Tabriklaymiz! Siz faylni hal qildingiz.

Tavsiya: