Huffman Kodlari: Misollar, Dastur

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.
ad
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.