|
3. Xoffmann kodi.
Xuffman algoritmi - alifboni minimal qisqartirish bilan maqbul kodlash uchun ochko'z algoritm. U 1952 yilda Massachusets texnologiya institutining aspiranti Devid Xuffman tomonidan ilmiy ishlarni yozish paytida ishlab chiqilgan. Hozirda ko'plab ma'lumotlarni siqish dasturlarida ishlatiladi.
Ushbu kodlash usuli ikkita asosiy bosqichdan iborat:
Optimal kod daraxtini yaratish.
O'rnatilgan daraxt asosida kod-belgi displeyini yaratish.
Ma'lumotni samarali kodlash uchun birinchi algoritmlardan biri 1952 yilda DA Xuffman tomonidan taklif etilgan. Algoritmning g'oyasi quyidagicha: xabarda belgilar paydo bo'lishi ehtimolini bilib, biz o'zgarmaydigan kodlarni qurish tartibini tasvirlashimiz mumkin. bitlarning butun sonidan iborat uzunlik. Belgilar ko'proq qisqa kodlarga tayinlanishi mumkin. Huffman kodlari prefiksiya xususiyatiga ega (ya'ni kododlar boshqasining prefiksi emas), bu ularni noyob dekodlash imkonini beradi.
Kirishdagi klassik Huffman algoritmi xabarda belgilar paydo bo'lishi chastotalari jadvalini oladi. Keyinchalik, ushbu jadval asosida Huffman kodlash daraxti (H-daraxt) qurilgan.
Kirish alifbosi belgilari bepul tugunlarning ro'yxatini tashkil qiladi. Har bir varaqning og'irligi bor, u siqilish xabarida belgi paydo bo'lishi ehtimoli yoki ehtimoliga teng bo'lishi mumkin.
Eng kichik og'irlikdagi ikkita bepul daraxt tugunlari tanlangan.
Ularning ota-onalari umumiy og'irliklariga teng bo'lgan vazn bilan yaratilgan.
Ota-onalar bepul tugunlar ro'yxatiga qo'shiladi va uning ikkita farzandi ushbu ro'yxatdan chiqariladi.
Bit 1 bitta ota-onani qoldirib, boshqasiga 0 bitni tayinlaydi. Ildizdan kelib chiqqan novdalarning ozgina qiymatlari avlodlarning og'irliklariga bog'liq emas.
Ikkinchisidan boshlab qadamlar faqat bitta bepul tugun bo'sh tugunlar ro'yxatida qolmaguncha takrorlanadi. Bu daraxtning ildizi deb hisoblanadi.
Aytaylik, bizda quyidagi chastota jadvali bor:
Bu jarayon daraxtni qurishda ifodalanishi mumkin, uning ildizi oxirgi bosqichdagi belgilarning kombinatsiyasi natijasida olingan kombinatsiyalangan belgilarning ehtimolligi yig'indisi, n 0 avlodlari oldingi bosqichdagi belgilar va boshqalar.
Xabarga kiritilgan har bir belgi uchun kodni aniqlash uchun biz hozirgi belgilarga mos keladigan daraxt bargidan uning ildiziga o'tishimiz kerak, daraxtning novdalari bo'ylab harakatlanayotganda bitlarni to'plashimiz kerak (yo'ldagi birinchi novdaga to'g'ri keladi). ahamiyatsiz qadar). Shu tarzda olingan bitlarning ketma-ketligi teskari tartibda yozilgan ushbu belgining kodidir.
Ushbu belgilar jadvali uchun Huffman kodlari quyidagicha bo'ladi.
Qabul qilingan kodlarning hech biri ikkinchisining prefiksi emasligi sababli ularni oqimdan o'qiyotganda ularni noyob echilishi mumkin. Bundan tashqari, A xabarining eng tez-tez uchraydigan belgisi eng kam bit bilan kodlangan, eng kam uchraydigan belgi D esa eng kattasi bilan kodlangan.
Bunday holda, belgilar jadvalidagi belgilardan iborat bo'lgan xabarning umumiy uzunligi 87 bitni tashkil etadi (har bir belgi uchun o'rtacha 2,2308 bit). Yagona kodlash yordamida xabarlarning umumiy uzunligi 117 bitni tashkil etadi (har bir belgi uchun 3 bit). Belgilangan chastotalar bilan mustaqil ravishda ramzlarni yaratadigan manbaning entropiyasi har bir belgi uchun ~ 2,1858 bitni tashkil etadi, ya'ni bunday manba uchun tuzilgan Huffman kodining ortiqcha bo'lishi, har bir belgi uchun bitlarning o'rtacha soni va entropiya o'rtasidagi farq sifatida tushuniladi. , har bir belgi uchun 0,05 bit dan kam.
Klassik Xuffman algoritmi bir qator muhim kamchiliklarga ega. Birinchidan, siqilgan xabar tarkibini tiklash uchun dekoder kodlovchi tomonidan ishlatiladigan chastota jadvalini bilishi kerak. Shuning uchun, siqilgan xabarning uzunligi ma'lumotlar oldidan yuborilishi kerak bo'lgan chastota jadvalining uzunligi bilan ko'payadi, bu esa xabarni siqish uchun barcha sa'y-harakatlarni bekor qilishi mumkin. Bundan tashqari, haqiqiy kodlashni boshlashdan oldin to'liq chastota statistikasiga ehtiyoj xabarda ikkita o'tish talab qilinadi: biri xabar modelini (chastota jadvali va H-daraxt) qurish uchun, ikkinchisi haqiqiy kodlash uchun. Ikkinchidan, kodlashning ortiqcha bo'lishi kodlangan belgilarning ehtimolligi 2 ga teskari kuchga ega bo'lgan hollardagina yo'qoladi. Uchinchidan, entropiyasi 1 ga teng bo'lmagan manba uchun (masalan, ikkilik manbalar uchun),
Do'stlaringiz bilan baham: |
