Oliy ta’lim,fan va innovatsiyalar vazirligi muhammad al‑xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

Huffman siqish usuli. Huffman kodlari: misollar, dastur

Ma'lumotni siqishning nisbatan oddiy usuli fayl uchun Huffman daraxtlari deb ataladigan narsalarni yaratish va uni siqish va undagi ma'lumotlarni ochish uchun ishlatilishi mumkin. Ko'pgina ilovalar ikkilik Huffman daraxtlaridan foydalanadi (masalan, har bir tugun barg yoki ikkita kichik tugunga ega). Biroq, Huffman daraxtlarini qurish mumkin ixtiyoriy raqam pastki daraxtlar (masalan, uchlik yoki umumiy holat, N- daraxtlar kabi).
O'z ichiga olgan fayl uchun Huffman daraxti Z turli belgilar Unda bor Z barglari. Muayyan belgini ifodalovchi ildizdan barggacha bo'lgan yo'l kodlashni belgilaydi va bargga boradigan yo'l bo'ylab har bir qadam kodlashni belgilaydi (bu bo'lishi mumkin). 0 , 1 , ..., (N-1)). Umumiy belgilarni ildizga yaqinroq, kamroq tarqalgan belgilarni esa ildizdan uzoqroqqa joylashtirish orqali kerakli siqilishga erishiladi. To'g'ri aytganda, bunday daraxt Huffman daraxti bo'ladi, agar kodlash natijasida minimal raqam bo'lsa. N Belgilangan faylni kodlash uchun -ary belgilar.
Bu masalada biz faqat har bir tugun ichki tugun yoki belgilarni kodlovchi barg bo'lgan va belgini kodlamaydigan ajratilgan barglar mavjud bo'lmagan daraxtlarni ko'rib chiqamiz.
Quyidagi rasmda Huffman uchlik daraxtining namunasi ko'rsatilgan, belgilar " a"va" e"bitta uchlik belgi bilan kodlangan; kamroq tarqalgan belgilar" s"va" p"ikki uchlik belgilar va eng kam uchraydigan belgilar yordamida kodlangan" x", "q"va" y"har biri uchta uchlik belgilar yordamida kodlangan.
Albatta, agar biz ro'yxatni kengaytirmoqchi bo'lsak N-ary belgilar keyin qaytib, ma'lumotlarni siqish uchun qaysi daraxt ishlatilishini bilish muhimdir. Buni bir necha usul bilan amalga oshirish mumkin. Ushbu vazifada biz foydalanamiz keyingi usul: kirish ma'lumotlar oqimidan oldin kodlangan belgilar qiymatlaridan iborat sarlavha bo'ladi Z leksikografik tartibda manba faylida.
Kiritilgan belgilar sonini bilish Z, ma'nosi N ko'rsatuvchi " N Huffman daraxti va sarlavhaning o'zi "arity" kodlangan belgilarning asosiy qiymatini topish kerak.