Axborotni lug‘atli Lempel-Ziv arxivlash usullari



Download 130,5 Kb.
bet1/4
Sana26.04.2022
Hajmi130,5 Kb.
#583001
  1   2   3   4

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


Download 130,5 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish