Huffman kodlari: misollar, dastur

Hozirgi vaqtda kamdan-kam odam siqishni ishlashi haqida o'ylaydi. O'tmish bilan taqqoslaganda, shaxsiy kompyuterdan foydalanish ancha osonlashdi. Va fayl tizimi bilan ishlaydigan deyarli har bir kishi arxivdan foydalanadi. Biroq, ularning ko'pchiligi qanday ishlashlari haqida o'ylashadi va fayllarni siqishni qaysi printsipga bog'liq. Ushbu jarayonning birinchi versiyasi Huffman kodlari bo'lib, ular hali ham turli xil mashhur arxivlarda qo'llaniladi. Ko'p foydalanuvchilar faylni siqishni qanchalik oson va u qaysi sxema bo'yicha ishlayotganligini ham o'ylamaydilar. Ushbu maqolada biz siqishni qanday ishlashini ko'rib chiqamiz, kodlash jarayonini tezlashtirish va soddalashtirishga yordam beradigan nuanslar, shuningdek, kodlash daraxtini yaratish printsipi nima ekanini tushunamiz.

Algoritm tarixi

Elektron axborotlarni samarali kodlash bo'yicha dastlabki algoritm Xafman XX asr o'rtalarida, ya'ni 1952 yilda taklif qilingan koddir. Ma'lumotni qisqartirish uchun yaratilgan ko'pgina dasturlarning asosiy asosiy elementi hisoblanadi. Hozirgi vaqtda bu kodni ishlatadigan eng ommabop manbalardan biri ZIP, ARJ, RAR arxivlari va boshqalar. Ushbu Huffman algoritmi JPEG va boshqa grafik ob'ektlarni siqish uchun ham ishlatiladi. Va barcha zamonaviy fakslar 1952 yilda kashf etilgan kodlashni ham qo'llaydi. Kod yaratilganidan bu qadar ko'p vaqt o'tganiga qaramasdan, bugungi kunga qadar eski va zamonaviy turdagi yangi kabuklarda va uskunalarda qo'llanilmoqda.

Samarali kodlash tamoyili

Huffman algoritmining asoslari eng ehtimoliy, eng tez-tez uchraydigan belgilarni o'zaro tizim kodlari bilan almashtirish imkonini beruvchi sxema. Va kamroq tarqalganlar o'rniga ko'proq kodlar almashtiriladi. Uzoq Huffman kodlariga o'tish tizimda barcha minimal qiymatlardan foydalanilgandan so'ng sodir bo'ladi. Ushbu usul, asl xabarning har bir belgi uchun kod uzunligini kamaytirish imkonini beradi. Muhim nuqta, kodlash boshida harflar paydo bo'lish ehtimolligi allaqachon ma'lum bo'lishi kerak. Ularning yakuniy xabari tuziladi. Ushbu ma'lumotlarga asoslanib, Huffman kod daraxti qurilib, uning asosida arxivdagi harflarni kodlash jarayoni amalga oshiriladi.

Huffmanning kodi, misol

Algoritmni ko'rsatish uchun, keling, kod daraxtini yaratishning grafik variantini ko'rib chiqamiz. Ushbu usulni qo'llash samarali bo'lganligi sababli, ushbu usulning kontseptsiyasi uchun zarur bo'lgan ayrim qadriyatlar ta'rifini aniqlab olish maqsadga muvofiqdir. Nodlardan tugunga yo'naltirilgan yoy va tugunlar to'plami odatda grafik deb ataladi. Daraxtning o'ziga xos xususiyatlari quyidagilardir:

• Har bir tugunda yoylarning birortasidan ko'pi o'tishi mumkin emas;
• Nodulardan biri daraxtning ildizi bo'lishi kerak, ya'ni unda hech qanday yoy bo'lmasligi kerak;
• Agar ildizdan yoylar bo'ylab harakatlanishni boshlasangiz, bu jarayon tugunlarning har qanday qismiga to'liq o'tishga imkon beradi.

Huffman kodlariga kiritilgan bunday tushunchalar daraxt bargidek mavjud. Bu chuqur qochib ketmasligi kerak bo'lgan tugun. Ikkita tugunni bir kamon bilan ulashgan bo'lsa, ulardan bittasi ota-ona, ikkinchisi esa, chuqurning qaysi tugunidan kelganligi va qaysi biri ichkarida ekanligi bilan bog'liq. Agar ikkita tugun bir xil ota-ona tuguniga ega bo'lsa, ular odatda birodarlashgan nodlar deb ataladi. Agar barglardan tashqari, tugunlarda bir nechta yoy bor bo'lsa, bu daraxt ikkilik deb ataladi. Bu aniq Huffman daraxti. Ushbu qurilish tugunlarining o'ziga xos xususiyati shundaki, har bir ota-onaning vazni uning nodal bolalari vazniga tengdir.

Huffmanga ko'ra, daraxt qurish algoritmi

Huffman kodini qurish alfavitning harflaridan olingan. Kelajakda kod daraxti uchun bepul bo'lgan ushbu tugunlar ro'yxati yaratiladi. Ushbu ro'yxatdagi har bir tugunning vazni ushbu tugunga mos keladigan xabar xatining paydo bo'lishi ehtimoli bilan bir xil bo'lishi kerak. Bunday holda, kelajak daraxtning bir nechta bepul tugunlari orasida eng kam og'irligi tanlanadi. Shu bilan birga, agar minimal ko'rsatkichlar bir nechta tugunlarda kuzatilsa, unda har qanday juftni erkin tanlash mumkin. Shundan so'ng, ota-ona tugunlari yaratiladi, bu esa bu juftlikning og'irligi bilan teng darajada tortilishi kerak. Shundan so'ng, ota-ona erkin nodlar bilan ro'yxatga yuboriladi va bolalar o'chiriladi. Shu bilan birga, yoylar tegishli indekslarni, shuningdek, nollarni oladi. Bu jarayon faqat bitta tugunni qoldirish uchun zarur bo'lgan darajada takrorlanadi. Keyin ikkilik raqamlar yuqoridan pastga yoziladi.

Siquv samaradorligini oshirish

Siqilish samaradorligini oshirish uchun kod daraxti qurilayotganda, daraxtga biriktirilgan ma'lum faylda paydo bo'lgan harflar ehtimoli haqidagi barcha ma'lumotlarni ishlatish va ularning ko'plab matnli hujjatlarga tarqalishiga yo'l qo'ymaslik kerak. Agar siz ushbu fayl orqali birinchi marta yurish qilsangiz, siz darhol siqilgan obyektdan kelgan harflarning qanchalik tez-tez bo'lishiga oid statistikani hisoblashingiz mumkin.

Siquv jarayonining tezlashishi

Algoritm ishini jadallashtirish uchun harflar ma'lum bir harfning paydo bo'lish ehtimoli indekslari emas, balki uning paydo bo'lish chastotasi bilan belgilanishi kerak. Buning natijasida algoritm osonlashadi va u bilan ishlash juda tezlashadi. Bu shuningdek, suzuvchi vergul va bo'linishlar bilan bog'liq operatsiyalarni ham to'xtatadi. Bundan tashqari, ushbu rejimda ishlaydigan dinamik Huffman kodi, yoki undan ko'ra algoritm o'zi o'zgarmaydi. Bu, ehtimolliklarning chastotalar bilan bevosita mutanosibligi bilan bog'liq. Faylning yakuniy og'irligi yoki "ildiz" tugunining qayta ishlov beriladigan ob'ektdagi harflar soniga teng bo'lishiga alohida e'tibor qaratishimiz kerak.

Xulosa

Huffman kodlari ko'pgina mashhur dastur va kompaniyalar tomonidan qo'llaniladigan oddiy va uzoq muddatli algoritmdir. Uning soddaligi va ravshanligi har qanday hajmdagi fayllarni siqib chiqarishning samarali natijalariga erishishga va diskda saqlangan maydonni sezilarli darajada kamaytirishga imkon beradi. Boshqacha aytganda, Huffman algoritmi uzoq vaqt o'rganilgan va yaxshi ishlab chiqilgan sxema bo'lib, uning dolzarbligi hozirgi kunga qadar pasaymaydi. Va fayllar hajmini kamaytirish, ularni tarmoq orqali yoki boshqa yo'llar bilan o'tkazish qobiliyati tufayli u osonroq, tezroq va qulayroq bo'ladi. Algoritm bilan ishlaydigan bo'lsak, uning tarkibiy va sifatiga ziyon etkazmasdan, lekin faylning og'irligini kamaytirishning maksimal ta'siriga ega bo'lishingiz mumkin. Boshqacha aytganda, Huffman kodini kodlash fayl o'lchamini siqishni uchun eng ommabop va dolzarb usul bo'lib qoldi va saqlanib turadi.