Axborotni lug‘atli Lempel-Ziv arxivlash usullari. Ushbu usullarning asosida statik arxivlash g‘oyasidan ham yaxshiroq g‘oya yotadi.
Lug‘atli kodlovchi ketma-ketlikdagi simvollar guruhini ayrim lug‘atlar bilan almashtirib kodlashga erishadi. Lug‘at bu tez-tez foydalanilishi kutilayotgan jumlalarning ro‘yhatidir. Indekslar shunday qurilganki, bunda o‘rtacha hisobda ular tomonidan kodlanadigan jumlalarga nisbatan kamroq joy egallaydi, buning hisobiga arxivlashga (siqishga) erishiladi. Shuningdek siqishning ushbu turi «makro» - kodlash yoki «kodlar kitobi» usuli singari mashhurdir.
Lug‘atli usullar odatda tezkordir, ya’ni, bunda chiqishdagi bitta kod bir nechta kirish simvollariga mos keladi va kod o‘lchami odatda mashina so‘zlariga mos keladi. Lug‘atli modellar kontekstli-cheklangan modellar singari yaxshi bo‘lmasada, yetarlicha yaxshi darajadagi siqishni beradi. Lug‘atli kodlovchilarning ko‘pchiligi kontekstli-cheklangan modellar yordamida yozib olinishi mumkinligini ko‘rsatish mumkin, shuning uchun ularning asosiy afzalligi siqish sifati emas, aksincha mashina resurslarini tejash hisoblanadi.
Lug‘at sxemasini loyihalashdagi markaziy qaror kodli lug‘atning yozib olish hajmini tanlash hisoblanadi. Ayrim ishlab chiquvchilar saqlanadigan jumlalarning uzunligiga cheklashlar qo‘yadilar. Ushbu cheklashga nisbatan jumlalarning tanlanishi statik, yarim adaptiv yoki adaptiv usulda amalga oshirilishi mumkin. Oddiy lug‘atli sxemalar qisqa jumlalarni o‘z ichiga oluvchi statik lug‘atlardan foydalanadi. Ular asosan fayl yozuvlarini siqish uchun yaroqlidir, masalan, bibliografik ma’lumotlar bazasi, bunda yozuvlar tasodifiy shaklda dekodlanishi kerak, biroq bunda aynan bitta jumla turli yozuvlarda tez-tez paydo bo‘ladi. Biroq, katta jumlalarga yo‘l qo‘yuvchi adaptiv sxemalar yaxshiroq siqishlarga erishadi. Quyida ko‘rib chiqiladigan Ziv-Lempel siqishida ushbu tavsifga mos keluvchi, hamda boshqa lug‘atli sxemalarni ortda qoldiruvchi siqish usullarining umumiy sinfi mavjud.
Amaliy jihatdan deyarli barcha lug‘atli kodlovchilar Ziv va Lempel ishidan kelib chiquvchi algoritmlar turkumiga taalluqlidir. Mohiyat shundan iboratki, jumlalar ko‘rsatkich tomonidan ular avval matnda paydo bo‘lgan joylarga almashtiriladi. Algoritmlarning ushbu turkumi Ziv-Lempel usuli deb nomlanadi, hamda LZ-siqish singari belgilanadi. Ushbu usul tezkorlik bilan matn strukturasiga moslashadi, hamda qisqa funksional so‘zlarni kodlashi mumkin, chunki ular u yerda haddan ziyod ko‘p marotaba paydo bo‘ladi. Shuningdek yangi so‘zlar va jumlalar avval uchragan so‘zlarning qismidan shakllanishi mumkin. Siqilgan matnning kodini ochilishi to‘g‘ridan-to‘g‘ri amalga oshiriladi – ko‘rsatkichni lug‘atdagi u ko‘rsatayotgan tayyor jumla bilan oddiy almashtirish amalga oshiriladi.
LZ-usuli amaliyotida yaxshiroq siqishga harakat qiladi, uning muhim hususiyati kodni ochuvchining o‘ta tezkor harakati hisoblanadi. Bunday ko‘rsatkich shakllaridan bittasi bu (m,1) juftligidir, bu kiruvchi oqimda m ni almashtirishdan boshlanuvchi 1 simvollaridan iborat jumlani almashtiradi. Masalan, ko‘rsatkich (7,2) dastlabki satrning 7 va 8-simvollarni adreslaydi. Ushbu simvoldan foydalangan holda, «abbaabbbabab» satri «abba (1,3) (3,2) (8,3)» singari kodlanishi kerak. LZ-usuli tushunchasi ostida yagona algoritm turganligi to‘g‘risidagi noto‘g‘ri tushuncha tarqalgan. Birinchi navbatda bu ikkita har xil siqish algoritmiga olib kelgan «murakkablik» satrini o‘lchash uchun variant edi. Ushbu izoh LZ-siqish o‘zi aslida nima ekanligi to‘g‘risidagi noma’lum tushunchani hosil qiluvchi ko‘p yangiliklarni o‘z ichiga oladi. Ushbu usulning variantlarini ko‘pligi tufayli uning o‘sib boruvchi turkumi orqali eng yaxshi tavsiflarni amalga oshirish mumkin, bunda har bir a’zo o‘z ishlab chiquvchilik qarorini aks ettiradi. Ushbu versiyalar ikkita bosh omillarda bir-biridan farq qiladi: ko‘rsatkichning orqaga harakatining chegarasi bormi va ushbu ko‘plikdan u qanday satr ostiga havola qilishi mumkin. Ko‘rsatkichning avval ko‘rib chiqilgan matn qismiga siljishi cheklanmagan bo‘lishi mumkin (kengayuvchi oyna) yoki simvoldan avval keluvchi N dan iborat bo‘lgan doimiy o‘lchamdagi oyna bilan cheklangan bo‘lishi mumkin, bunda odatda N bir necha mingni tashkil etadi. Shuningdek tanlangan satrlar osti cheklanmagan yoki ba’zi bir fikrga muvofiq tanlangan ko‘plikdagi jumlalar bilan cheklangan bo‘lishi mumkin. Ushbu shartlarning har bir kombinatsiyasi bajarish tezligi, talab etiladigan operativ xotira hajmi va siqish sifati o‘rtasidagi kompromiss bo‘lib hisoblanadi. Kengayuvchi oyna satrlar ostining katta miqdoridan foydalanishni tashkil etish hisobiga eng yaxshi siqishni taklif etadi. Lekin oynaning kattaligiga ko‘ra tegishli satrlar ostini qidirish vaqtining o‘sishi tufayli kodlovchi o‘z ishini sekinlashtirishi mumkin, siqish esa ko‘rsatkichlar o‘lchamining kattalashishi tufayli yomonlashishi mumkin. Agar oyna uchun xotira yetishmasa, jarayon tashlab yuboriladi, shu bilan birga oynaning yangitdan kattalashish davriga qadar siqishni yomonlashtiradi. Doimiy o‘lchamdagi oyna ushbu muammolardan xolis, biroq ko‘rsatkich foydalanishi mumkin bo‘lgan kamroq satr ostini o‘z ichiga oladi.
Foydalanish mumkin bo‘lgan ko‘plikdagi satrlar ostining qayd etilgan oyna o‘lchami bilan cheklanishi ko‘rsatkichlarning o‘lchamini kichraytiradi va kodlashni tezlashtiradi. LZ-usullarining asosiy variantlari va ularning farqlari 2.4 -jadvalda keltirilgan.
2.4- jadval
LZ-usullarining asosiy turlari va ularning farqlari
