Axborotni lug‘atli Lempel-Ziv arxivlash usullari

Nomi	Mualliflari
Farqi
LZ77	Ziv and Lempel [1977]	Ko‘rsatkichlar va sinvollar almashtirib turiladi. Ko‘rsatkichlar satr ostini avvalgi N simvollari orasida adreslaydi.
LZ78	Ziv and Lempel [1978]	Ko‘rsatkichlar va simvollar almashtirib turiladi. Ko‘rsatkichlar avval ko‘rib chiqilgan satr ostini adreslaydi.
LZR	Lempe, Ziv and Roden [1981]	Ko‘rsatkichlar va simvolgilar almashtirib turiladi. Ko‘rsatkichlar satr ostini avvalgi barcha simvollar orasida adreslaydi.

2.1- jadval davomi

LZSS	Lempe, Ziv, Storer and Szimanski [1982]	Ko‘rsatkichlar va simvollar almashtirib turiladi. Ko‘rsatkichlar satr ostini avvalgi barcha simvollar orasida adreslaydi.
LZW	Lempe, Zivand Welch [1984]	Xulosa faqat ko‘rsatkichlarni o‘z ichiga oladi. Ko‘rsatkichlar avval ko‘rib chiqilgan satr ostini adreslaydi. Ko‘rsatkichlar qayd etilgan uzunlikka ega.
LZMW	Lempe, Ziv, Miller and Wegman [1984]	LZTga o‘hshash, lekin jumlalar avvalgi ikkita jumlalarning konkatenatsiyasidan quriladi.
LZC	Lempe, Zivand Thomas [1985]	Hulosa faqat ko‘rsatkichlarni o‘z ichiga oladi. Ko‘rsatkichlar avval ko‘rib chiqilgan satr ostini adreslaydi.
LZJ	Lempe, Zivand Jakobsson [1985]	Xulosa faqat ko‘rsatkichlarni o‘z ichiga oladi. Ko‘rsatkichlar satr ostini avvalgi barcha simvollar orasida adreslaydi.
LZB	Lempe, Zivand Bell [1987]	LZSS ga o‘hshash, lekin ko‘rsatkichlar uchun turli kodlash qo‘llaniladi.
LZH	Lempe, Zivand Hufman [1987]	LZSS ga o‘xshash, lekin ikkinchi qadamda ko‘rsatkichlar uchun Xaffman kodlashi qo‘llaniladi.
LZT	Lempe, Zivand Tischer [1987]	LZCga o‘xshash, lekin jumlalar LRU-ro‘yhatga joylashtiriladi.
LZFG	Lempe, Ziv, Fiala and Greene [1989]	Ko‘rsatkich tugunni raqamli qidirish daraxtidan tanlaydi. Daraxtdagi satrlar sirpanuvchi oynadan olinadi.

Ularning barchasi Ziv va Lempel tavsiflagan hamda LZ77 va LZ78 singari muvofiq ravishda belgilangan ikkita turli yondoshuvlarning bittasidan kelib chiqqan. Ba’zi mualliflar ularning bir hilligi to‘g‘risidagi yanglish fikrlarini bildirsalar ham ushbu ikkita yondoshuv mutlaqo bir biridan farq qiladi. “LZ-sxemalar” atamasi ularning kashfiyotchilari nomidan kelib chiqadi. Odatda har bir keyingi ko‘rib chiqiladigan variant aslida bundan avvalgisining takomillashtirilgani bo‘lib hisoblanadi.

LZ77 - bu birinchi nashr qilingan LZ-usuli edi. Unda ko‘rsatkichlar kod pozitsiyasidan avvalgi doimiy o‘lchamdagi oynadagi jumlalarni ifodalaydi. Ko‘rsatkichlar tomonidan almashtiriladigan satr ostining maksimal uzunligi F parametri bilan belgilanadi (odatda 10-20). Ushbu cheklashlar LZ77 ga N simvollardan iborat «sirpanuvchi oyna»dan foydalanish imkonini beradi. Ulardan birinchi N-F kodlangan bo‘lib, oxirgi F esa oldinga o‘tuvchi buferni tashkil etadi. Belgini kodlashda oynaning birinchi N-F simvollarida ushbu bufer bilan mos keluvchi eng uzun satr qidiriladi. U buferni qisman to‘sib qo‘yishi mumkin, lekin buferning o‘zi bo‘la olmaydi. Topilgan eng ko‘p muvofiqlikdan so‘ng triada bilan kodlanadi, bunda i bufer boshidan uning siljishi, j – muvofiqlik uzunligi, birinchi simvol esa, satr ostiga mos kelmaydigan oyna. So‘ngra oyna o‘ngga, algoritmning yangi qadamiga tayyor j+1 simvolga suriladi. Belgilangan simvolni har bir ko‘rsatkichga bog‘lab qo‘yilishi buferni to‘sib qo‘yuvchi birinchi simvol uchun muvofiqlik topilmaydigan hollarda ham kodlash bajarilishiga kafolat beradi.
Kodlovchi va kodni ochuvchi uchun talab etiladigan hotira hajmi oyna o‘lchami bilan cheklanadi. Triadada (i) ning siljishi [log(N-F)] bitlari tomonidan taqdim etilishi mumkin, triada tomonidan almashtiriladigan simvollarning soni esa, (i) - [logF] bitlari tomonidan taqdim etilishi mumkin. Kodning ochilishi oson va tez amalga oshiriladi. Bunda kodlashdagi oyna bilan ishlash tartibining aynan o‘zi qo‘llab-quvvatlanadi, biroq bir xil satrlarni qidirishdan farqli ravishda u aksincha ulardan navbatdagi triadaga muvofiq oynadan nusxa ko‘chiradi. Nisbatan arzon apparaturada kodni ochishda 10 Mb/sek. tezligiga erishildi. Ziv va Lempellar N ning yetarli darajadagi ko‘pligida LZ77 istalgan va bunga maxsus yo‘naltirilgan yarim adaptatsiyalangan lug‘atli usuldan ham matnni yaxshiroq siqishi mumkinligini ko‘rsatib berdi. Ushbu dalil yarim adaptatsiyalangan sxema kodlanadigan matnning o‘zidan tashqari lug‘atga ham ega bo‘lishi kerakligini tasdiqlaydi, bunda LZ77 uchun lug‘at va matn – aynan bir xildir. Yarim adaptatsiyalangan lug‘at elementining o‘lchami unga mos keluvchi LZ77 da kodlanayotgan matndagi jumlaning o‘lchamidan kam emas.
LZ77 ning har bir kodlash qadami bir xil vaqtni talab etadi, agar u katta bo‘lsa, bu uning asosiy kamchiligi bo‘lib hisoblanadi. Bunda to‘g‘ridan to‘g‘ri amalga oshirish ko‘rilayotgan fragmentda simvollarni tenglashtirish (N-F)*F operatsiyasiga qadar talab etilishi mumkin. Sekin kodlash va tez kodni ochishning ushbu hususiyati ko‘pchilik LZ-sxemalar uchun xarakterlidir. Kodlash tezligi ikkilamchi daraxtlar, raqamli qidiruv yoki hesh-jadval daraxtlari singari tizimlardan foydalanish hisobiga oshirilishi mumkin, biroq bunda talab etiladigan xotira hajmi ham oshib ketadi. Bu amaliyotda, masalan, dialogli ma’lumot fayllari, qo‘llanmalar, yangiliklar, telematnlar va elektron kitoblar bilan ishlashda tez-tez uchrab turadi.
LZR usuli LZ77 ga o‘xshash, bunda u ko‘rsatkichlarga matnning ko‘rib chiqilgan qismida istalgan pozitsiyani adreslash imkonini berishi bundan mustasno. LZ77 uchun bu N parametrini kiruvchi matnning o‘lchamidan katta qilib o‘rnatilishiga o‘xshash. Triadada i va j qiymatlari ixtiyoriy katta qiymatga o‘sishi mumkinligi sababli, ular o‘zgaruvchan uzunlikdagi butun kodlar sifatida taqdim etiladi. Ushbu usul Elias tomonidan qo‘llanilgan va C(w') sifatida belgilangan. Butun musbat sonni kodlashda kod uzunligi logarifmda uning o‘lchamidan oshib ketadi. Masalan, 1,8 va 16 sonlari uchun kodlar muvofiq ravishda 0010,10010000 va 101100000 ga teng bo‘ladi. Lug‘atning kattaligiga qo‘yiladigan cheklanishning yo‘qligi tufayli LZR amaliyotda uncha qo‘llanilmaydi, chunki bunda kodlash jarayoniga matnni joylashtirish uchun muvofiqlik qidiriladigan ko‘proq xotira talab etiladi. Liniyaviy qidiruvdan foydalanishda n simvolli matn O(n^2) vaqtda kodlangan bo‘ladi.
LZSS usuli LZ77 va LZR ishining natijasi bo‘lib qat’iy almashadigan ko‘rsatkich va simvollarni o‘zida ifoda etuvchi triadalar seriyasi hisoblanadi. Har bir ko‘rsatkich izidan aniq simvolning qo‘llanilishi amaliyotda bexuda urinish bo‘lib hisoblanadi, chunki ko‘pincha uni keyingi ko‘rsatkich qismi qilib qo‘yish mumkin.
LZSS ko‘rsatkich va simvollarning erkin aralashmasidan foydalangan holda, ushbu muammo ustida ishlamoqda, bunda oxirgi yaratiladigan ko‘rsatkich u kodlaydigan belgidan katta o‘lchamga ega bo‘lgan hollarda qo‘shiladi. N simvollardan iborat oyna LZ77 dagi kabi qo‘llaniladi, shuning uchun ko‘rsatkichlar o‘lchami doimiydir. Har qaysi ko‘rsatkich yoki simvol uchun bir biridan ajratishga va ishlatilmaydigan bitlarni bartaraf qilish uchun qo‘shimcha bit qo‘shiladi.
LZB bu ular tomonidan adreslanadigan jumlaning uzunligidan qat’iy nazar, har bir ko‘rsatkich LZSS da doimiy o‘lchamga ega. Amaliyotda bitta uzunlikka ega jumlalar boshqalarga nisbatan juda tez-tez uchrab turadi, shuning uchun turli uzunlikdagi ko‘rsatkichlar bilan eng yaxshi siqishga erishish mumkin. LZB aniq simvollar va ularni farqlovchi bayroqlar singari ko‘rsatkichlarni turli kodlash usullarini baholash bo‘yicha tajribalarning natijasi bo‘lib hisoblanadi. Ushbu usul LZSS ga nisbatan juda yaxshi siqishni beradi va parametrlarni tanlashga bo‘lgan qo‘shimcha afzalliklarga ega. Birinchi tashkil etuvchi ko‘rsatkichda oyna boshidan boshlanish pozitsiyasi mavjud. LZB ushbu komponentga nisbatan ishlaydi. Dastlab, simvollar oynada 2 ta bo‘lganida o‘lcham 1 bitga teng bo‘ladi, keyin, oynada 4 ta simvol bo‘lganida 2 ta bitgacha o‘sadi va h., bu oyna N simvolni o‘z ichiga olmaguniga qadar davom etadi. Ikkinchi tashkil etuvchi (jumla uzunligi) ko‘rsatkichni kodlash uchun LZB Elias o‘zgaruvchan uzunlikdagi kodlar sxemasidan foydalanadi – S (gamma). Chunki ushbu kod istalgan uzunlikdagi jumlani o‘zida ifoda etishi mumkin, bunda hech qanday cheklashlar unga qo‘yilmaydi.
LZH usuli ko‘rsatkichlarini taqdim etish uchun LZB bir nechta oddiy kodlarni qo‘llaydi, biroq eng yaxshi taqdim etish arifmetik kodlash yoki Xaffman kodlash vositasida ularni taqsimlash ehtimolligi asosida amalga oshirilishi mumkin. LZH-tizimi LZSS ga o‘hshash, biroq ko‘rsatkich va simvollar uchun Xaffman kodlashini qo‘llaydi. Ushbu statistik kodlovchilardan bittasini LZ-ko‘rsatkichlarga qo‘llashda, katta miqdordagi kodlarni uzatish bo‘yicha sarf-xarajatlar tufayli (hattoki adaptiv rejimda) siqishni yaxshilash qiyinligi ma’lum bo‘ldi. Bundan tashqari yakuniy sxemaga LZ-usulining tezkorligi va oddiyligi yetishmaydi.
LZ algoritmlarini iboralar bo‘yicha arxivlovchi algoritmlar deyiladi, chunki ushbu algoritmlarda axborotdagi iboralar yoki harflar birlashmasi oldinroq qaytarilgan xuddi shunday ibora yoki harflar birlashmasi bilan almashtirishga asoslangan. Iboralar bo‘yicha yo‘qotishsiz arxivlovchi algoritmlarni ayrim adabiyotlarda jadval asosida arxivlovchi algoritmlar ham deyiladi.
Iboralar bo‘yicha arxivlovchi algoritmlarning dastlabkisi 1977 yilda paydo bo‘ldi va ushbu algoritmning nomi LZ77 deb nomlandi. Keyinchalik bir yildan so‘ng ushbu algoritmning modifikatsiyalangan varianti yaratildi va algoritm nomi LZ78 deb atala boshlandi. Keyinchalik ushbu LZ oilasiga mansub bo‘lgan ko‘plab yangi arxivlovchi algoritmlar paydo bo‘ldi.
Ushbu oilaga mansub bo‘lgan eng sodda algoritmlardan biri hisoblanadign LZ78 algoritmi yordamida axborotni kodlashtirish jarayonini ko‘rib chiqamiz. Masalan ushbu “aaabbabaabaaabab” axborotni kodlashtirish talab qilinsin. Ushbu axborotni 2.5-jadvalda ko‘rsatilganidek 7 ta mayda iboralarga (harflar birlashmasi) bo‘lamiz.
2.5-jadval
LZ78 algoritmi yordamida “aaabbabaabaaabab” axborotni kodlashtirish