Axborotni lug‘atli Lempel-Ziv arxivlash usullari

Axborotni iboralarga bo‘lish	a	aa	b	ba	baa	baaa
bab
Raqamlarga ajratish	1	2	3	4	5	6	7
Natija	(0,a)	(1,a)	(0,b)	(3,a)	(4,a)	(5,a)	(4,b)

Axborotdagi har bir harf yoki iboralar (harflar birlashmasi) o‘zidan oldin qaytarilgan iboralar (harflar birlashmasi) va qo‘shuv mavjud bo‘lgan simvol bilan kodlanadi. Masalan oxirgi uchta belgi 4 (“b”) iborasi sifatida kodlashtiriladi.

Ko‘rsatkichning oldinga siljish uzoqligi cheklanmagan (ya’ni, oyna yo‘q), shuning uchun kodlash bajarilayotganida jumlalarning to‘planib borishi ko‘payadi. Ularning ixtiyoriy ravishda ko‘p miqdoriga yo‘l qo‘yilishi ko‘rsatkich o‘lchamini kattalashtirishni talab etadi. R jumla ajratilgan bo‘lsa, ko‘rsatkich [log R] bitlari sifatida taqdim etiladi. Amaliyotda lug‘at cheksiz ravishda o‘sib borishi mumkin emas. Foydalanish mumkin bo‘lgan xotira to‘lganidan so‘ng, u tozalanadi va yangi matn boshidan boshlangani singari kodlash davom etadi. LZ78 ning eng yaxshi amaliy hususiyati, kiritish yordamida raqamli qidiruv daraxtidan samarali qidiruv hisoblanadi. Har bir tugun tomonidan taqdim etiladigan jumla raqamini o‘z ichiga oladi. Chunki kiritiladigan jumla undan oldingilardan biriga faqat bitta simvolga uzunroq bo‘ladi, bunda ushbu operatsiyani amalga oshirish uchun kodlovchi daraxtdan bitta shox pastga tushishi kerak bo‘ladi. LZ78 ning muhim nazariy xususiyati joriy matnni statsionar ergodik manba bilan ishlab chiqarishdagi kiritishning ma’lum darajada oshishida siqish optimalroq bo‘lib hisoblanishidir. Bu shuni anglatadiki, LZ78 manba entropiyasi tomonidan belgilangan minimal o‘lchamga cheksiz uzunlikdagi satrni keltiradi. Faqat ayrim siqish usullari ushbu xususiyatga egadir. Agar u tomonidan amalga oshiriladigan istalgan ketma-ketlik uni o‘z uzunligining o‘sishiga nisbatan aniqroq xarakterlasa, manba ergodik hisoblanadi. Bu o‘ta zaif cheklash bo‘lganligi tufayli, LZ78 matnlarni siqish muammosining yechimi bo‘lib ko‘rinishi mumkin. Biroq, optimallik kiritish hajmi cheksizlikka intilishida hosil bo‘ladi, matnlarning ko‘pchiligi esa ancha qisqaroqdir. Bu jumlani butun kodning o‘lchamidan ancha kichik bo‘lgan aniq simvol o‘lchamiga asoslangan. Uning uzunligi 8 bit bo‘lganligi bois, 2^40 jumlani yaratishda u atigi chiqarishning 20 % ni egallaydi. Agar davomiylikdagi kiritish imkoni bo‘lganida ham xotirani siqish optimal bo‘lishidan ancha ilgariroq to‘ldiririladi. Real vazifa - LZ78 qanchalik tez ushbu chegaraga mos kelishini ko‘rishdir. Amaliyotda ko‘rganimizdek, muvofiqlik bu nisbatan sekinlikdir, LZ77 bilan qiyoslash usuli shundan iborat.
Hozirgi kunga kelib LZ oilasiga mansub bo‘lgan algoritmlar ichida eng samaraliroqlaridan biri bu LZSS algoritmi hisoblanadi. Ushbu algoritm 1982 yilda Storer va Szimanskilar tomonidan LZ77 algoritmini modifikatsiyalash natijasida paydo bo‘ldi. Ushbu algoritm vositasida axborotni kodlashtirilsa siqish koeffitsientining qiymati bir necha barobar katta. Ushbu algoritm asosida axborotni kodlashtirishga misol ko‘rib chiqamiz (2.6-jadval).
2.6-jadval
Hisoblash natijalari