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

Ma'lumotlarni kiritish
Kirish ma'lumotlari butun sondan boshlanadi T, alohida satrda joylashgan va keyingi test holatlari sonini ko'rsatadi. Keyinchalik, har biri T test holatlari, ularning har biri joylashgan 3 --chi qatorlar quyidagicha:

• 
  Sinov ishidagi alohida belgilar soni Z (2 ≤ Z ≤ 20 );
  
• 
  Raqam N ko'rsatuvchi " N- "Huffman daraxtining tabiati ( 2 ≤ N ≤ 10 );
  
• 
  Qabul qilingan xabarning sarlavhasini ifodalovchi satr, har bir belgi diapazondagi raqam bo'ladi ... Ushbu qator kamroq bo'ladi 200 belgilar.
  

Eslatma: Kamdan kam bo'lsa-da, dekodlashda sarlavha bir nechta talqinlarga ega bo'lishi mumkin (masalan, sarlavha uchun " 010011101100 ", va qadriyatlar Z = 5 va N = 2). Kirish ma'lumotlarida taklif qilingan barcha test holatlarida yagona yechim mavjudligi kafolatlanadi.
Chiqish
Har biri uchun T test holatlarining chiqishi Z har birining dekodlangan versiyasini beruvchi qatorlar Z belgilar ortib borayotgan tartibda. Formatdan foydalaning original-> kodlash, qayerda original- bu kasrli raqam oralig'ida va ushbu belgilar uchun tegishli kodlangan raqamlar qatori (har bir raqam ≥ 0 va< N).

1. 
   kod = oqimdan keyingi bit, uzunlik = 1
   
2. 
   Kod paytida< base
   kod = kod<< 1
   kod = kod + oqimdan keyingi bit
   uzunlik = uzunlik + 1
   
3. 
   belgi = simb + kod - tayanch]
   

Faraz qilaylik, (2) dagi halqa bir necha marta takrorlangandan so'ng to'xtaydi. Bunday holda, ifoda (kod - asos) uzunlik darajasida kerakli tugunning (belgining) tartib raqamidir. Daraxtdagi uzunlik darajasidagi birinchi tugun (belgi) offs indeksidagi ramzlar qatorida joylashgan. Lekin bizni birinchi belgi emas, balki raqam ostidagi belgi (kod - tayanch) qiziqtiradi. Shuning uchun simb massividagi kerakli belgi indeksi (offs + (kod - tayanch)) bo'ladi. Boshqacha qilib aytganda, talab qilinadigan belgi simvol = simb + kod - tayanch].
Keling, aniq bir misol keltiraylik. Ta'riflangan algoritmdan foydalanib, biz Z / xabarini dekodlaymiz.
Z / = "0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 01101010"

1. 
   kod = 0, uzunlik = 1
   
2. 
   kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   uzunlik = 1 + 1 = 2
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   uzunlik = 2 + 1 = 3
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 1 = 1
   uzunlik = 3 + 1 = 4
   kod = 1 = tayanch = 1
   
3. 
   belgi = simb = 2 + kod = 1 - tayanch = 1] = simb = A
   

1. 
   kod = 1, uzunlik = 1
   
2. 
   kod = 1 = tayanch = 1
   
3. 
   simvol = symb = 7 + kod = 1 - tayanch = 1] = simb = H
   

1. 
   kod = 0, uzunlik = 1
   
2. 
   kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   uzunlik = 1 + 1 = 2
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   uzunlik = 2 + 1 = 3
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   uzunlik = 3 + 1 = 4
   kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 1 = 1
   uzunlik = 4 + 1 = 5
   kod = 1> tayanch = 0
   
3. 
   ramz = simb = 0 + kod = 1 - tayanch = 0] = simb = F
   

Shunday qilib, biz dastlabki 3 ta belgini dekodladik: A, H, F... Ushbu algoritmdan so'ng biz aniq S xabarini olishimiz aniq.

Kod uzunligini hisoblash

Xabarni kodlash uchun biz belgilar kodlarini va ularning uzunligini bilishimiz kerak. Oldingi bo'limda ta'kidlanganidek, kanonik kodlar ularning uzunligi bilan yaxshi aniqlanadi. Shunday qilib, bizning asosiy vazifamiz kodlarning uzunligini hisoblashdir.
Ma'lum bo'lishicha, bu vazifa, aksariyat hollarda, Huffman daraxtini qurishni talab qilmaydi. Bundan tashqari, Huffman daraxtining ichki (yo'q) tasviridan foydalanadigan algoritmlar tezlik va xotira iste'moli nuqtai nazaridan ancha samaralidir.
Bugungi kunda kodlar uzunligini (,) hisoblash uchun juda ko'p samarali algoritmlar mavjud. Biz ulardan faqat bittasini ko'rib chiqish bilan cheklanamiz. Bu algoritm juda oddiy, ammo shunga qaramay u juda mashhur. U zip, gzip, pkzip, bzip2 va boshqalar kabi dasturlarda qo'llaniladi.
Keling, Huffman daraxtini qurish algoritmiga qaytaylik. Har bir iteratsiyada biz eng kam og'irlikdagi ikkita tugun uchun chiziqli qidiruvni amalga oshirdik. Shubhasiz, bu maqsad uchun piramida (minimal) kabi ustuvor navbat ko'proq mos keladi. Eng kam vaznga ega bo'lgan tugun eng yuqori ustuvorlikka ega bo'ladi va piramidaning tepasida bo'ladi. Keling, ushbu algoritmni keltiramiz.
Keling, barcha kodlangan belgilarni piramidaga kiritaylik.
Keling, piramidadan 2 ta tugunni ketma-ket ajratib olaylik (bu eng kichik og'irlikdagi ikkita tugun bo'ladi).
Keling, yangi tugun hosil qilaylik va unga bolalarcha, piramidadan olingan ikkita tugunni biriktiramiz. Bunday holda, hosil bo'lgan tugunning og'irligi bola tugunlari og'irliklarining yig'indisiga teng ravishda o'rnatiladi.
Keling, hosil bo'lgan tugunni piramidaga kiritamiz.
Agar piramidada bir nechta tugun bo'lsa, unda 2-5 ni takrorlang.
Har bir tugun uchun uning ota-onasiga ko'rsatgich saqlangan deb taxmin qilamiz. Daraxtning ildizida ushbu ko'rsatkichni NULL ga o'rnating. Endi barg tugunini (belgi) tanlaymiz va saqlangan ko'rsatkichlar bo'yicha keyingi ko'rsatkich NULL bo'lguncha daraxtga ko'tarilamiz. Oxirgi shart daraxtning ildiziga yetganimizni bildiradi. Ko'rinib turibdiki, darajadan darajaga o'tishlar soni barg tugunining (belgi) chuqurligiga va shuning uchun uning kodining uzunligiga teng. Shu tarzda barcha tugunlarni (ramzlarni) chetlab o'tib, biz ularning kodlari uzunligini olamiz.

Maksimal kod uzunligi

Qoida tariqasida, deb ataladigan kod kitobi, oddiy ma'lumotlar strukturasi, asosan ikkita massiv: biri uzunliklari, ikkinchisi kodlari bilan. Boshqacha qilib aytganda, kod (bit qatori sifatida) xotira joyida yoki qattiq o'lchamdagi registrda saqlanadi (odatda 16, 32 yoki 64). To'lib ketishining oldini olish uchun kod registrga mos kelishiga ishonch hosil qilishimiz kerak.
Ma'lum bo'lishicha, N-belgili alifboda maksimal kod hajmi (N-1) bitgacha bo'lishi mumkin. Boshqacha qilib aytganda, N = 256 (umumiy variant) uchun biz 255 bit uzunlikdagi kodni olishimiz mumkin (garchi buning uchun fayl juda katta bo'lishi kerak: 2.292654130570773 * 10 ^ 53 ~ = 2 ^ 177.259)! Bunday kod registrga mos kelmasligi aniq va siz u bilan biror narsa qilishingiz kerak.
Birinchidan, qanday sharoitlarda toshib ketishini bilib olaylik. i-simvolning chastotasi i-chi Fibonachchi soniga teng bo'lsin. Masalan: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Keling, tegishli Huffman daraxtini quramiz.
ROOT / \ / \ / \ / \ H / \ / \ /\ G / \ / \ /\ F / \ / \ /\ E / \ / \ /\ D / \ / \ /\ C / \ / \ A B
Bunday daraxt deyiladi degeneratsiya... Uni olish uchun belgilar chastotasi hech bo'lmaganda Fibonachchi raqamlari yoki hatto tezroq o'sishi kerak. Amalda, haqiqiy ma'lumotlarga ko'ra, bunday daraxtni olish deyarli imkonsiz bo'lsa-da, uni sun'iy ravishda yaratish juda oson. Har holda, bu xavfni hisobga olish kerak.
Ushbu muammoni ikkita maqbul yo'l bilan hal qilish mumkin. Birinchisi kanonik kodlarning xususiyatlaridan biriga asoslanadi. Gap shundaki, kanonik kodda (bit string) kamida muhim bitlar nolga teng bo'lmasligi mumkin. Boshqacha qilib aytganda, boshqa barcha bitlar umuman saqlanmasligi mumkin, chunki ular har doim nolga teng. N = 256 bo'lsa, qolgan barcha bitlar nolga teng bo'lsa, har bir koddan faqat kamida muhim 8 bitni saqlashimiz kifoya. Bu muammoni hal qiladi, lekin faqat qisman. Bu kodlashni ham, dekodlashni ham ancha murakkablashtiradi va sekinlashtiradi. Shuning uchun bu usul amalda kamdan-kam qo'llaniladi.
Ikkinchi yo'l - kodlarning uzunligini sun'iy ravishda cheklash (qurilish paytida yoki undan keyin). Bu usul odatda qabul qilingan, shuning uchun biz bu haqda batafsilroq to'xtalamiz.
Uzunlikni cheklovchi kod algoritmlarining ikki turi mavjud. Evristik (taxminan) va optimal. Ikkinchi turdagi algoritmlar amalga oshirishda ancha murakkab va, qoida tariqasida, birinchisiga qaraganda ko'proq vaqt va xotirani talab qiladi. Evristik jihatdan cheklangan kodning samaradorligi uning optimal cheklangan koddan chetga chiqishi bilan belgilanadi. Farqi qanchalik kichik bo'lsa, shuncha yaxshi. Shuni ta'kidlash kerakki, ba'zi evristik algoritmlar uchun bu farq juda kichik (,,), bundan tashqari, ular juda tez-tez optimal kodni yaratadilar (garchi ular bu har doim shunday bo'lishiga kafolat bermaydi). Bundan tashqari, beri amalda toshib ketish juda kamdan-kam hollarda sodir bo'ladi (agar maksimal kod uzunligiga juda qattiq cheklov o'rnatilmagan bo'lsa); kichik alifbo o'lchami bilan oddiy va tez evristik usullardan foydalanish maqsadga muvofiqdir.
Biz bitta oddiy va juda mashhur evristik algoritmni ko'rib chiqamiz. U zip, gzip, pkzip, bzip2 va boshqa ko'plab dasturlarda o'z yo'lini topdi.
Maksimal kod uzunligini cheklash muammosi Huffman daraxtining balandligini cheklash muammosiga teng. E'tibor bering, qurilishga ko'ra, Huffman daraxtining barg bo'lmagan har qanday tugunining ikkita avlodi bor. Algoritmimizning har bir iteratsiyasida biz daraxt balandligini 1 ga kamaytiramiz. Shunday qilib, L maksimal kod uzunligi (daraxt balandligi) bo'lsin va uni L / & lt L bilan cheklash talab qilinadi. Keyinchalik RN i eng o'ng bo'lsin. barg tuguni i darajasida va LN i - eng chap tomonda.
Keling, L darajasidan boshlaylik. RN L tugunini ota-onasining joyiga o'tkazing. Chunki tugunlar juft bo'lib ketadi, biz RN L ga ulashgan tugun uchun joy topishimiz kerak. Buning uchun j & lt (L-1) bo'lgan barg tugunlari bo'lgan L ga eng yaqin j darajasini toping. LN j o'rniga biz varaq bo'lmagan tugunni hosil qilamiz va unga LN j tugunini va L darajasidan bo'linmagan tugunni bolalar sifatida biriktiramiz. Biz L darajasidagi qolgan barcha tugun juftlariga bir xil amalni qo'llaymiz. Tugunlarni shu tarzda qayta taqsimlash orqali biz daraxtimizning balandligini 1 ga qisqartirganimiz aniq. Endi u (L-1) ga teng. Agar hozir L / & lt (L-1) bo'lsa, biz daraja (L-1) va boshqalar bilan ham xuddi shunday qilamiz. kerakli chegaraga yetguncha.
Keling, misolimizga qaytaylik, bu erda L = 5. Maksimal kod uzunligini L / = 4 ga cheklaylik.
ROOT / \ / \ / \ / \ H C E / \ / \ / \ / \ /\ A D G / \ / \ B F
Ko'rinib turibdiki, bizning holatimizda RN L = F, j = 3, LN j = C... Birinchidan, RN L = tugunini harakatlantiring F ota-onasi o'rniga.
ROOT / \ / \ / \ / \ H / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ C E / \ / \ / \ / \ F A D G B(ulanmagan tugun)
Endi LN j = o'rniga C Bargsiz tugun hosil qilaylik.
ROOT / \ / \ / \ / \ H E / \ / \ / \ / \ / \ / \ F A D G ? ? B(ulanmagan tugun) C(ulanmagan tugun)
Keling, hosil bo'lgan tugunga ikkita ajratilmaganni biriktiramiz: B va C.
ROOT / \ / \ / \ / \ H / \ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ /\ E / \ / \ / \ / \ / \ / \ F A D G B C
Shunday qilib, biz maksimal kod uzunligini 4 ga cheklab qo'ydik. Kod uzunliklarini o'zgartirish orqali biz samaradorlikni biroz yo'qotganimiz aniq. Shunday qilib, bunday kod bilan kodlangan S xabari hajmi 92 bit bo'ladi, ya'ni. Minimal zaxiradan ortiq 3 bit.
Kodning maksimal uzunligini qanchalik cheklasak, kodning samaradorligi shunchalik kam bo'lishi aniq. Keling, maksimal kod uzunligini qancha cheklashingiz mumkinligini bilib olaylik. Shubhasiz, bir ozdan qisqa emas.

Kanonik kodlarni hisoblash

Ko'p marta ta'kidlaganimizdek, kodlarning uzunligi kodlarni o'zi yaratish uchun etarli. Buni qanday qilish mumkinligini sizga ko'rsatamiz. Aytaylik, biz allaqachon kodlarning uzunligini hisoblab chiqdik va har bir uzunlikdagi qancha kod borligini hisobladik. L maksimal kod uzunligi va T i i uzunlikdagi kodlar soni bo'lsin.
Biz S i - ni hisoblaymiz boshlang'ich qiymati i uzunligi kodi, barcha i dan
S L = 0 (har doim)
S L-1 = (S L + T L) >> 1
S L-2 = (S L-1 + T L-1) >> 1
...
S 1 = 1 (har doim)
Bizning misolimiz uchun L = 5, T 1 .. 5 = (1, 0, 2, 3, 2).
S 5 = 00000 bin = 0 dek
S 4 = (S 5 = 0 + T 5 = 2) >> 1 = (00010 bin >> 1) = 0001 bin = 1 dek
S 3 = (S 4 = 1 + T 4 = 3) >> 1 = (0100 bin >> 1) = 010 bin = 2 dek
S 2 = (S 3 = 2 + T 3 = 2) >> 1 = (100 bin >> 1) = 10 bin = 2 dek
S 1 = (S 2 = 2 + T 2 = 0) >> 1 = (10 bin >> 1) = 1 bin = 1 dek
Ko'rinib turibdiki, S 5, S 4, S 3, S 1 aynan belgilar kodlari B, A, C, H... Ushbu ramzlarni ularning barchasi birinchi o'rinda turishi, har biri o'z darajasida birlashtiradi. Boshqacha qilib aytganda, biz har bir uzunlik (yoki daraja) uchun dastlabki kod qiymatini topdik.
Endi qolgan belgilarga kodlar belgilaymiz. I darajadagi birinchi belgining kodi S i, ikkinchisi S i + 1, uchinchisi S i + 2 va boshqalar.
Keling, misolimiz uchun qolgan kodlarni yozamiz: