Nomi
|
Mualliflari
| |
Farqi
| | | |
LZ77
|
Ziv and Lempel [1977]
|
Ko‗rsatkichlar va belgilar almashlab turiladi.
Ko‗rsatkichlar satr ostini avvalgi N
belgilari orasida adreslaydi.
| |
LZ78
|
Ziv and Lempel [1978]
|
Ko‗rsatkichlar va belgilar almashlab turiladi.
Ko‗rsatkichlar avval ko‗rib chiqilgan satr ostini adreslaydi.
| |
LZR
|
Roden [1981]
|
Ko‗rsatkichlar va belgilar almashlab turiladi.
Ko‗rsatkichlar satr ostini avvalgi barcha belgilar orasida adreslaydi.
| |
LZSS
|
Roden [1981]
|
Ko‗rsatkichlar va belgilar almashlab turiladi.
Ko‗rsatkichlar satr ostini avvalgi barcha belgilar orasida adreslaydi.
| |
LZW
|
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.
| |
LZM W
|
Miller and Wegman [1984]
|
LZTga o‗hshash, lekin jumlalar avvalgi ikkita jumlalarning konkatenatsiyasidan
quriladi.
| |
LZC
|
Thomas [1985]
|
Hulosa faqat ko‗rsatkichlarni o‗z ichiga oladi. Ko‗rsatkichlar avval ko‗rib chiqilgan
satr ostini adreslaydi.
| |
LZJ
|
Jakobsson [1985]
|
Xulosa faqat ko‗rsatkichlarni o‗z ichiga
oladi. Ko‗rsatkichlar satr ostini avvalgi barcha belgilar orasida adreslaydi.
| |
LZB
|
Bell [1987]
|
LZSS ga o‗hshash, lekin ko‗rsatkichlar
uchun turli kodlash qo‗llaniladi.
|
2.6- jadval davomi
|
LZH
|
Brent [1987]
|
LZSS ga o‗xshash, lekin ikkinchi
qadamda ko‗rsatkichlar uchun Xaffman kodlashi qo‗llaniladi.
| |
LZT
|
Tischer [1987]
|
LZC ga o‗xshash, lekin jumlalar LRU-
ro‗yhatga joylashtiriladi.
| |
LZFG
|
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 belgilardan 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 belgilarida 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 belgi esa, satr ostiga mos kelmaydigan oyna. So‗ngra oyna o‗ngga, algoritmning yangi qadamiga tayyor j+1 belgiga suriladi. Belgilangan belgini har bir ko‗rsatkichga bog‗lab qo‗yilishi buferni to‗sib qo‗yuvchi birinchi belgi 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 belgilarning 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 belgilarni 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-belgili matn O(n^2) vaqtda kodlangan bo‗ladi.
LZSS usuli LZ77 va LZR ishining natijasi bo‗lib qat‘iy almashadigan ko‗rsatkich va belgilarni o‗zida ifoda etuvchi triadalar
seriyasi hisoblanadi. Har bir ko‗rsatkich izidan aniq belgining qo‗llanilishi amaliyotda bexuda urinish bo‗lib hisoblanadi, chunki ko‗pincha uni keyingi ko‗rsatkich qismi qilib qo‗yish mumkin.
LZSS ko‗rsatkich va belgilarning 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 belgilardan iborat oyna LZ77 dagi kabi qo‗llaniladi, shuning uchun ko‗rsatkichlar o‗lchami doimiydir. Har qaysi ko‗rsatkich yoki belgi uchun bir biridan ajratish uchun 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 belgilar 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, belgilar oynada 2 ta bo‗lganida o‗lcham 1 bitga teng bo‗ladi, keyin, oynada 4 ta belgi bo‗lganida 2 ta bitgacha o‗sadi va h., bu oyna N belgini 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 belgilar 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.
Lempel – Ziv 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.
Avraham Lempel 1936 yil Polshaning Lvov shahrida tug‗ilgan. Izrail olimi, informatik.
Yo‗qotishsiz siqish algoritmi Lempel – Ziv
– Velch (LZW) tomonidan 1984 yil chop etilgan.
Bu algoritm patenti aslida Zivga tegishli bo‗lganligi sababli ham olimlar sharafiga LZW deb nomalanadi. Bu Lempel – Ziv tomonidan chop etilgan LZ78 algoritmini qayta ishlangan
turidir. Algoritm shunday tuzilganki, uni qisqa vaqtda amalga oshirish mumkin va ishlashga qulay.
Avraham Lempel
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 axborotni kodlashtirish talab qilsin "aaabbabaabaaabab". Ushbu axborotni 2.7-jadvalda ko‗rsatilganidek 7 ta mayda iboralarga (harflar birlashmasi) bo‗lamiz. Axborotdagi har bir harf yoki iboralar (harflar birlashmasi) o‗zidan oldin qaytarilgan iboralar (harflar birlashmasi) va qo‗shuv mavjud bo‗lgan belgi bilan kodlanadi. Masalan oxirgi uchta belgi 4 ("b") iborasi sifatida kodlashtiriladi.
2.7-jadval LZ78 algoritmi yordamida "aaabbabaabaaabab" axborotni kodlashtirish
|
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)
|
Ko‗rsatkichning oldinga siljish uzoqligi cheklanmagan (ya‘ni, oyna yo‗q), shuning uchun kodlash bajarilayotganida jumlalarning to‗planib borishi ko‗payadi. Ularning ixtiyoriy 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 bo‗lib, 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 belgiga 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. Manba ergodik hisoblanadi, agar u tomonidan amalga oshiriladigan istalgan ketma-ketlik uni o‗z uzunligining o‗sishiga nisbatan aniqroq xarakterlasa. 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 belgi o‗lchamiga asoslangan. Uning uzunligi 8 bit bo‗lganligi bois, 2^40 jumlani yaratishda u atigi chiqarishning 20 foizini egallaydi. Agar davomiylikdagi kiritish imkoni bo‗lganida ham biz xotirani siqish optimal bo‗lishidan ancha ilgariroq to‗ldirib bo‗lamiz. 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 Jimanskilar 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.8-jadval).
2.8-jadval
Hisoblash natijalari
|
Qada m
|
Siljuvchi oyna
|
Takror
-langan Ibora
|
Kodlashtirilg an ma‘lumot
| |
Iboralar
|
Bufer
|
f
|
i
|
j
|
s
| | |
1
|
-
|
AVAAD
|
-
|
0
|
-
|
-
|
A
| |
2
|
A
|
VAADD
|
-
|
0
|
-
|
-
|
V
| |
3
|
AV
|
AADDD
|
-
|
0
|
-
|
-
|
A
| |
4
|
AVA
|
ADDDD
|
-
|
0
|
-
|
-
|
A
| |
5
|
AVAA
|
DDDDD
|
-
|
0
|
-
|
-
|
D
| |
6
|
AVAAD
|
DDDDV
|
-
|
0
|
-
|
-
|
D
| |
7
|
AVAADD
|
DDDVA
|
DD
|
1
|
2
|
2
|
-
| |
8
|
AVAADDDD
|
DVAAV
|
-
|
0
|
-
|
-
|
D
| |
9
|
AVAADDDDD
|
VAAVA
|
VAA
|
1
|
3
|
8
|
-
| |
10
|
AVADDDDDVAA
|
VAASSS
|
VAA
|
1
|
3
|
3
|
-
| |
11
|
AVDDDDDVAAVAA
|
SSSSEA
|
-
|
0
|
-
|
|
C
| |
12
|
AVAADDDDDVAAVAAS
|
SSSEAF
|
-
|
0
|
-
|
-
|
C
| |
13
|
AVAADDDDDVAAVAASS
|
SSEAFF
|
CC
|
1
|
2
|
2
|
-
| |
14
|
AVAFDDDDDVAAVAASSSS
|
YeAFFF
|
-
|
0
|
-
|
-
|
Ye
| |
15
|
AVAADDDDDVAAVAASSSS
|
AFFFFD
|
-
|
0
|
-
|
-
|
A
| |
16
|
AVAADDDDDVAAVAASSSS
|
FFFFDA
|
-
|
0
|
-
|
-
|
F
| |
17
|
AVAADDDDVAAVAASSSSE
|
FFFDAA
|
-
|
0
|
-
|
-
|
F
| |
18
|
AVAADDDDVAAVAASSSSE
|
FFDAA
|
FF
|
1
|
2
|
2
|
-
| |
19
|
AVAADDDDVAAVAASSSSE
|
DAAAA
|
-
|
0
|
-
|
-
|
D
| |
20
|
AVAADDDDDVAAVAASSSS
|
AAAA
|
AA
|
1
|
2
|
13
|
-
| |
21
|
AVAADDDDDVAAVAASSSS
|
AA
|
AA
|
1
|
2
|
2
|
-
|
Axborot sifatida quyidagi axborotni olamiz: VAADDDDDBAACCCCEAFFFFDAAAA
f – bayroqcha;
i – takrorlangan iboraning uzunligi;
j - takrorlangan iboraning necha qadam oldin qaytarilganligi; s – ochiq holatda uzatilgan belgi.
|
