Lempel — Ziv — Velch algoritmi (Lempel–Ziv–Welch, LZW) — bu universal maʼlumotlarni siqish algoritmi bo‘lib, maʼlumot yo‘qotmasdan siqishni amalga oshiradi. Uni Avraam Lempel, Yaakov Ziv va Terri Velch yaratgan. Velch uni 1984-yilda LZ78 algoritmining takomillashtirilgan varianti sifatida eʼlon qilgan. LZ78 algoritmini esa 1978-yilda Lempel va Ziv chop etgan. Algoritm dasturiy va apparat vositalarida nisbatan oson amalga oshiriladigan qilib yaratilgan.
«LZW» qisqartmasi algoritm ixtirochilarining familiyalaridan — Lempel, Ziv va Velchdan olingan, biroq ko‘pchilik[kimlar?] patent Zivga tegishli bo‘lgani uchun bu usul Ziv — Lempel — Velch algoritmi.
Tavsif
Bu algoritm xabarni kodlash (siqish) davomida iboralar lug‘atini dinamik ravishda yaratadi: muayyan belgilar ketma-ketligiga (iboralarga) belgilangan uzunlikdagi bitlar guruhlari (kodlar) mos qo‘yiladi (masalan, Velchning dastlabki maqolasida tavsiya etilgan 12 bitli kodlar). Boshlanishida lug‘at 1 belgidan iborat barcha iboralar bilan to‘ldiriladi (8 bitli belgilar uchun ular 256 ta). Kodlash jarayonida algoritm matnni chapdan o‘ngga, belgi-beligacha ko‘rib chiqadi. Navbatdagi belgini o‘qishda joriy o‘rinda lug‘atdagi biror iboraga mos keladigan eng uzun satr topiladi. So‘ng bu iboraning kodi chiqishga uzatiladi, va satri, bunda — kirish xabarida dan keyin keladigan belgi, lug‘atga yangi ibora sifatida kiritilib, unga kod beriladi (chunki ochko‘z usulda tanlangan, shuning uchun, lug‘atda hali mavjud bo‘lmaydi). Keyingi ibora belgisidan boshlanadi. Algoritmni rasmiyroq tarzda quyidagi bosqichlar orqali ifodalash mumkin:
- Lug‘atni barcha mumkin bo‘lgan bir belgili iboralar bilan to‘ldirish. Kirish iborasi ga xabarning birinchi belgisini berish.
- Agar
КОНЕЦ_СООБЩЕНИЯbo‘lsa, unda uchun kodni chiqarish va algoritmni tugatish. - Kodlanayotgan xabardan navbatdagi belgisini o‘qish.
- Agar iborasi lug‘atda allaqachon mavjud bo‘lsa, kirish iborasi ga WK qiymatini berish va 2-bosqichga o‘tish.
- Aks holda, kodini chiqarish, ni lug‘atga kiritish, kirish iborasi ga qiymatini berish va 2-bosqichga o‘tish.
Dekodlash algoritmiga kirish sifatida faqat kodlangan matn kerak: iboralar lug‘atini kodlash algoritmining ishini takrorlash orqali osongina tiklash mumkin (ammo quyidagi misolda muhokama qilinadigan, bir qarashda sezilmaydigan nozik jihatlar ham bor).
Amalga oshirilishi
LZW algoritmining muhim xususiyati — uni amalga oshirish osonligidir. Shu bois u siqish darajasi ko‘pincha LZ77kabi muqobil algoritmlarnikidan past bo‘lsa ham, hozirgacha juda ommalashgan. Odatda LZW lug‘atdagi iboralarni o‘z ichiga olgan prefiks daraxti yordamida amalga oshiriladi: ni topish uchun daraxt ildizidan boshlab imkon qadar uzun satrni o‘qish kifoya; yangi iborasini qo‘shish uchun topilgan tugunga belgisi bo‘yicha yangi farzand tugun biriktiriladi. W iborasining kodi sifatida esa barcha tugunlar saqlanadigan massivdagi tugun indeksi ishlatilishi mumkin.
Iboralarni kodlash
Iboralar uchun belgilangan uzunlikdagi kodlardan (Velch tavsifida 12 bit) foydalanish siqish samaradorligiga salbiy taʼsir qilishi mumkin. Birinchidan, dastlabki belgilar kodlanganda bu usul maʼlumotni siqish o‘rniga uning hajmini oshirishi mumkin (agar belgi 8 bit egallasa). Ikkinchidan, lug‘atning umumiy hajmi () uncha katta bo‘lmaydi. Birinchi muammo chiqish ketma-ketligini Haffman algoritmi yordamida (ehtimol, moslashuvchan usulda) yoki arifmetik kodlash orqali hal qilinadi. Ikkinchi muammoni yechishda boshqa yondashuvlar qo‘llanadi.
Birinchi sodda usul — qandaydir optimal universal kod dan, masalan, Levenshteyn kodi yoki Elias kodidan foydalanish. Bunda nazariy jihatdan lug‘at cheksiz o‘sishi mumkin.
Yana bir keng tarqalgan usul — iboralar soni oshgani sayin lug‘atning maksimal ruxsat etilgan hajmini o‘zgartirish. Dastlab, masalan, maksimal lug‘at hajmi 29 (28 deb olinadi (bunda kodlar 8 bitli yakka belgilar iboralariga ajratib qo‘yilgan bo‘ladi) va ibora kodiga 9 bit ajratiladi. Iboralar soni 29ga yetganda maksimal hajm 210 ga oshadi, kodlar uchun esa 10 bit ajratiladi. Shu tariqa davom etadi. Demak, nazariy jihatdan lug‘at istalgancha katta bo‘lishi mumkin. Bu usul quyidagi misolda ko‘rsatilgan (ammo odatda lug‘atning maksimal hajmi cheklanadi; masalan, quyida ko‘riladigan LZWning mashhur LZC modifikatsiyasida kod uzunligi 9 bitdan 16 bitgacha oshadi).
Oxirgi usulning aksariyat amalga oshirilishlarida ibora kodiga ajratilgan bitlar soni lug‘atni to‘ldirib yuboradigan yangi ibora qo‘shilishidan oldin, ammo kodi chiqishga yozilganidan keyin oshiriladi. Masalan, ayni paytda algoritm ishlayotganida kod uzunligi bit bo‘lsin va algoritm iborasining kodini chiqarib, lug‘atga yangi iborasini qo‘shmoqchi bo‘lsin; agar kodi ga teng bo‘lsa (yaʼni lug‘atni to‘ldirib yuborsa), avval W ning bitli kodi chiqariladi, shundan keyingina bir birlikka oshiriladi va keyingi kodlar bitdan iborat bo‘ladi. LZWning dastlabki amalga oshirilishlari orasida ni kodi chiqarilishidan oldin oshiradiganlari ham bor. Bunda lug‘atga qo‘shilishidan avval chiqariladigan kodi allaqachon bitni egallaydi (aslida bunga ehtiyoj yo‘q, chunki kodi dan kichik). Bunday holat «erta o‘zgarish» (early change) deyiladi. Amalga oshirishlardagi bu tafovut tufayli Adobe PDF formatida LZWning ikkala turini ham qo‘llab-quvvatlaydi («erta o‘zgarish» ishlatilishi siqilgan maʼlumotlar sarlavhasidagi maxsus bayroqcha bilan belgilanadi).
Lug‘atning to‘lib ketishi
LZW algoritmida kodlarning uzunligi belgilangan bo‘lgani uchun lug‘at hajmi cheklangan (o‘zgaruvchan uzunlikdagi kodlar ishlatilganda ham lug‘at hajmi mavjud xotira bilan cheklanadi). Lug‘at to‘lib ketganda nima qilish kerak? Bir nechta strategiya mavjud:
- Eng oddiy yo‘l — tuzilgan lug‘atni keyinchalik o‘zgartirmasdan ishlatishda davom etish. Ammo bu ko‘pincha samarasiz yechim bo‘ladi.
- Bir paytlar ommabop bo‘lgan compress[ingl.] dasturining mualliflari lug‘atni siqish darajasi maqbul bo‘lguncha ishlatadilar, siqish sifati yomonlashsa esa uni tozalaydilar. LZWning ushbu o‘zgartirilgan turi LZC (Lempel-Ziv-Compress, quyiga qarang) deb ataladi.
- P. Tisher lug‘at to‘lganida yangi iborani kiritishdan oldin eng uzoq vaqt ishlatilmagan iborani o‘chirishni (LRU, Least Recently Used) taklif qilgan. Bunday modifikatsiya baʼzan LZT (Lempel-Ziv-Tischer, quyiga qarang) deb ataladi.
Misol
Ushbu misolda LZW algoritmining ishlashi, xabarni kodlash va dekodlashning har bir bosqichidagi chiqish maʼlumotlari hamda lug‘at holati ko‘rsatiladi. Tushuntirishni osonlashtirish uchun alifboni faqat bosh harflar bilan cheklaymiz: tinish belgilari va bo‘shliqlar bo‘lmaydi. Siqiladigan xabar quyidagicha:
TOBEORNOTTOBEORTOBEORNOT#
Belgi # xabarning tugashini bildiradi. Shunday qilib, alifbomizda 27 ta belgi bor (A dan Z gacha 26 ta bosh harf va # belgisi). Kompyuter ularni bitlar guruhlari bilan ifodalaydi; alifbodagi har bir belgini ifodalash uchun 5 bit yetarli. Lug‘at kattalashgani sayin yangi elementlarni ham kodlash uchun bitlar guruhi uzunligi oshishi kerak. 5 bitli guruhlar ta bit kombinatsiyasini beradi. Shu sabab lug‘atda 33-so‘z paydo bo‘lganda algoritm 6 bitli guruhlarga o‘tishi kerak. Eʼtibor bering, barcha bitlari nol bo‘lgan 00000guruh ishlatilgani uchun 33-guruhning kodi 32bo‘ladi. Boshlang‘ich lug‘at quyidagilarni o‘z ichiga oladi:
# = 00000 A = 00001 B = 00010 C = 00011 . . . Z = 11010
Kodlash
LZW algoritmisiz xabarni o‘z holicha uzatish — 25 ta belgi, har biri 5 bitdan — jami 125 bit talab etadi. Buni LZW yordamida olingan natija bilan solishtiramiz:
Символ: Битовый код: Новая запись словаря:
(на выходе)
T 20 = 10100
O 15 = 01111 27: TO
B 2 = 00010 28: OB
E 5 = 00101 29: BE
O 15 = 01111 30: EO
R 18 = 10010 31: OR <--- со следующего символа начинаем использовать 6-битные группы
N 14 = 01110 32: RN
O 15 = 01111 33: NO
T 20 = 10100 34: OT
TO 27 = 11011 35: TT
BE 29 = 11101 36: TOB
OR 31 = 11111 37: BEO
TOB 36 = 100100 38: ORT
EO 30 = 11110 39: TOBE
RN 32 = 100000 40: EOR
OT 34 = 100010 41: RNO
# 0 = 00000 42: OT#
Общая длина = 13*5 + 3*6 = 83 бит.
Shunday qilib, LZW yordamida 29 bitni 125 bitdan qisqartirdik — bu qariyb 22 % ga qisqartirdik. Xabar uzunroq bo‘lsa, lug‘at elementlari matnning tobora uzunroq bo‘laklarini ifodalaydi va takrorlanuvchi so‘zlar juda ixcham kodlanadi.
Dekodlash
Endi yuqoridagi kodlangan xabarni qabul qilganimizni va uni dekodlashimiz kerakligini tasavvur qilaylik. Avvalo boshlang‘ich lug‘atni bilishimiz zarur. Lug‘atning keyingi yozuvlari esa oldingi yozuvlarni ketma-ket birlashtirish orqali jarayon davomida qayta tiklanadi.
Данные: На выходе: Новая запись:
Полная: Частичная:
10100 = 20 T 27: T?
01111 = 15 O 27: TO 28: O?
00010 = 2 B 28: OB 29: B?
00101 = 5 E 29: BE 30: E?
01111 = 15 O 30: EO 31: O?
10010 = 18 R 31: OR 32: R? <---- начинаем использовать 6-битные группы
01110 = 14 N 32: RN 33: N?
01111 = 15 O 33: NO 34: O?
10100 = 20 T 34: OT 35: T?
11011 = 27 TO 35: TT 36: TO? <---- для 37, добавляем только первый элемент
11101 = 29 BE 36: TOB 37: BE? следующего слова словаря
11111 = 31 OR 37: BEO 38: OR?
100100 = 36 TOB 38: ORT 39: TOB?
11110 = 30 EO 39: TOBE 40: EO?
100000 = 32 RN 40: EOR 41: RN?
100010 = 34 OT 41: RNO 42: OT?
00000 = 0 #
Yagona kichik qiyinchilik lug‘atdagi yangi so‘z darhol uzatilganda yuzaga kelishi mumkin. Yuqoridagi dekodlash misolida dekoder birinchi Tbelgini uchratganida 27-so‘z T bilan boshlanishini biladi, ammo u qaysi belgi bilan tugaydi? Muammoni quyidagi misol orqali ko‘rsatamiz. Biz ABABA:
Данные: На выходе: Новая запись:
Полная: Частичная:
.
.
.
011101 = 29 AB 46: (word) 47: AB?
101111 = 47 AB? <--- что нам с этим делать?
xabarini dekodlayapmiz. Bir qarashda bu dekoder uchun yechimsiz vaziyat. Biz 47-so‘z ABAbo‘lishi kerakligini oldindan bilamiz, ammo dekoder buni qanday aniqlaydi? 47-so‘z 29-so‘z va undan keyingi belgidan tashkil topganiga eʼtibor bering. Demak, 47-so‘z «keyingi belgi» bilan tugaydi. Lekin bu so‘z darhol uzatilgani uchun u ham «keyingi belgi» bilan boshlanishi lozim. Shunday qilib, u boshlangan belgi bilan tugaydi; mazkur holatda bu Abelgisidir. Shu usul yordamida dekoder 47-so‘z ABA.
ekanini aniqlaydi. Umuman, bunday vaziyat ko‘rinishidagi ketma-ketlik kodlanganda yuzaga keladi, bunda — bitta belgi, esa satr bo‘lib, so‘zi lug‘atda allaqachon mavjud.
Samaradorlikning nazariy bahosi
Cheklanmagan lug‘atga ega LZWning nazariy xususiyatlari, umuman olganda, LZ78nikiga o‘xshaydi va bu ikkala siqish usulining tahlili ham o‘xshash. Cheklanmagan lug‘atni qaraganda chiqish iboralari o‘zgaruvchan uzunlikdagi kodlar bilan, masalan, qandaydir universal kod yoki lug‘atning maksimal hajmi ortishi bilan uzunligi oshib boradigan belgilangan uzunlikdagi kod bilan kodlanadi, deb taxmin qilish tabiiy (bu haqda amalga oshirish).
bo‘limiga qarang).
Asimptotik optimallik Ushbu siqish usulining nazariy samaradorligi maʼlum etalon ko‘rsatkich bilan taqqoslanadi. Afsuski, maʼlumotlarni siqishning ideal etalon ko‘rsatkichi — Kolmogorov murakkabligi — hatto taxminan ham hisoblab bo‘lmaydi. Shu sabab har qanday siqish algoritmi unga nisbatan taqqoslanganda muqarrar ravishda past natija beradi. Lempel va Ziv Kolmogorov murakkabligining yumshatilgan varianti sifatida chekli avtomatlar yordamida siqish usulini taklif qilishgan. Texnik sabablarga ko‘ra bu ko‘rsatkich cheksiz satrlar uchun aniqlanadi. Chekli alifbo sifatida ni belgilaymiz. Faraz qilaylik, — cheksiz satr, u quyidagi alifboda berilgan: . Belgilaymiz: — lug‘ati cheklanmagan LZW algoritmida satrni kodlash uchun kerak bo‘ladigan bitlar soni. U holda:
bu yerda — LZW kodlashidagi satrga tegishli iboralar soni. Ziv quyidagini isbotlagan:
bu yerda — quyida taʼriflanadigan chekli avtomatlar yordamida siqish ko‘rsatkichi. Shunday qilib, LZWning siqish koeffitsiyenti ( ning ga — siqilmagan satr egallagan bitlar soniga — nisbati) asimptotik jihatdan bilan chegaralanadi va shu maʼnoda LZW optimaldir. Bundan tashqari, lug‘at hajmi cheklansa va to‘lib ketganda eng kam ishlatilgan iboralar o‘chirilsa, LZW quyidagi maʼnoda ham asimptotik optimal bo‘ladi:
bu yerda — ko‘pi bilan ta iborali, har bir iboraning uzunligi ko‘pi bilan bo‘lgan va lug‘at to‘lganda eng kam ishlatilgan ibora chiqarib tashlanadigan LZW kodlashining bitlar soni (bu variant LZTga o‘xshaydi; modifikatsiyalar bo‘limiga qarang). LZ78 va LZ77 algoritmlari ham (mos ravishda, cheklangan lug‘at va cheklangan sirpanuvchi oynali variantlari bilan) shunday xususiyatlarga ega. Endi quyidagi ko‘rsatkichni aniqlaymiz: .
Ko‘rsatkich ko‘p jihatdan Kolmogorov murakkabligiga o‘xshaydi, biroq uning taʼrifida to‘liq Tyuring mashinalari o‘rniga xotirasi cheklangan Tyuring mashinalari, yaʼni chekli avtomatlar qo‘llanadi. Berilgan son uchun bilan barcha deterministik Mili avtomatlari to‘plamini belgilaymiz. Bu avtomatlarning ta holati bor va ular alifbosidagi satrlarni ikkilik ketma-ketliklarga shunday o‘zgartiradiki, avtomat chiqishidan asl satrni tiklash mumkin. Aniqroq aytganda, avtomatining qirralarida ikkilik satrlar (jumladan, bo‘sh satrlar ham) yozilgan. Shunday qilib, istalgan chekli satri alifbosida berilgan bo‘lsa, avtomati maʼlum bir holatga o‘tadi va ishlash davomida ikkilik ketma-ketlikni hosil qiladi. Ushbu ketma-ketlik hamda holat orqali satrni bir qiymatli tiklash mumkin (avtomat qirralarida bo‘sh satrlar ham bo‘lishi mumkinligi uchun satri faqat ketma-ketlik asosida emas, balki yakuniy holat asosida ham tiklanadi). Berilgan cheksiz satr uchun quyidagini aniqlaymiz:
bu yerda — dagi bitlar soni. Shunday qilib, — chekli avtomatlar yordamida satrni siqishda erishish mumkin bo‘lgan eng kichik siqish koeffitsiyentining bahosidir. Cheklanmagan lug‘atli LZWni Mili avtomati bilan modellashtirib bo‘lmaydi, biroq cheklangan lug‘atida ko‘pi bilan ta ibora saqlaydigan, har bir iborasi uzunligi ko‘pi bilan bo‘lgan LZWni bunday modellashtirish mumkin (bunday avtomat hajmi quyidagi kattalikka bog‘liq — ).
Iboralar sonining optimal emasligi
Chekli avtomatlar yordamida siqish ko‘rsatkichi tabiiy mezon bo‘lsa-da, bir qarashda tuyulganidek samarali emas. Masalan, ga nisbatan asimptotik optimal deb, berilgan satrni o‘zaro turlicha iboralarga ajratadigan (yaʼni bo‘lganda ) va keyin ni bit yordamida kodlaydigan istalgan siqish algoritmini hisoblash mumkin. Shubhasiz, bunday kuchsiz mezonlarga javob beruvchi algoritm amalda samarali bo‘lishi shart emas. Bundan tashqari, chekli avtomatlar bilan siqish ko‘rsatkichi ko‘plab siqish usullarining maʼlumotlardagi uzun takrorlanuvchi bo‘laklarni ular birinchi uchragan joyga havolalar bilan almashtirish qobiliyatini hisobga olmaydi (chekli avtomatning xotirasi uzun bo‘laklarni taqqoslash uchun yetmaydi). Amaliyotda katta hajmdagi maʼlumotlar yaxshi siqilishiga ko‘pincha aynan shu mexanizm sabab bo‘ladi. Quyida ko‘rsatilganidek, eng yomon holatda LZW (va LZ78) bu vazifani, masalan, LZ77ga nisbatan ancha yomon bajaradi.
Lug‘at hajmi cheklanmagan LZW algoritmi berilgan chekli satrni quyidagi iboralarga ajratadi: . Har bir ibora yo bitta belgi bo‘ladi, yoki ga teng; bunda — dan kichik son; esa iborasining birinchi belgisi. Ushbu satrni boshqa usulda ham ko‘rinishida ajratish mumkin. Berilgan satr uchun tabiiy savol tug‘iladi: LZWning ochko‘z algoritmi hosil qilgan ajratish qanchalik yaxshi?
Faraz qilaylik, — satrni quyidagi ko‘rinishda ajratish mumkin bo‘ladigan eng kichik son: . Bunda har bir satr yo bitta belgi bo‘ladi, yoki ga teng; bunda — dan kichik son; esa satrning birinchi belgisi. Serjio De Agostino va Rikkardo Silvestri eng yomon holatda qiymati dan baravar katta bo‘lishi mumkinligini isbotlagan; bu hatto alifbo atigi ikkita belgidan iborat bo‘lsa ham o‘rinli (ular, shuningdek, ekanini, yaʼni bu baho optimal ekanini ko‘rsatgan). Boshqacha aytganda, bu holatda ochko‘z strategiya optimal natijadan juda uzoq bo‘lishi mumkin. LZW yondashuvini qisman oqlaydigan jihat shuki, ta iboradan iborat optimal ajratishni topish NP-to‘liq masala ekanini De Agostino va Storer tomonidan isbotlangan.
Yana bir tabiiy savol: LZW algoritmini LZ77 bilan taqqoslasak, natija qanday bo‘ladi? Maʼlumki, LZ77 satrni ochko‘z usulda iboralarga ajratadi. Bunda har bir ibora yo bitta belgi, yo satrining qism satri bo‘ladi. Huke, Lorey, Re va Charikar hamda boshqalar eng yomon holatda qiymati baravar kattaroq bo‘lishi mumkinligini, bunda taqqoslash uchun olinganini ko‘rsatgan. Boshqa tomondan, har doim dan kichik emasligi, bundan ham kuchliroq ravishda, har doim dan kichik emasligi maʼlum. Boshqacha aytganda, LZW va hatto ta iborani o‘z ichiga oladigan «optimal» LZW versiyasi LZ77dan yaxshiroq bo‘la olmaydi (hech bo‘lmaganda sezilarli darajada; bu yerda iboralar soni muhokama qilinmoqda, ularni kodlash usuli emas), ayrim g‘ayrioddiy holatlarda esa keskin yomon natija ko‘rsatishi mumkin.
Qo‘llanilishi
Yaratilgan davrida LZW algoritmi aksariyat ilovalar uchun o‘sha paytda maʼlum boshqa usullarga qaraganda yaxshiroq siqish koeffitsiyentini taʼminlagan. U kompyuterlarda keng qo‘llanilgan dastlabki maʼlumotlarni siqish usuliga aylandi.
Algoritm (aniqrog‘i, uning LZC modifikatsiyasi, quyiga qarang) compress[ingl.] dasturida amalga oshirildi. Bu dastur taxminan 1986-yilga kelib Unix tizimlari uchun deyarli standart yordamchi dasturga aylandi. Yana bir qancha ommabop arxivatorlar ham shu yoki unga yaqin usullardan foydalanadi.
Aynan 1987-yilda algoritm GIF tasvir formati standartining bir qismiga aylandi. Undan ixtiyoriy ravishda TIFF formatida ham foydalanish mumkin. Bundan tashqari, algoritm v.42bis modem aloqa protokoli va PDF formatida ham ishlatiladi (PDFdagi matn va tasvirlarning aksariyati esa odatda boshqa algoritm bilan siqiladi — Deflate).
Patentlar
LZW algoritmi va uning turli variantlariga AQSHda ham, boshqa mamlakatlarda ham qator patentlar berilgan. LZ78 uchun AQSH patenti 4 464 650 berilgan; u Sperry Corporation kompaniyasiga tegishli bo‘lib, kompaniya keyinchalik Unisys Corporation tarkibiga kirgan. AQSHda LZW uchun ikkita patent berilgan: AQSH patenti 4 814 746 — IBMga tegishli; va Velchning AQSH patenti 4 558 302 ( 20-iyun 1983-yilda berilgan) — dastlab Sperry Corporationga tegishli, keyinchalik Unisys Corporationga o‘tgan. Hozirga kelib barcha patentlarning amal qilish muddati tugagan.
Unisys, GIF va PNG
CompuServeda GIF formati ishlab chiqilayotganida AQSH patenti 4 558 302 mavjudligidan xabardor bo‘lishmagan. 1994-yil dekabrida Unisys kompaniyasi LZWning keng tarqalgan grafik formatida ishlatilayotganini bilib, GIF fayllarini yaratish imkonini beruvchi tijorat dasturlaridan litsenziya to‘lovlari undirish rejasi haqida eʼlon qildi. O‘sha vaqtda format shunchalik keng tarqalgandiki, aksariyat dasturiy taʼminot ishlab chiqaruvchilarining to‘lovni amalga oshirishdan boshqa chorasi qolmagan edi. Bu holat PNG grafik formatini yaratish sabablaridan biriga aylandi (uning norasmiy ochilishi: «PNG’s Not GIF» — «PNG GIF emas»). 1999-yil avgust oyi oxirida Unisys bepul va notijorat dasturiy taʼminot hamda litsenziyasiz dastur foydalanuvchilari uchun LZWdan tekin foydalanish litsenziyalarini bekor qildi. Bu esa League for Programming Freedom tashkilotini «barcha GIFlarni yoqib yuboramiz» kampaniyasini boshlashga va jamoatchilikka mavjud muqobil formatlar haqida maʼlumot berishga undadi. Patent huquqi sohasidagi ko‘plab mutaxassislar patent faqat LZW maʼlumotlarini ochadigan, ammo siqmaydigan qurilmalarga tatbiq etilmasligini taʼkidlashgan. Shu sabab mashhur gzip yordamchi dasturi .Z fayllarini o‘qishi, ammo yozolmasligi mumkin.
20-iyun 2003-yilda AQSHdagi dastlabki patentning amal qilish muddati tugadi. Shundan so‘ng Unisys u bo‘yicha litsenziya to‘lovlarini undira olmaydigan bo‘ldi. Yevropa, Yaponiya va Kanadadagi o‘xshash patentlarning muddati 2004-yilda tugagan.
Modifikatsiyalar
- LZC (1985, Thomas S. W., McKie J., Davies S., Turkowski K., Woods J. A. va Orost J. W.) — LZWning amalda eng mashhur qo‘llanilishlaridan biri bo‘lib, compress[ingl.] (Lempel-Ziv-Compress) dasturida taqdim etilgan. LZC ibora kodlari uchun 9 dan 16 bitgacha foydalanadi (lug‘at kattalashgan sari bitlar soni ham ortadi; amalga oshirilishibo‘limiga qarang). Lug‘at to‘lganda LZC uni o‘zgartirmasdan ishlatishda davom etadi, shu bilan birga maʼlumotlarning siqilish darajasini kuzatadi. Agar joriy lug‘at bilan siqish darajasi nomaqbul darajada yomonlashsa, LZC lug‘atni tozalab, ishni davom ettiradi. LZC LZWga qaraganda zaifroq siqadi, ammo siqish tezligi yuqoriroq.
- LZT (1985, P. Tisher) — LZWning yana bir mashhur variantidir. Lug‘at to‘lib ketganda LZT ishni davom ettiradi, biroq har safar yangi ibora qo‘shishdan oldin prefiks daraxtidagi eng uzoq vaqt ishlatilmagan bargga mos iborani o‘chiradi. Ushbu daraxt barcha iboralarni o‘z ichiga oladi. LZT amalga oshirilishida barcha barglar bog‘langan ro‘yxatga joylanadi; siqish jarayonida barg ishlatilgan sari ro‘yxat boshiga ko‘chiriladi. Shunday qilib, eng uzoq vaqtdan beri ishlatilmagan barglar ro‘yxat oxirida joylashadi (qolgan tafsilotlar tushunarli).
- LZMW (1985, Viktor Miller va Mark Vegman[ingl.]) — kirish oqimidan lug‘atda avvaldan mavjud eng uzun satrni (uni W deb belgilaymiz) topadi, W kodini chiqishga uzatadi va so‘ng lug‘atga VW satrini qo‘shadi. Bu yerda V — oldingi bosqichda kodi chiqarilgan lug‘at satri (dastlab V bo‘sh satr). Shunday qilib, lug‘atdagi satrlar dastlabki LZWga qaraganda tezroq uzayadi va amalda ko‘pincha yaxshiroq siqish sifatiga erishiladi. Miller va Vegman, shuningdek, xotira yetishmaganda lug‘atdan LZTdagi kabi kam ishlatiladigan iboralarni olib tashlashni taklif qilishgan.
- LZAP (1988, Jeyms Storer) — LZMWning bir modifikatsiyasi. Farqi shundaki, har bir bosqichda lug‘atga faqat VW satri emas, balki VW1, VW2, …, VW|W|-1ham qo‘shiladi, bunda Wi — W ning uzunligi i bo‘lgan prefiksi («LZAP»dagi «AP» «all prefixes», yaʼni «barcha prefikslar» degani). Masalan, V = wiki va W = pedia bo‘lsin. Yaʼni algoritm oldingi bosqichda lug‘atdan wikisatrini, hozirgi bosqichda esa pedia satrini topgan. U holda algoritm lug‘atga LZMW kabi wikipediasatrini qo‘shadi, bundan tashqari wikip, wikipe, wikiped, wikipedisatrlarini ham qo‘shadi. LZAPni amalga oshirish LZMWga qaraganda osonroq, lekin u LZMWning aksariyat afzalliklarini saqlaydi. Faqat lug‘at ko‘proq shishgani uchun lug‘at satrlari kodlari ko‘proq joy egallaydi.
Adabiyotlar
- Arnold R., Bell T.[ingl.]. Maʼlumot yo‘qotmasdan siqish algoritmlarini baholash uchun matnlar to‘plami (A corpus for the evaluation of lossless compression algorithms) // IEEE Maʼlumotlarni siqish konferensiyasi (IEEE Data Compression Conference). — 1997. — 201–210-betlar. — doi:10.1109/DCC.1997.582019.
- Bell T.[ingl.], Witten I. H.[ingl.], Cleary J. G. Matnni siqish uchun modellashtirish (Modeling for text compression) // ACM Computing Surveys[ingl.]. — 1989. — 21-jild, № 4. — 557–591-betlar. — doi:10.1145/76894.76896.
- Charikar M., Lehman E., Lehman A., Liu D., Panigrahy R., Prabhakaran M., Sahai A., shelat a. Eng kichik grammatika muammosi (The smallest grammar problem) // IEEE Transactions on Information Theory[ingl.]. — 2005. — 51-jild, № 7. — 2554—2576-betlar. — doi:10.1109/TIT.2005.850116.
- De Agostino S., Silvestri R. LZ2 siqish algoritmining eng yomon holatdagi tahlili (A worst-case analysis of the LZ2 compression algorithm) // Information and Computation[ingl.]. — 1997. — 139-jild, № 2. — 258–268-betlar. — doi:10.1006/inco.1997.2668.
- De Agostino S., Storer J. A. Dinamik matn siqishda onlayn va oflayn hisoblash (On-line versus off-line computation in dynamic text compression) // Information Processing Letters[ingl.]. — 1996. — 59-jild, № 3. — 169–174-betlar. — doi:10.1016/0020-0190(96)00068-3.
- Hucke D., Lohrey M., Reh C. P. Eng kichik grammatika muammosiga qayta nazar (The smallest grammar problem revisited) // Satrlarni qayta ishlash va axborot izlash (String Processing and Information Retrieval, SPIRE). — 2016. — 9954-jild. — 35–49-betlar. — doi:10.1007/978-3-319-46049-9_4.
- Lempel A., Ziv J. O‘zgaruvchan tezlikdagi kodlash orqali alohida ketma-ketliklarni siqish (Compression of individual sequences via variable-rate coding) // IEEE Transactions on Information Theory[ingl.]. — 1978. — 24-jild, № 5. — 530–536-betlar. — doi:10.1109/TIT.1978.1055934.
- Miller V. S., Wegman M. N.[ingl.]. Ziv va Lempel mavzusidagi variantlar (Variations on a theme by Ziv and Lempel) // So‘zlar ustidagi kombinator algoritmlar (Combinatorial algorithms on words). — 1985. — 12-jild. — 131–140-betlar. — doi:10.1007/978-3-642-82456-2_9.
- Sheinwald D. Ziv–Lempel isboti va unga oid masalalar haqida (On the Ziv-Lempel proof and related topics) // Proceedings of the IEEE[ingl.]. — 1994. — 82-jild, № 6. — 866–871-betlar. — doi:10.1109/5.286190.
- Storer J. A. Maʼlumotlarni siqish: usullar va nazariya (Data Compression: Methods and Theory). — Nyu-York, AQSH: Computer Science Press, 1988. — 413 bet — ISBN 0-7167-8156-5.
- Velch T. A. Yuqori unumli maʼlumotlarni siqish usuli (A technique for high-performance data compression) // Computer. — 1984. — 6-jild, № 17. — 8–19-betlar. — doi:10.1109/MC.1984.1659158.
- Ziv J. LZ78ning lug‘ati cheklangan varianti buzilish o‘lchovi sharoitida chekli holatli siqiluvchanlikka asimptotik ravishda erishadi (A constrained-dictionary version of LZ78 asymptotically achieves the finite-state compressibility with a distortion measure) // IEEE Axborot nazariyasi seminari (IEEE Information Theory Workshop). — 2015. — 1–4-betlar. — doi:10.1109/ITW.2015.7133077.
- Adobe Systems Incorporated. Hujjatlarni boshqarish — Ko‘chma hujjat formati — 1-qism: PDF 1.7 (ingl.). PDF 1.7 spetsifikatsiyasi. Adobe (1-iyul, 2008-yil). Murojaat qilingan sana: 26-yanvar, 2018-yil.