Axborotni lug‘atli Lempel-Ziv arxivlash usullari

Qadam Siljuvchi oyna

Download 130,5 Kb. bet 4/4 Sana 26.04.2022 Hajmi 130,5 Kb. #583001

Bu sahifa navigatsiya:

• Iboralar Bufer

Qadam	Siljuvchi oyna		Takror -langan ibora
Kodlashtirilgan ma’lumot
	Iboralar	Bufer		f	i	j	s
1	-	AVAADDD	-	0	-	-	A
2	A	VAADDDD	-	0	-	-	V
3	AV	AADDDDD	-	0	-	-	A 0
4	AVA	ADDDDDB	-	0	-	-	A
5	AVAA	DDDDDVA	-	0	-	-	D
6	AVAAD	DDDDVAA	-	0	-	-	D
7	AVAADD	DDDVAAV	DD	1	2	2	-
8	AVAADDDD	DVAAVAA	-	0	-	-	D
9	AVAADDDDD	VAAVAAS	VAA	1	3	8	-
10	AVADDDDDVAA	VAASSSS	VAA	1	3	3	-
11	AVDDDDDVAAVAA	SSSSEAF	-	0	-		C
12	AVAADDDDDVAAVAAS	SSSEAFF	-	0	-	-	C
13	AVAADDDDDVAAVAASS	SSEAFFF	CC	1	2	2	-
14	AVAFDDDDDVAAVAASSSS	YeAFFFFD	-	0	-	-	Ye
15	AVAADDDDDVAAVAASSSSE	AFFFFDA	-	0	-	-	A
16	AVAADDDDDVAAVAASSSSEA	FFFFDAAA	-	0	-	-	F
17	AVAADDDDVAAVAASSSSEAF	FFFDAAA	-	0	-	-	F
18	AVAADDDDVAAVAASSSSEAFF	FFDAAAA	FF	1	2	2	-
19	AVAADDDDVAAVAASSSSEAFFFF	DAAAA	-	0	-	-	D
20	AVAADDDDDVAAVAASSSSEAFFFFD	AAAA	AA	1	2	13	-
21	AVAADDDDDVAAVAASSSSEAFFFFDAA	AA	AA	1	2	2	-

Axborot sifatida quyidagi axborotni olamiz:

AVAADDDDDBAACCCCEAFFFFDAAAA
f – bayroqcha;
i – takrorlangan iboraning uzunligi;
j - takrorlangan iboraning nechta qadam oldin qaytarilganligi;
s – ochiq holatda uzatilgan belgi.
N_chiq= 14*(1+8)+7*(1+3+5) = 189 (bit)
N_kir= 30*8 = 240 bit. Axborot hajmini kamaytirish natijasida olingan yutuq 240-189 = 51 bitga teng.
LZW, LZ78dan LZWga o‘tish, LZ77dan LZSSga o‘tish bilan paralleldir. Har bir jumladan keyin aniq simvolni xulosaga kiritish ko‘pincha bexuda urinish hisoblanadi. LZW ushbu simvollarni har tomonlama boshqaradi, shuning uchun xulosa faqat ko‘rsatkichlarni o‘z ichiga oladi. Bunga dastlabki alifboning barcha simvollarini o‘z ichiga oluvchi jumlalar ro‘yhatini initsializatsiya qilish bilan erishiladi. Har bir yangi jumlaning oxirgi simvoli keyingi jumlaning birinchi simvoli singari kodlanadi. Agar jumla boshqa, bevosita undan oldingi jumla bilan kodlangan bo‘lsa, kodni ochishda yuzaga keladigan vaziyat asosiy e’tiborni talab etadi, lekin bu hal etib bo‘lmaydigan muammo bo‘lib hisoblanmaydi.
LZW dastlab disk kanalining maxsus qurilmasi vositasida ma’lumotlarni diskka yozib olishda ularni siqish usuli sifatida taklif etilgan. Axborot bahosining o‘ta yuqoriligi bois, bunday yondoshuvda muhimi siqish juda tez bajarilishi kerak. Ko‘rsatkichlarning uzatilishi uchun (odatda) 12 bitli doimiy o‘lchamdan foydalanilganda uni soddalashtirish va tezlashtirish mumkin. 4096 jumlaning ajratilishidan keyin yangilarini ro‘yhatga kiritish mumkin emas, hamda kodlash statik bo‘lib qoladi. Bunga bog‘liq bo‘lmagan holda, amaliyotda LZW maqbul siqishga erishadi va adaptiv sxema uchun juda tezkor bo‘lib hisoblanadi. Miller va Vegmanning birinchi varianti LZW ning mustaqil kashfiyoti bo‘lib hisoblanadi.
LZS – ushbu sxema UNIX tizimida foydalaniladigan COMPRESS dasturi tomonidan qo‘llaniladi. Bu LZW amalga oshirish singari boshlangan edi, lekin keyinchalik yaxshiroq va o‘ta tezkor siqishga erishish maqsadida bir necha marotaba o‘zgartirildi. Natija bo‘lib esa yuqori xarakteristikalarga ega sxema hisoblandi, bu esa hozirgi vaqtda o‘ta foydalilardan biri bo‘lib hisoblanadi. Avvalgi modifikatsiya ko‘rsatkichlarga nisbatan LZ78 uzunlikdagi singari o‘zgaruvchan bo‘lib ishlagan. Ko‘rsatkichlar bilan ishlaydigan dastur bo‘limi samaradorlik uchun assemblerda yozilgan edi. Xotiraning lug‘at bilan to‘lishining oldini olish uchun parametr sifatida ko‘rsatkichning maksimal uzunligi (odatda 16 bit, lekin uncha katta bo‘lmagan mashinalar uchun kamroq) uzatilishi kerak. Lug‘at to‘lganidan keyin xotirani tozalash uchun LZS siqish koeffitsientini kuzatadi. Faqat uning yomonlashishi boshlanganidan keyingina lug‘at tozalanadi va eng boshidan yangidan quriladi.
LZT usuli LZS ga asoslangan. Asosiy farqi shundan iboratki, lug‘at to‘lganida yangi jumlalar uchun joy oxirgi paytlarda eng kam foydalaniladigan jumlalarni tashlab yuborish bilan yaratiladi (LRU-almashtirish). Bu hesh-jadval ko‘rinishida tashkil etilgan o‘z-o‘zini tartibga soladigan jumlalar ro‘yhatining qo‘llab quvvatlanishi bilan samarali ravishda amalga oshiriladi. Ro‘yhat shunday loyihalashtirilganki, bunda jumla ko‘rsatkichli operatsiyalarning uncha katta bo‘lmagan soni hisobiga almashtirilishi mumkin bo‘ladi. Qo‘shimcha tufayli ushbu algoritm LZSdan sal sekinroqdir, lekin juda yaxshilab o‘ylab chiqilgan jumlalarni tanlash lug‘atda aynan shunday siqish koeffitsientiga xotirani kamroq sarflanishi bilan erishishni ta’minlaydi. Shuningdek, LZT LZSga nisbatan jumlalarning raqamini ancha yaxshiroq bo‘lgan ikkilamchi kodlash fazasiga bo‘lish usuli vositasida ancha samaraliroq qilib kodlaydi (uni shuningdek ba’zi boshqa LZ-usullariga qo‘llasa ham bo‘ladi). Bunda kodlovchi va kodni ochuvchiga qidirish va LRU-ro‘yhatini qo‘llab quvvatlash vazifasiga nisbatan muhim bo‘lmagan uncha katta bo‘lmagan qo‘shimcha harajatlar talab etiladi.
LZMW, LZ78 dan bo‘lgan barcha hosila algoritmlar lug‘at uchun mavjud bo‘lgan jumlaga bitta simvolni qo‘shish yo‘li bilan yangi jumlani yaratadi. Ushbu usul shak-shubxasiz amalga oshirishni oddiylashtirsa ham, o‘ta ixtiyoriydir. LZMW lug‘at yozuvlarini shakllantirish uchun boshqacha yondoshuvdan foydalanadi. Yangi jumla oxirgi ikkita kodlangan jumlalarni konkatenatsiya qilish yordamida yaratiladi. Bu esa jumlalar tez o‘sishidan darak beradi va ularning barcha prefikslari ham lug‘atda joylashavermaydi. Kam foydalaniladigan jumlalar LZTdagi kabi lug‘atning cheklangan hajmida ishning adaptiv rejimini ta’minlash uchun yo‘qotilib boriladi. Umuman olganda, jumlalarni tezkorlik bilan tuzish strategiyasi LZMWda bir vaqtning o‘zida jumlaning bitta simvolga o‘sishiga nisbatan eng yaxshi siqishga erishiladi, lekin samarali amalga oshirish uchun yaxshilab o‘ylab chiqilgan daraxtlar tizimi zarurdir.
LZJ o‘zida uning variantlari qatoridagi yetishmovchilikni to‘ldiruvchi LZ-siqishga yangicha yondoshuvni ifoda etadi. Dastlab taxmin qilinayotgan LZJ lug‘ati uzunligi bo‘yicha ayrim maksimal h qiymati (h 6 atrofida yaxshi ishlaydi) bilan cheklangan matnning ko‘rib chiqilgan qismidagi har bir yagona satrini o‘z ichiga oladi. Lug‘atning har bir jumlasiga 0 dan N-1 gacha bo‘lgan chegaradagi (N 8192 atrofida) qayd etilgan uzunlikdagi tartib raqami biriktiriladi. Har bir satr kodlanishining kafolati uchun lug‘atga ko‘plikdagi joriy simvollar kiritiladi. Lug‘at to‘liq bo‘lganida kirishda bir marta paydo bo‘ladigan satrning yo‘qotilishi bilan qisqartiriladi. LZJ da kodlash va kodning ochilishi matnning kodlangan qismidagi satr ostini saqlash uchun qidiruvning raqamli daraxti strukturasi asosida bajariladi. Daraxtning balandligi h simvollari bilan cheklangan va u N tugunlardan ko‘pini o‘z ichiga ololmaydi. Satr unga muvofiq bo‘lgan tugun tomonidan biriktirilgan yagona raqam bo‘yicha taniladi. Kodni ochish jarayoni aynan shunaqa daraxtni daraxt bo‘ylab yuqoriga harakat qilgan holda, tugun raqamini qaytadan satr ostiga qayta o‘zgartirish usuli bilan qo‘llab-quvvatlashi kerak.
LZFG - Fiallo va Grini tomonidan taklif etilgan bo‘lib, bu LZ-variantlaridan eng samaralisidir. U ortiqcha xotirani talab etmagan holda tez kodlashni va ochishni, yaxshi siqish samaradorligini beradi. U aynan bir xil jumlalarni ikkita har xil ko‘rsatkichlar bilan kodlash imkoniyatida kodlangan matnni raqamli qidiruv daraxti ko‘rinishida saqlash va chiqish fayliga daraxt pozitsiyasini joylashtirgan holda yo‘qotishlarning bartaraf etilishida LZJ ga o‘xshashdir. Kodni ochish jarayoni daraxtlarning bir xil tizimini qo‘llab quvvatlashi kerak, chunki o‘zi hamda kodlovchi uchun aynan o‘sha resurslar talab etiladi. LZFG LZ78 ning texnikasi yordamida LZJ ga nisbatan o‘ta tezkor siqishga erishadi, bunda ko‘rsatkichlar avvalgi ajratilgan jumla doirasidan tashqarida boshlanishi mumkin. Bu har bir kodlanadigan jumla uchun lug‘atga bitta jumla kiritilishini bildiradi. LZ78 dan farq qiluvchi jihatlari ko‘rsatkichlar qanchalik ko‘p simvollardan nusxa ko‘chirilishi kerakligini ko‘rsatuvchi cheklanmagan uzunlikdagi komponentlarni o‘z ichiga oladi. Kodlangan simvollar oynada (LZ77 uslubida) joylashtirilgan hamda oynani tark etuvchi jumlalar raqamli qidiruv daraxtidan olib tashlanadi. Kodlarni samarali ravishda taqdim etish uchun o‘zgaruvchan uzunlikdagi kodlar qo‘llaniladi. Yangi jumlalar simvollar ortidan keluvchi simvollar hisoblagichi yordamida kodlanadi.
Axborotni arxivlashning tavsiflovchi ko‘rsatkichlarga quyidagilar kiradi:
1) Arxivlash koeffitsienti:

bunda n – xabarni uzatish uchun minimal zarur bo‘lgan simvollar soni (amaliy jihatdan bu siqishning etalon algoritmi chiqishidagi simvollar sonidir);
q – ushbu algoritm bilan siqilgan xabardagi simvollar soni. Ikkilamchi kodlashda n axborot manbai entropiyasiga tengdir.
2) Xabarning ortiqcha koeffitsienti. A xabarining ortiqcha koeffitsienti quyidagi formula bilan aniqlanadi:

Download 130,5 Kb.

Do'stlaringiz bilan baham: