Algoritmul Lempel-Ziva-Welch

Algoritmul Lempel -Ziv-Welch ( Lempel -Ziv-Welch , LZW ) este un algoritm universal de comprimare a datelor fără pierderi creat de Abraham Lempel , Jacob Ziv și Terry Welch ). A fost publicat de Welch în 1984 [1] ca o implementare îmbunătățită a algoritmului LZ78 publicat de Lempel și Ziv în 1978 [2] . Algoritmul este conceput pentru a fi destul de ușor de implementat atât în software cât și în hardware [1] .

Acronimul „LZW” se referă la numele inventatorilor algoritmului: Lempel, Ziv și Welch, dar mulți[ cine? ] susțin că, deoarece brevetul aparținea lui Ziv, metoda ar trebui numită algoritmul Ziv-Lempel-Welch .

Descriere

Acest algoritm, atunci când codifică (comprima) un mesaj, creează în mod dinamic un dicționar de fraze: anumitor secvențe de caractere (fraze) li se atribuie grupuri de biți (coduri) de lungime fixă (de exemplu, cei de 12 biți, așa cum se sugerează în articol original de Welch [1] ). Dicționarul este inițializat cu toate frazele de 1 caracter (în cazul caracterelor de 8 biți, acestea sunt 256 de fraze). Pe măsură ce este codificat, algoritmul scanează textul caracter cu caracter de la stânga la dreapta. Când algoritmul citește următorul caracter în această poziție, există un șir W de lungime maximă care se potrivește cu o frază din dicționar. Apoi codul acestei fraze este trimis la ieșire, iar șirul WK, unde K este caracterul care urmează lui W în mesajul de intrare, este introdus în dicționar ca o nouă frază și i se atribuie un anumit cod (deoarece W a fost ales cu lăcomie , WK nu este încă inclus în dicționar). Caracterul K este folosit ca început al frazei următoare. Mai formal, acest algoritm poate fi descris prin următoarea secvență de pași:

Inițializare dicționar cu toate expresiile posibile cu un singur caracter. Inițializarea frazei de intrare W cu primul caracter al mesajului.
Dacă END_MESSAGE, atunci emiteți un cod pentru W și terminați algoritmul.
Citiți următorul caracter K din mesajul codificat.
Dacă expresia WK este deja în dicționar, atunci setați expresia de intrare W la WK și treceți la Pasul 2.
În caz contrar, scoateți codul W, adăugați WK în dicționar, setați fraza de intrare W la valoarea K și mergeți la Pasul 2.

Algoritmul de decodare are nevoie doar de textul codificat ca intrare: dicționarul de fraze corespunzător este ușor de recreat prin imitarea funcționării algoritmului de codificare (dar există nuanțe subtile discutate în exemplul de mai jos).

Implementare

O caracteristică notabilă a algoritmului LZW este ușurința sa de implementare, ceea ce îl face încă foarte popular, în ciuda raportului de compresie adesea mai slab în comparație cu analogii precum LZ77 [3] . De obicei, LZW este implementat folosind un arbore de prefix care conține expresii dintr-un dicționar: pentru a găsi W, trebuie doar să citiți cel mai lung șir posibil de la rădăcina arborelui, apoi pentru a adăuga o nouă frază, WK trebuie adăugat la nodul găsit. al noului fiu prin simbolul K, iar codul frazei W poate acționa ca index al unui nod într-o matrice care conține toate nodurile.

Codificarea frazei

Utilizarea codurilor cu lungime fixă pentru fraze (12 biți în descrierea Welch [1] ) poate afecta negativ eficiența compresiei, deoarece, în primul rând, pentru caracterele codificate inițiale, această abordare va umfla mai degrabă datele, decât comprima (dacă caracterul are 8 biți și, în al doilea rând, dimensiunea totală a dicționarului (2 12 =4096) nu este atât de mare. Prima problemă este rezolvată prin codificarea secvenței de ieșire cu algoritmul Huffman (eventual adaptativ ) sau codificare aritmetică . Pentru a rezolva cea de-a doua, se folosesc alte abordări.

Prima opțiune simplă este aplicarea unui cod universal optim, cum ar fi codul Levenshtein sau codul Elias . În acest caz, teoretic, dicționarul poate crește la infinit.

O altă opțiune mai comună este modificarea dimensiunii maxime posibile a dicționarului pe măsură ce crește numărul de fraze. [4] Inițial, de exemplu, dimensiunea maximă a dicționarului este de 2 9 (2 8 coduri sunt deja ocupate de fraze pentru codificarea caracterelor unice de 8 biți) și 9 biți sunt alocați pentru codul de frază. Când numărul de fraze devine 2 9 , dimensiunea maximă devine 2 10 și sunt alocați 10 biți pentru coduri. Si asa mai departe. Astfel, teoretic, un dicționar poate fi arbitrar de mare. Această metodă este demonstrată în exemplul de mai jos (de obicei, totuși, dimensiunea maximă a dicționarului este limitată; de exemplu, în LZC - o modificare populară a LZW, discutată mai jos - lungimile codului cresc de la 9 la 16 biți.).

În cele mai multe implementări ale acestei din urmă metode, numărul de biți alocați codului frazei este crescut până când se adaugă o nouă frază WK, care depășește dicționarul, dar după ce codul W este scris la ieșire. returnează codul frazei W și se adaugă noua frază WK în dicționar; dacă codul WK este egal cu 2 p (adică WK depășește dicționarul), atunci codul p-bit W este scos mai întâi și numai după aceea p este crescut cu unu, astfel încât codurile ulterioare să ocupe p + 1 biți. Implementările timpurii ale LZW le includ pe cele care incrementează p înainte de a scoate codul W, adică codul W de ieșire înainte ca WK să fie adăugat la dicționar ocupă deja p+1 biți (ceea ce nu este necesar deoarece codul W este mai mic de 2 p ). Acest comportament se numește „schimbare timpurie”. Această confuzie de implementare a determinat Adobe să accepte ambele variante de LZW în PDF (dacă sunt utilizate „modificări timpurii” este indicat printr-un steag special în antetul datelor care sunt comprimate). [5]

Dicţionar overflow

Deoarece codurile din algoritmul LZW au o lungime fixă, dimensiunea dicționarului este limitată (când se utilizează coduri de lungime nefixă, dimensiunea dicționarului este limitată de cantitatea de memorie disponibilă). Apare întrebarea: ce să faci în caz de depășire a dicționarului? Sunt folosite mai multe strategii.

Cea mai evidentă opțiune este să utilizați pur și simplu dicționarul construit fără alte modificări. [1] În mod clar, aceasta este adesea o strategie proastă.
Autorii utilitarului odată popular compress folosesc pur și simplu dicționarul construit atâta timp cât raportul de compresie rămâne acceptabil și apoi îl curăță dacă calitatea compresiei se deteriorează. Această modificare a LZW se numește LZC (Lempel-Ziv-Compress, vezi mai jos). [6]
P. Tischer a sugerat, înainte de a introduce o frază nouă în dicționarul debordant, la următorul pas al algoritmului, să ștergeți din dicționar fraza care nu a fost folosită de cel mai mult timp (LRU, Least Recently Used). Această modificare este uneori numită LZT (Lempel-Ziv-Tischer, vezi mai jos). [7]

Exemplu

Acest exemplu arată algoritmul LZW în acțiune, arătând starea ieșirii și vocabularul în fiecare etapă, atât în timpul codificării, cât și al decodării mesajului. Pentru a simplifica prezentarea, ne vom limita la un alfabet simplu - doar majuscule, fara semne de punctuatie si spatii. Mesajul care trebuie comprimat arată astfel:

SĂ FĂRĂNUT#

Marcatorul # este folosit pentru a marca sfârșitul mesajului. Astfel, există 27 de caractere în alfabetul nostru (26 de litere mari de la A la Z și #). Calculatorul reprezintă acest lucru ca grupuri de biți, pentru a reprezenta fiecare caracter al alfabetului, avem nevoie doar de un grup de 5 biți pe caracter. Pe măsură ce vocabularul crește, dimensiunea grupurilor trebuie să crească pentru a găzdui elemente noi. Grupurile de 5 biți dau 2 5 = 32 de combinații posibile de biți, așa că atunci când al 33-lea cuvânt apare în dicționar, algoritmul ar trebui să treacă la grupuri de 6 biți. Rețineți că, deoarece este folosit grupul tuturor zerourilor 00000, al 33-lea grup are codul 32 . Dicționarul inițial va conține:

# = 00000 A=00001 B=00010 C=00011 . . . Z = 11010

Codificare

Fără a utiliza algoritmul LZW, atunci când transmiteți mesajul așa cum este - 25 de caractere a câte 5 biți fiecare - va fi nevoie de 125 de biți. Comparați acest lucru cu ceea ce se întâmplă când utilizați LZW:

Simbol: Bitcode: Nouă intrare în dicționar: (la iesire) T20 = 10100 O 15 = 01111 27: TO B2 = 0001028: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: SAU <--- începeți să utilizați grupuri de 6 biți de la următorul caracter N14 = 001110 32: RN O 15 = 001111 33: NR T 20 = 010100 34: OT TO 27 = 011011 35: TT BE 29 = 011101 36: TOB SAU 31 = 011111 37: BEO TOB 36 = 100100 38:ORT EO 30 = 011110 39: TOBE RN 32 = 100000 40: EOR OT 34 = 100010 41: RNO # 0 = 000000 42: OT# Lungime totală = 6*5 + 11*6 = 96 de biți.

Astfel, folosind LZW, am redus mesajul cu 29 de biți din 125 - adică aproape 22%. Pe măsură ce mesajul devine mai lung, elementele de vocabular vor reprezenta părți din ce în ce mai lungi ale textului, făcând cuvintele repetate foarte compacte.

Decodare

Acum să ne imaginăm că am primit mesajul codificat arătat mai sus și trebuie să-l decodificăm. În primul rând, trebuie să cunoaștem dicționarul inițial și putem reconstrui intrările ulterioare din dicționar din mers, deoarece sunt pur și simplu o concatenare a intrărilor anterioare.

Date: Ieșire: Intrare nouă: Complet: Parțial: 10100 = 20 T 27: T? 01111 = 15 O 27: LA 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: SAU 32: R? <---- începeți să utilizați grupuri de 6 biți 001110 = 14 N 32: RN 33: N? 001111 = 15 O 33: NU 34: O? 010100 = 20 T 34: OT 35: T? 011011 = 27 LA 35: TT 36: LA? <---- pentru 37, adăugați doar primul element 011101 = 29 BE 36: TOB 37: BE? următorul cuvânt din dicționar 011111 = 31 SAU 37: BEO 38: SAU? 100100 = 36 TOB 38: ORT 39: TOB? 011110 = 30 EO 39: TOBE 40: EO? 100000 = 32 RN 40: EOR 41: RN? 100010 = 34 OT 41: RNO 42: OT? 000000 = 0 #

Singura dificultate ușoară poate apărea dacă noul cuvânt din dicționar este trimis imediat. În exemplul de decodare de mai sus, când decodorul întâlnește primul caracter, T , știe că cuvântul 27 începe cu T, dar unde se termină? Să ilustrăm problema cu următorul exemplu. Decodificăm mesajul ABABA :

Date: Ieșire: Intrare nouă: Complet: Parțial: . . . 011101 = 29 AB 46: (cuvânt) 47: AB? 101111 = 47AB? <--- ce ar trebui să facem în privința asta?

La prima vedere, aceasta este o situație de nerezolvat pentru decodor. Știm dinainte că cuvântul 47 ar trebui să fie ABA , dar de unde știe decodorul despre el? Rețineți că cuvântul 47 este format din cuvântul 29 plus următorul caracter. Astfel, cuvântul 47 se termină cu „caracter care urmează”. Dar din moment ce acest cuvânt este trimis imediat, trebuie să înceapă cu „următorul caracter” și astfel se termină cu același caracter cu care începe, în acest caz A . Acest truc permite decodorului să determine că cuvântul 47 este ABA .

În general, această situație apare atunci când o secvență de forma cScSc este codificată , unde c este un singur caracter și S este un șir, iar cuvântul cS este deja în dicționar.

Evaluarea teoretică a eficienței

Proprietățile teoretice ale vocabularului neconstrâns LZW sunt în general aceleași cu cele ale LZ78, iar analiza celor două metode de compresie este similară. Când luăm în considerare un dicționar nemărginit, este firesc să presupunem că frazele de ieșire sunt codificate cu coduri de lungime variabilă, de exemplu, un cod universal sau un cod fix, a cărui dimensiune crește odată cu dimensiunea maximă a dicționarului (vezi secțiunea de implementare ).

Optimitatea asimptotică

Pentru o evaluare teoretică a eficienței, această metodă de compresie este comparată cu o metrică de referință. Din păcate, metrica ideală de compresie a datelor de referință - complexitatea Kolmogorov - nu este nici măcar aproximativ calculabilă și, prin urmare, orice algoritm de compresie pierde în mod evident în comparație cu acesta. Lempel și Ziv au propus o versiune slăbită a complexității Kolmogorov - compresie prin automate finite [2] . Din motive tehnice, această metrică este definită pentru șiruri infinite. Reparăm un alfabet finit . Lasă un șir infinit peste . Indicați prin numărul de biți din codificarea LZW cu un dicționar nelimitat pentru șir . Prin urmare avem $\Sigma$ $x=x_{1}x_{2}\cdots$ $\Sigma$ $\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$ $x_{1}x_{2}\cdots x_{n)$

\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})\leq z\log _{2}z+O(z\log _{2}|\Sigma |),

unde este numărul de fraze din codificarea LZW pentru . Ziv a arătat [8] că $z$ $x_{1}x_{2}\cdots x_{n)$

\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})}{n\log _{2}| \Sigma |}}\leq \mathrm {FS} (x),

unde este metrica compresiei prin automate finite, definită mai jos [2] . Astfel, raportul de compresie LZW (raportul la - numărul de biți ocupați de șirul necomprimat) este mărginit asimptotic , iar în acest sens LZW este optim. Mai mult, dacă dimensiunea dicționarului este limitată și strategia de overflow este de a elimina frazele cel mai puțin utilizate, LZW este, de asemenea, optim asimptotic în următorul sens: [8] $\mathrm {FS} (x)$ $\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$ $n\log _{2}|\Sigma |$ $\mathrm {FS}$

\lim _{D\to \infty }\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_ {n})}{n\log _{2}|\Sigma |}}\leq \mathrm {FS} (x),

unde denotă numărul de biți din codificarea LZW cu un dicționar care nu conține mai mult de fraze, fiecare frază are o lungime de cel mult , iar atunci când dicționarul depășește, fraza cel mai puțin folosită este aruncată (această opțiune este similară cu LZT; vezi modificările ) ). Rețineți că algoritmii LZ78 și LZ77 au proprietăți similare (inclusiv variante similare, respectiv, cu un dicționar și o fereastră glisantă de dimensiuni limitate) [8] . Să definim acum . $\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_{n})$ $D$ $\log _{2}^{2}D$ $\mathrm {FS}$

Metrica este în multe privințe similară cu complexitatea Kolmogorov, dar în locul mașinilor Turing cu drepturi depline , în definirea sa sunt folosite mașini Turing cu memorie finită, adică automate finite. Pentru un număr dat , notăm prin mulțimea tuturor automatelor Mealy deterministe care au stări și recodifică șiruri peste alfabet în secvențe binare, astfel încât ieșirea automatului să poată restaura șirul original; mai precis, șirurile binare (eventual goale) sunt scrise pe marginile automatului, astfel încât pentru orice șir finit peste alfabet , automatul ajunge într-o anumită stare și în proces produce o secvență binară și poate fi restaurat în mod unic din succesiunea și starea (pentru ca automatul contractant să poată avea șiruri goale pe margini, șirul este restabilit nu numai prin succesiune ci și prin starea finală [9] ). Pentru un șir infinit dat , definiți: [8] $\mathrm {FS} (x)$ $s$ ${\mathcal {A}}_{s}$ $A,$ $s$ $\Sigma$ $A$ $y$ $\Sigma$ $A$ $v$ $A(y)$ $A(y)$ $v$ $y$ $y$ $A(y)$ $v$ $x=x_{1}x_{2}\cdots$

\mathrm {FS} (x)=\lim _{s\to \infty}\limsup \limits _{n\to \infty }\min \limits _{A\in {\mathcal {A)} _{s}}{\frac {|A(x_{1}x_{2}\cdots x_{n})|}{n\log _{2}|\Sigma |}},

unde denotă numărul de biți în . Astfel, reprezintă o estimare pentru cel mai mic raport de compresie posibil care poate fi atins la comprimarea unui șir cu automate finite. Rețineți că, din cauza nemărginirii dicționarului, algoritmul LZW nu poate fi modelat folosind un automat Mealy, spre deosebire de algoritmul LZW cu vocabular limitat, cu cel mult fraze de lungime (mărimea unui astfel de automat Mealy depinde în mod natural de ). $|A(y)|$ $A(y)$ $\mathrm {FS} (x)$ $X$ $D$ $\log _{2}^{2}D$ $D$

Număr neoptimal de fraze

Metrica de compresie prin automate finite, deși naturală, nu este atât de eficientă pe cât ar părea la prima vedere. Deci, optim asimptotic în ceea ce privește este orice algoritm de compresie care împarte șirul dat în fraze diferite (adică când ) și apoi codifică folosind biți [9] . Este clar că un algoritm care îndeplinește criterii atât de slabe nu trebuie să fie eficient în practică. În plus, metrica de compresie a mașinii de stări nu reflectă capacitatea multor metode de compresie de a înlocui bucăți lungi care se repetă în date cu referințe la locația în care a apărut pentru prima dată o astfel de porțiune (mașina de stări pur și simplu nu are suficientă memorie pentru a compara lungi). bucăți). Acest mecanism este adesea motivul pentru eficiența comprimării cantităților mari de date în practică și, după cum se arată mai jos, LZW (și LZ78) funcționează destul de slab la această sarcină în cel mai rău caz, în comparație cu, de exemplu, LZ77. $\mathrm {FS}$ $x=x_{1}x_{2}\cdots x_{n)$ $f_{1}f_{2}\cdots f_{k)$ $f_{i}\neq f_{j)$ $i<j<k$ $X$ $k\log _{2}k+O(k\log _{2}|\Sigma |)$

Algoritmul LZW cu dimensiunea nelimitată a dicționarului descompune șirul final dat în fraze , astfel încât fiecare frază să fie fie un caracter, fie egal cu , unde este un număr mai mic decât și este primul caracter al frazei . Există și alte descompuneri ale formei pentru un șir și se pune firesc întrebarea: cât de bună este descompunerea construită de algoritmul LZW lacom? $x=x_{1}x_{2}\cdots x_{n)$ $p_{1}p_{2}\cdots p_{z)$ $p_{k}$ $p_{h}a$ $h$ $k$ $A$ $p_{h+1}$ $p_{1}p_{2}\cdots p_{z)$ $X$

Să notăm numărul minim astfel încât șirul să poată fi reprezentat ca o descompunere în care fiecare șir este fie un caracter, fie egal cu , unde este un număr mai mic decât și este primul caracter al șirului . Sergio De Agostino și Ricardo Silvestri [10] au demonstrat că în cel mai rău caz poate fi mai mult decât un factor de 1, chiar dacă alfabetul conține doar două caractere (au mai arătat că această estimare este optimă). Cu alte cuvinte, strategia lacomă în acest caz oferă rezultate care sunt foarte departe de a fi optime. O parte din justificarea abordării LZW este că construirea unei descompunere optimă a frazei este o problemă NP-completă , așa cum arată De Agostino și Storer [11] . $z_{o)$ $X$ $p'_{1}p'_{2}\cdots p'_{z_{o)}$ $p'_{k)$ $p'_{h}a$ $h$ $k$ $A$ $p'_{h+1}$ $z$ $z_{o)$ $\Omega (n^{1/4})$ $z\leq z_{o}\cdot O(n^{1/4}),$ $z_{o)$

O altă întrebare firească este cât de bun este LZW în comparație cu LZ77 ? Se știe că LZ77 descompune cu lăcomie un șir în fraze , astfel încât fiecare frază să fie fie un caracter, fie un subșir al șirului . Hooke, Laurie, Re [12] și Charikar și colab. [13] au arătat că în cel mai rău caz poate fi de câteva ori mai mare decât . Pe de altă parte, se știe că întotdeauna nu este mai puțin decât , și chiar mai mult, întotdeauna nu mai puțin decât . [13] Cu alte cuvinte, LZW, și chiar și versiunea „optimală” a LZW care conține fraze, nu poate fi mai bună decât LZ77 (cel puțin semnificativ - rețineți că numărul de fraze este discutat aici, nu modul în care sunt codificate), iar în unele cazuri patologice ar putea fi catastrofal mai rău. $X$ $f_{1}f_{2}\cdots f_{w)$ $f_{h}$ $f_{1}f_{2}\cdots f_{h-1)$ $z$ $\Omega ((n/\log n)^{1/2})$ $w$ $z$ $w$ $z_{o)$ $w$ $z_{o)$

Aplicație

La momentul introducerii sale, algoritmul LZW a oferit un raport de compresie mai bun pentru majoritatea aplicațiilor decât orice altă metodă bine-cunoscută a vremii. A devenit prima metodă de compresie a datelor utilizată pe scară largă pe computere.

Algoritmul (sau mai degrabă modificarea lui, LZC, vezi mai jos) a fost implementat în programul compress , care a devenit mai mult sau mai puțin un utilitar standard pe sistemele Unix în jurul anului 1986. Câteva alte utilitare de arhivare populare folosesc, de asemenea, această metodă sau cei apropiați.

În 1987, algoritmul a devenit parte a standardului formatului de imagine GIF . Poate fi folosit și (opțional) în format TIFF . În plus, algoritmul este utilizat în protocolul de comunicare modem v.42bis și standardul PDF [14] (deși în mod implicit majoritatea textului și a datelor vizuale din PDF sunt comprimate folosind algoritmul Deflate ).

Brevete

Au fost emise o serie de brevete pentru algoritmul LZW și variațiile acestuia, atât în SUA, cât și în alte țări. LZ78 a fost eliberat de brevetul american 4.464.650 de către Sperry Corporation , care mai târziu face parte din Unisys Corporation . Două brevete americane au fost emise pentru LZW: brevetul american 4.814.746 deținut de IBM și brevetul american Welch 4.558.302 (emis la 20 iunie 1983 ) deținut de Sperry Corporation, preluat ulterior de Unisys Corporation. Până acum, toate brevetele au expirat.

GIF-uri și PNG-uri Unisys

La dezvoltarea formatului GIF , CompuServe nu cunoștea existența brevetului american 4.558.302 . În decembrie 1994, când Unisys a luat cunoștință de utilizarea LZW într-un format grafic utilizat pe scară largă, compania și-a făcut public planurile de a colecta redevențe din programele comerciale cu capacitatea de a crea fișiere GIF. La acea vreme, formatul era deja atât de răspândit încât majoritatea companiilor de software nu aveau de ales decât să plătească. Această situație a fost unul dintre motivele dezvoltării formatului grafic PNG (transcriere neoficială: „PNG’s Not GIF” [15] ), care a devenit al treilea cel mai răspândit. pe WWW , dupa GIF si JPEG . La sfârșitul lunii august 1999, Unisys a reziliat licențele fără drepturi de autor pentru LZW pentru software gratuit și necomercial [16] și pentru utilizatorii de programe fără licență, determinând Liga pentru Libertatea de Programare să lanseze o campanie de „ardere toate GIF-urile” [17] și să informeze publicul despre alternativele disponibile. Mulți experți în dreptul brevetelor au subliniat că brevetul nu acoperă dispozitivele care pot doar decomprima datele LZW, dar nu le pot comprima; din acest motiv, popularul utilitar gzip poate citi fișiere .Z, dar nu le scrie.

Pe 20 iunie 2003, brevetul inițial din SUA a expirat, ceea ce înseamnă că Unisys nu mai poate colecta drepturi de autor pentru el. Brevete similare în Europa, Japonia și Canada au expirat în 2004.

Modificări

LZC (1985, Thomas SW, McKie J., Davies S., Turkowski K., Woods JA și Orost JW) [6] este una dintre cele mai cunoscute implementări practice ale LZW, furnizată în utilitarul compress (Lempel- Ziv-Compress). LZC folosește 9 până la 16 biți pentru codurile de frază (numărul de biți crește odată cu dimensiunea dicționarului, vezi secțiunea de implementare ); când dicționarul depășește, LZC pur și simplu continuă să îl folosească fără alte modificări, dar algoritmul monitorizează gradul de compresie a datelor și, când compresia cu dicționarul actual devine inacceptabil de proastă, LZC șterge dicționarul și continuă să funcționeze. LZC comprimă mai rău decât LZW, dar viteza de compresie este mai mare.
LZT (1985, Tischer P.) [7] este o altă variantă cunoscută a LZW. Când dicționarul depășește, LZT continuă, dar de fiecare dată înainte de a introduce o nouă frază în dicționar, acesta elimină fraza care corespunde celei mai lungi foi nefolosite din arborele de prefix care conține toate frazele. În implementarea LZT, toate frunzele sunt plasate într-o listă legată, iar de fiecare dată când frunzele sunt folosite în timpul compresiei, frunzele sunt mutate în capul listei; astfel frunzele care nu au fost folosite cel mai mult timp sunt la coada listei (mai multe detalii sunt evidente).
LZMW (1985, Victor Miller și Mark Wegman ) [18] - găsește în fluxul de intrare cel mai lung șir care este deja în dicționar (să-l notăm W), scoate codul W și apoi îl adaugă la dicționar șirul VW, unde V este șirul din dicționar al cărui cod a fost returnat în pasul anterior (inițial, V este un șir gol). Astfel, șirurile din dicționar cresc mai repede decât în LZW original, iar în practică este adesea posibil să se obțină o calitate mai bună a compresiei. Miller și Wegman au sugerat, de asemenea, că, în caz de lipsă de memorie, frazele care sunt folosite rar ar trebui eliminate din dicționar, așa cum se face în LZT.
LZAP (1988, James Storer) [19] este o modificare a LZMW, care diferă prin aceea că la fiecare pas, nu numai șirul VW este adăugat în dicționar, ci și șirurile VW 1 , VW 2 , …, VW |W |-1 , unde W i este un prefix W de lungime i. („AP” în „LZAP” înseamnă „toate prefixele”, adică „toate prefixele.”) De exemplu, dacă V = wiki și W = pedia - adică în pasul anterior, algoritmul a găsit șirul wiki în dicționarul , iar pe acesta a găsit pedia - atunci algoritmul va adăuga șirul wikipedia la dicționar , așa cum ar face LZMW, dar adaugă și șirurile wikip , wikipe , wikiped , wikipedi . Algoritmul LZAP este mai ușor de implementat decât LZMW, dar în același timp păstrează majoritatea avantajelor LZMW, cu excepția faptului că codurile șirurilor de dicționar ocupă mai mult spațiu deoarece dicționarul este mai umflat.

Vezi și

Note

↑ 1 2 3 4 5 Welch, 1984 .
↑ 1 2 3 Lempel, Ziv, 1978 .
↑ Arnold, Bell, 1997 .
↑ Bell, Witten, Cleary, 1989 , secțiunea 3.4.6.
↑ Specificația PDF 1.7 , secțiunea 7.4.4.3.
↑ 1 2 Bell, Witten, Cleary, 1989 , secțiunea 3.4.8.
↑ 1 2 Bell, Witten, Cleary, 1989 , secțiunea 3.4.9.
↑ 1 2 3 4 Ziv, 2015 .
↑ 12 Sheinwald , 1994 .
↑ De Agostino, Silvestri, 1997 .
↑ De Agostino, Storer, 1996 .
↑ Hucke, Lohrey, Reh, 2016 .
↑ 12 Charikar și colab., 2005 .
↑ Specificația PDF 1.7 , secțiunea 7.4.4.
↑ Web Review: PNG-ul NU este GIF! . Consultat la 18 octombrie 2018. Arhivat din original la 30 martie 2022. (nedefinit)
↑ Fișierele de brevet Unisys LZW și GIF . Consultat la 18 octombrie 2018. Arhivat din original la 19 octombrie 2018. (nedefinit)
↑ Unisys Aplicarea brevetelor GIF - Slashdot . Preluat la 18 octombrie 2018. Arhivat din original la 18 octombrie 2018. (nedefinit)
↑ Miller, Wegman, 1985 .
↑ Storer, 1988 .

Literatură

Arnold R., Bell T. Un corpus pentru evaluarea algoritmilor de compresie fără pierderi // IEEE Data Compression Conference. - 1997. - S. 201-210 . - doi : 10.1109/DCC.1997.582019 .
Bell T. , Witten IH , Cleary JG Modelare pentru compresia textului // ACM Computing Surveys . - 1989. -T. 21,nr 4. —S. 557–591. doi:/76894.76896.
Charikar M., Lehman E., Lehman A., Liu D., Panigrahy R., Prabhakaran M., Sahai A., shelat a. Cea mai mică problemă de gramatică // IEEE Transactions on Information Theory . - 2005. - T. 51 , nr 7 . - S. 2554-2576 . - doi : 10.1109/TIT.2005.850116 .
De Agostino S., Silvestri R. A worst-case analysis of the LZ2 compression algorithm // Information and Computation . - 1997. - T. 139 , nr 2 . — S. 258–268 . - doi : 10.1006/inco.1997.2668 .
De Agostino S., Storer JA Calcul on-line versus off-line în compresia dinamică a textului // Litere de procesare a informațiilor . - 1996. - T. 59 , nr 3 . — S. 169–174 . - doi : 10.1016/0020-0190(96)00068-3 .
Hucke D., Lohrey M., Reh CP Cea mai mică problemă de gramatică revizuită // String Processing and Information Retrieval (SPIRE). - 2016. - T. 9954 . — p. 35–49 . - doi : 10.1007/978-3-319-46049-9_4 .
Lempel A. , Ziv J. Comprimarea secvențelor individuale prin codificare cu rată variabilă // IEEE Transactions on Information Theory . - 1978. - T. 24 , nr 5 . — S. 530–536 . - doi : 10.1109/TIT.1978.1055934 .
Miller V. S , Wegman MN Variațiuni pe o temă de Ziv și Lempel // Algoritmi combinatori pe cuvinte. - 1985. -T. 12. —S. 131–140. -doi:10.1007/978-3-642-82456-2_9.
Sheinwald D. Despre proba Ziv-Lempel și subiecte conexe // Proceedings of the IEEE . - 1994. - T. 82 , nr 6 . — S. 866–871 . - doi : 10.1109/5.286190 .
Comprimarea datelor Storer JA : Metode și teorie. - New York, SUA: Computer Science Press, 1988. - 413 p. - ISBN 0-7167-8156-5 .
Welch TA O tehnică de comprimare a datelor de înaltă performanță // Computer. - 1984. - V. 6 , Nr. 17 . — P. 8–19 . - doi : 10.1109/MC.1984.1659158 .
Ziv J. O versiune de dicționar constrâns a LZ78 realizează asimptotic compresibilitatea în stare finită cu o măsură de distorsiune // IEEE Information Theory Workshop. - 2015. - S. 1–4 . - doi : 10.1109/ITW.2015.7133077 .
Adobe Systems Inc. Gestionarea documentelor - Format document portabil - Partea 1: PDF 1.7 . Specificație PDF 1.7 . Adobe (1 iulie 2008). Data accesului: 26 ianuarie 2018.

Metode de compresie

Teorie

informație	propriu Reciproc Entropie Entropia condiționată Complexitate Redundanţă
Unități	Pic Nat Ciuguli Hartley Formula Hartley

Fara pierderi

Compresie entropică	Sisteme numerice asimetrice Algoritmul Huffman Algoritmul adaptiv Huffman Algoritmul Shannon-Fano algoritmul lui Shannon Codare aritmetică ( Interval ) Codurile Golomb Delta Cod universal Elias Fibonacci
Dicţionar Methods	RLE Dezumfla LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Alte	RLE CTW BWT MTF PPM DMC

Audio

Teorie	Convoluţie PCM Alianta Prelevarea de probe teorema lui Kotelnikov
Metode	LPC LAR LSP WLPC CELP ACELP O lege μ-legea ADPCM MDCT transformata Fourier Model psihoacustic
Alte	Compresor audio Compresia vorbirii Codarea benzii

Imagini

Termeni	spațiu de culoare Pixel Subeșantionarea de saturație Artefacte de compresie
Metode	RLE DPCM fractal wavelet EZW SPIHT LP PrEP PCL
Alte	Rata de biți Imagine de testare standard PSNR Cuantizarea

Video

Termeni	Caracteristicile video Cadru Tipuri de cadre Calitate video
Metode	Compensarea mișcării PrEP Cuantizarea wavelet
Alte	Codec video Teoria distorsiunii ratei CBR ABR VBR

Formate de arhivare
Doar arhivare	ar cpio DAR shar gudron LBR
Doar compresie	bzip2 comprima gzip LZMA LZW lzop rzip S.Q. XZ
Arhivare și compresie	7z ACB AS ARC ALZip ARJ Cabinet cpt dd DGCA dmg GCA kgb LHA LZX PAQ PRS RAR qda stai SQX xar grădină zoologică ZIP
Ambalare și distribuție software	apk deb pachet bijuterie RPM MSI BORCAN RĂZBOI RAR (Java) URECHE