LZW ma’lumotlarni siqish algoritmi

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 W lug‘atdagi biror iboraga mos keladigan eng uzun satr topiladi. So‘ng bu iboraning kodi chiqishga uzatiladi, va WK satri, bunda K — kirish xabarida W dan keyin keladigan belgi, lug‘atga yangi ibora sifatida kiritilib, unga kod beriladi (chunki W ochko‘z usulda tanlangan, shuning uchun, WK lug‘atda hali mavjud bo‘lmaydi). Keyingi ibora K belgisidan boshlanadi. Algoritmni rasmiyroq tarzda quyidagi bosqichlar orqali ifodalash mumkin:

  1. Lug‘atni barcha mumkin bo‘lgan bir belgili iboralar bilan to‘ldirish. Kirish iborasi W ga xabarning birinchi belgisini berish.
  2. Agar КОНЕЦ_СООБЩЕНИЯbo‘lsa, unda W uchun kodni chiqarish va algoritmni tugatish.
  3. Kodlanayotgan xabardan navbatdagi K belgisini o‘qish.
  4. Agar WK iborasi lug‘atda allaqachon mavjud bo‘lsa, kirish iborasi W ga WK qiymatini berish va 2-bosqichga o‘tish.
  5. Aks holda, Wkodini chiqarish, WK ni lug‘atga kiritish, kirish iborasi W ga K 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: W ni topish uchun daraxt ildizidan boshlab imkon qadar uzun satrni o‘qish kifoya; yangi WK iborasini qo‘shish uchun topilgan tugunga K 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 (212=4096) 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 WKibora qo‘shilishidan oldin, ammo Wkodi chiqishga yozilganidan keyin oshiriladi. Masalan, ayni paytda algoritm ishlayotganida kod uzunligi p bit bo‘lsin va algoritm W iborasining kodini chiqarib, lug‘atga yangi WK iborasini qo‘shmoqchi bo‘lsin; agar WK kodi 2p ga teng bo‘lsa (yaʼni WK lug‘atni to‘ldirib yuborsa), avval W ning p bitli kodi chiqariladi, shundan keyingina p bir birlikka oshiriladi va keyingi kodlar p+1 bitdan iborat bo‘ladi. LZWning dastlabki amalga oshirilishlari orasida p ni Wkodi chiqarilishidan oldin oshiradiganlari ham bor. Bunda lug‘atga Wqo‘shilishidan avval chiqariladigan WK kodi allaqachon p+1 bitni egallaydi (aslida bunga ehtiyoj yo‘q, chunki W kodi 2pdan 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:

  1. Eng oddiy yo‘l — tuzilgan lug‘atni keyinchalik o‘zgartirmasdan ishlatishda davom etish. Ammo bu ko‘pincha samarasiz yechim bo‘ladi.
  2. 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.
  3. 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 25=32 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 cScScko‘rinishidagi ketma-ketlik kodlanganda yuzaga keladi, bunda c — bitta belgi, S esa satr bo‘lib, cS 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, x=x1x2⋯ — cheksiz satr, u quyidagi alifboda berilgan: Σ. Belgilaymiz: LZW(x1x2⋯xn) — lug‘ati cheklanmagan LZW algoritmida x1x2⋯xn satrni kodlash uchun kerak bo‘ladigan bitlar soni. U holda:

LZW(x1x2⋯xn)≤zlog2z+O(zlog2|Σ|),

bu yerda z — LZW kodlashidagi x1x2⋯xn satrga tegishli iboralar soni. Ziv quyidagini isbotlagan:

lim supn→∞LZW(x1x2⋯xn)nlog2|Σ|≤FS(x),

bu yerda FS(x) — quyida taʼriflanadigan chekli avtomatlar yordamida siqish ko‘rsatkichi. Shunday qilib, LZWning siqish koeffitsiyenti ( LZW(x1x2⋯xn) ning nlog2|Σ| ga — siqilmagan satr egallagan bitlar soniga — nisbati) asimptotik jihatdan FS 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:

limD→∞lim supn→∞LZWD(x1x2⋯xn)nlog2|Σ|≤FS(x),

bu yerda LZWD(x1x2⋯xn) — ko‘pi bilan D ta iborali, har bir iboraning uzunligi ko‘pi bilan log22D 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: FS.

Ko‘rsatkich FS(x) 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 s son uchun 𝒜s bilan barcha deterministik Mili avtomatlari A, to‘plamini belgilaymiz. Bu avtomatlarning s ta holati bor va ular Σ alifbosidagi satrlarni ikkilik ketma-ketliklarga shunday o‘zgartiradiki, avtomat chiqishidan asl satrni tiklash mumkin. Aniqroq aytganda, A avtomatining qirralarida ikkilik satrlar (jumladan, bo‘sh satrlar ham) yozilgan. Shunday qilib, istalgan chekli y satri Σ alifbosida berilgan bo‘lsa, A avtomati maʼlum bir v holatga o‘tadi va ishlash davomida A(y) ikkilik ketma-ketlikni hosil qiladi. Ushbu A(y) ketma-ketlik hamda v holat orqali y satrni bir qiymatli tiklash mumkin (avtomat qirralarida bo‘sh satrlar ham bo‘lishi mumkinligi uchun y satri faqat A(y) ketma-ketlik asosida emas, balki yakuniy v holat asosida ham tiklanadi). Berilgan cheksiz x=x1x2⋯ satr uchun quyidagini aniqlaymiz:

FS(x)=lims→∞lim supn→∞minA∈𝒜s|A(x1x2⋯xn)|nlog2|Σ|,

bu yerda |A(y)| — A(y)dagi bitlar soni. Shunday qilib, FS(x) — chekli avtomatlar yordamida x 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 D ta ibora saqlaydigan, har bir iborasi uzunligi ko‘pi bilan log22D bo‘lgan LZWni bunday modellashtirish mumkin (bunday avtomat hajmi quyidagi kattalikka bog‘liq — D).

Iboralar sonining optimal emasligi

Chekli avtomatlar yordamida siqish ko‘rsatkichi tabiiy mezon bo‘lsa-da, bir qarashda tuyulganidek samarali emas. Masalan, FS ga nisbatan asimptotik optimal deb, berilgan x=x1x2⋯xn satrni o‘zaro turlicha f1f2⋯fk iboralarga ajratadigan (yaʼni fi≠fj bo‘lganda i<j<k) va keyin xni klog2k+O(klog2|Σ|) 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 x=x1x2⋯xn satrni quyidagi iboralarga ajratadi: p1p2⋯pz. Har bir pk ibora yo bitta belgi bo‘ladi, yoki phaga teng; bunda h — kdan kichik son; a esa ph+1 iborasining birinchi belgisi. Ushbu satrni boshqa usulda ham p1p2⋯pz ko‘rinishida ajratish mumkin. Berilgan x satr uchun tabiiy savol tug‘iladi: LZWning ochko‘z algoritmi hosil qilgan ajratish qanchalik yaxshi?

Faraz qilaylik, zo — x satrni quyidagi ko‘rinishda ajratish mumkin bo‘ladigan eng kichik son: p'1p'2⋯p'zo. Bunda har bir p'k satr yo bitta belgi bo‘ladi, yoki p'haga teng; bunda h — kdan kichik son; a esa p'h+1 satrning birinchi belgisi. Serjio De Agostino va Rikkardo Silvestri eng yomon holatda z qiymati zo dan Ω(n1/4) baravar katta bo‘lishi mumkinligini isbotlagan; bu hatto alifbo atigi ikkita belgidan iborat bo‘lsa ham o‘rinli (ular, shuningdek, z≤zo⋅O(n1/4), 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, zo 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 x satrni ochko‘z usulda f1f2⋯fw iboralarga ajratadi. Bunda har bir fh ibora yo bitta belgi, yo f1f2⋯fh−1satrining qism satri bo‘ladi. Huke, Lorey, Re va Charikar hamda boshqalar eng yomon holatda z qiymati Ω((n/log⁡n)1/2) baravar kattaroq bo‘lishi mumkinligini, bunda taqqoslash uchun wolinganini ko‘rsatgan. Boshqa tomondan, z har doim wdan kichik emasligi, bundan ham kuchliroq ravishda, zo har doim wdan kichik emasligi maʼlum. Boshqacha aytganda, LZW va hatto zo 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