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

B= S 5 = 00000 bin	A= S 4 = 0001 bin	C= S 3 = 010 bin
H= S 1 = 1 bin
F= S 5 + 1 = 00001 bin	D= S 4 + 1 = 0010 bin	E= S 3 + 1 = 011 bin
	G= S 4 + 2 = 0011 bin

Ko'rinib turibdiki, biz xuddi kanonik Huffman daraxtini qurganimiz kabi bir xil kodlarni oldik.

Kod daraxtidan o'tish

Kodlangan xabarni dekodlash uchun dekoderda kodlash uchun ishlatilgan bir xil kod daraxti (u yoki bu shaklda) bo'lishi kerak. Shuning uchun, kodlangan ma'lumotlar bilan birgalikda biz tegishli kod daraxtini saqlashga majburmiz. Bu qanchalik ixcham bo'lsa, shuncha yaxshi ekanligi aniq.
Ushbu muammoni hal qilishning bir necha yo'li mavjud. Eng aniq yechim- daraxtni aniq saqlang (ya'ni, u yoki bu turdagi tugunlar va ko'rsatkichlarning tartiblangan to'plami sifatida). Bu, ehtimol, eng behuda va samarasiz yo'ldir. Amalda, u ishlatilmaydi.
Belgilar chastotalari ro'yxati (ya'ni chastota lug'ati) saqlanishi mumkin. Uning yordami bilan dekoder kod daraxtini osongina qayta qurishi mumkin. Bu usul avvalgisiga qaraganda kamroq isrofgar bo'lsa-da, bu eng yaxshisi emas.
Nihoyat, kanonik kodlarning xususiyatlaridan biri foydalanish mumkin. Yuqorida aytib o'tilganidek, kanonik kodlar ularning uzunligi bilan to'liq aniqlanadi. Boshqacha qilib aytadigan bo'lsak, dekoderning barcha ehtiyojlari belgilar kodlari uzunligi ro'yxatidir. N-belgili alifbo uchun bitta kod uzunligini o'rtacha hisobda [(log 2 (log 2 N))] bitlarda kodlash mumkinligini hisobga olsak, biz juda ko'p narsani olamiz. samarali algoritm... Biz u haqida batafsilroq to'xtalamiz.
Faraz qilaylik, alifbo o'lchami N = 256, va biz oddiyni siqamiz matn fayli(ASCII). Katta ehtimol bilan biz bunday faylda alifbomizdagi barcha N belgilarni topa olmaymiz. Keyin etishmayotgan belgilar kodining uzunligini qo'yamiz nolga teng... Bunday holda, saqlangan kod uzunliklari ro'yxati birgalikda guruhlangan etarlicha katta miqdordagi nollarni (etishmayotgan belgilarning kod uzunligi) o'z ichiga oladi. Har bir bunday guruh guruh kodlash deb ataladigan - RLE (Run - Length - Encoding) yordamida siqilishi mumkin. Bu algoritm juda oddiy. Bir qatordagi M bir xil elementlar ketma-ketligi o'rniga biz ushbu ketma-ketlikning birinchi elementini va uning takrorlanish sonini saqlaymiz, ya'ni. (M-1). Misol: RLE ("AAAABBBCDDDDDDD") = A3 B2 C0 D6.
Bundan tashqari, bu usul biroz kengaytirilishi mumkin. Murojaat qilishimiz mumkin RLE algoritmi nafaqat nol uzunlikdagi guruhlarga, balki qolganlarning hammasiga. Kod daraxtini o'tkazishning bu usuli keng tarqalgan va ko'pgina zamonaviy ilovalarda qo'llaniladi.

Xulosa
Umuman olganda, optimallashtirish masalalari xuddi shunday geometrik talqinga ega. Muammoli rejalar to'plami cho'qqilari mos yozuvlar rejalariga mos keladigan ko'pburchakni ifodalaydi. Masalani yechishda maqsad funksiyasining katta qiymatiga ega bo‘lgan ko‘pburchakning bir cho‘qqisidan boshqasiga uning optimal qiymati olinmaguncha o‘tish amalga oshiriladi. E'tibor bering, optimallashtirish usullarining samaradorligi aniq cho'qqilarni qidirish (iteratsiya) faqat maqsad funktsiyasining eng katta o'sishi yo'nalishida amalga oshirilishida. Shuning uchun, juda ko'p sonli barcha cho'qqilar emas, balki faqat ekstremalga yaqinroq bo'lganlar hisobga olinadi.
Optimallashtirish masalalari sinfini aniqlashda va uni yechish usulini tanlashda amalga oshirilishi mumkin bo‘lgan yechimlar to‘plamining qavariq yoki qavariq bo‘lmaganligini, chiziqli yoki chiziqli bo‘lmagan maqsad funksiya ekanligini bilish kerak.
Fayllarni siqish qanday ishlashi haqida kam odam o'ylaydi. Oldingi foydalanish bilan solishtirganda shaxsiy kompyuter bu juda osonlashdi. Va u bilan ishlaydigan deyarli har bir kishi fayl tizimi arxivlardan foydalanadi. Ammo ularning qanday ishlashi va fayllar qanday siqilganligi haqida kam odam o'ylaydi. Ushbu jarayonning birinchi versiyasi Huffman kodlari bo'lib, ular bugungi kungacha turli mashhur arxivchilarda qo'llaniladi. Ko'pgina foydalanuvchilar faylni siqish qanchalik oson va u qanday ishlashi haqida o'ylamaydilar. Ushbu mustaqil ishda biz siqilish qanday sodir bo'lishini ko'rib chiqamiz, qanday nuanslar kodlash jarayonini tezlashtirish va soddalashtirishga yordam beradi, shuningdek, kodlash daraxtini qurish printsipi nima ekanligini aniqlaymiz.


FOYDALANILGAN ADABIYOTLAR:
https://uz.delachieve.com/chiziqli-dasturlash/
https://bumotors.ru/uz/metod-szhatiya-haffmana-kody-haffmana-primery-primenenie.html