Lempel-Ziv-Welch

LZW
Dezvoltat de	Abraham Lempel , Jacob Ziv , Terry Welch
Tip	Comprimarea datelor
Comprimare	Fara pierderi

Lempel-Ziv-Welch (prescurtat LZW ) un algoritm utilizat în informatică pentru compresia datelor fără pierderi . De exemplu, acest algoritm este utilizat în codificarea imaginilor în format GIF și opțional în fișiere TIFF .

Istorie

Introdus ^[1] de Terry Welch în 1984, algoritmul se bazează pe cercetările anterioare efectuate de Jacob Ziv și Abraham Lempel .

De fapt, acesta din urmă a publicat în 1977 o lucrare privind compresia „fereastră glisantă”, urmată în 1978 de o altă cercetare privind compresia bazată pe „dicționar”.

Cei doi algoritmi au fost numite LZ77 și LZ78 respectiv. În 1984, Terry Welch a îmbunătățit LZ78 dând naștere algoritmului cunoscut astăzi sub numele de LZW, acronim pentru Lempel-Ziv-Welch.

Descriere

Unele avantaje ale compresiei LZW sunt:

Ușurința de implementare
Aplicabilitate pentru orice tip de date: text, imagini, sunete etc.

Factorul de compresie nu este adesea foarte mare, tocmai datorită naturii generice a algoritmului care nu profită de particularitățile datelor care trebuie comprimate.

Premise

ADN-ul poate fi văzut ca o secvență de A, C, G și T

Intrarea algoritmului de compresie ( codificator ) și decompresie ( decodor ) constă dintr-o secvență finită de simboluri ( șir ) care aparțin unui set numit alfabet.
De exemplu, imaginați-vă că doriți să arhivați o secvență ADN .
În general, o porțiune de ADN este compusă dintr-o secvență (finită) a 4 baze azotate: A Denina , T imina , C itosina și G uanina .
Alfabetul pe care este construită o secvență ADN este setul:

\sum =\{A,C,G,T\}

{\ displaystyle \ sum = \ {A, C, G, T \}}

{\ displaystyle \ sum = \ {A, C, G, T \}}

Un șir pe alfabet $\sum$ ${\ displaystyle \ sum}$ $\ sum$ este alcătuit din orice secvență finită de A, C, G și T, de exemplu:

„ACGTACGTACG”

În realitate, nu toate șirurile astfel construite sunt valabile, de fapt există câteva „reguli” pentru combinarea bazelor, ignorate aici pentru a simplifica discuția .

Cantitatea de memorie necesară pentru a stoca un șir este proporțională cu numărul de simboluri din care este alcătuită.
Comprimarea unui șir înseamnă exprimarea acelorași informații folosind mai puține simboluri.

Structura

Foarte des șirul de intrare conține unele părți ( șiruri secundare ), care se repetă de mai multe ori în cadrul aceluiași.
De exemplu, examinând șirul anterior, putem evidenția următoarele repetări:

AC GT AC GT AC G

Nu există o singură modalitate de a alege sub-șiruri repetate.

Ideea centrală a algoritmului LZW este de a exploata prezența acestor repetări pentru comprimare. Algoritmul are performanțe diferite în funcție de datele de intrare și, în general, este mai potrivit în comprimarea fișierelor textuale. Pe măsură ce șirul de intrare este examinat, șirurile secundare care se repetă sunt determinate automat și inserate într-un dicționar . Un nou simbol care nu aparține alfabetului inițial va fi asociat cu fiecare șir. Acesta din urmă este apoi extins cu simboluri speciale, fiecare dintre ele reprezentând un anumit sub șir.

În exemplul anterior este posibil să identificăm două secvențe repetate:

B.C
GT

Aceste două șiruri de caractere vor fi „detectate” de algoritmul care le va insera în dicționar și le va asocia două simboluri noi:

Dicţionar
Secvenţă	Simbol
B.C	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$
GT	$\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$

Noile intrări sunt adăugate celor deja prezente în dicționar, extinzându-l pe măsură ce avansați cu prelucrarea informațiilor de comprimat.

Înlocuind secvențele repetate cu noile simboluri, obținem următorul rezultat:

\alpha _{1}

{\ displaystyle \ alpha _ {1}}

\ alfa _ {1}

\alpha _{2}

{\ displaystyle \ alpha _ {2}}

\ alfa _ {2}

\alpha _{1}

{\ displaystyle \ alpha _ {1}}

\ alfa _ {1}

\alpha _{2}

{\ displaystyle \ alpha _ {2}}

\ alfa _ {2}

\alpha _{1}

{\ displaystyle \ alpha _ {1}}

\ alfa _ {1}

G.

Noul șir este construit pe o extensie a alfabetului inițial și anume:

\sum =\{A,C,G,T,\alpha _{1},\alpha _{2}\}

{\ displaystyle \ sum = \ {A, C, G, T, \ alpha _ {1}, \ alpha _ {2} \}}

{\ displaystyle \ sum = \ {A, C, G, T, \ alpha _ {1}, \ alpha _ {2} \}}

Rezultatul comprimării constă doar din șirul codificat, deoarece dicționarul nu este stocat deoarece, în realitate, alegerea sub-șirurilor de inserat în dicționar are loc după criterii foarte specifice care permit reconstrucția aceluiași pornind de la date comprimate.

Intrarea algoritmului de decompresie ( decodor ) este deci un șir format din date (simboluri A, C, G, T) și coduri speciale (simboluri $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ , $\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$ ). Sarcina decompresiei este de a reconstrui șirul original prin procesarea datelor codificate.

Următoarele intrări discută în detaliu procesarea intrării în faza de compresie, cunoscută și sub numele de fază de codificare , și în faza de decompresie ( decodare ).

Comprimare

Ca prim pas în dicționar sunt introduse toate simbolurile alfabetului, folosindu-le ca coduri speciale.

În exemplu, dicționarul inițial este compus după cum urmează:

Dicţionar
Secvenţă	Cod
LA	LA
C.	C.
G.	G.
T.	T.

Pentru a determina intrările care vor fi inserate în dicționar, algoritmul folosește un șir separat, de acum înainte numit tampon, care va fi modificat / șters de mai multe ori în timpul execuției. Inițial tamponul este gol, adică nu conține simboluri.

Șirul începe să fie examinat de la primul simbol; diferitele caractere întâlnite sunt colectate în buffer, până la formarea unei secvențe care nu este conținută în dicționar. În exemplul „ACGTACGTACG” aveți următorii pași (partea conținută în buffer este evidențiată în galben):

Fiecare linie descrie starea algoritmului înainte de efectuarea iterației sale.

Repetare	Intrare	Tampon curent	Simbol în ieșire	Intrare adăugată în dicționar
1	ACGTACGTACG	(gol)	(nimeni)	(nici unul)
2	Un CGTACGTACG	LA
3	AC GTACGTACG	B.C

În acest moment, tamponul conține o secvență care nu este prezentă în dicționar. Când se efectuează a treia iterație, se vor efectua următorii pași:

Din memoria tampon, care nu este conținută în dicționar, sunt considerate toate simbolurile, cu excepția ultimului: în exemplul A. Prin aceasta, se obține un șir conținut în dicționar.
Șirul A din buffer este căutat în dicționar, trimitând codul asociat, care în acest caz coincide cu A.
Întregul buffer (AC) este inserat ca o nouă intrare de dicționar, asociindu-l cu un nou simbol ( $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ ).
Tamponul este înlocuit cu ultimul său caracter (în acest caz AC devine C)

În acest moment, scanarea se reia de la următorul simbol, adică de la al treilea. Mai jos este tabelul cu diferiți pași efectuați de algoritm:

Repetare	Intrare	Tampon curent	Simbol în ieșire	Intrare adăugată în dicționar
4	A C GTACGTACG	C.	LA	AC (( $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ )))
5	A CG TACGTACG	CG
6	AC G TACGTACG	G.	C.	CG (( $\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$ )))
7	AC GT ACGTACG	GT
8	ACG T ACGTACG	T.	G.	GT (( $\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$ )))
9	ACG TA CGTACG	TA
10	ACGT ÎN CGTACG	LA	T.	TA (( $\alpha _{4}$ ${\ displaystyle \ alpha _ {4}}$ ${\ displaystyle \ alpha _ {4}}$ )))

Dicţionar
Secvenţă	Cod
LA	LA
C.	C.
G.	G.
T.	T.
B.C	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$
CG	$\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$
GT	$\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$
TA	$\alpha _{4}$ ${\ displaystyle \ alpha _ {4}}$ ${\ displaystyle \ alpha _ {4}}$

Pe măsură ce procesarea progresează, secvențe din ce în ce mai lungi vor fi disponibile în dicționar, care pot fi afișate cu un singur simbol. Continuând să executăm algoritmul, avem următorii pași:

Repetare	Intrare	Tampon curent	Simbol în ieșire	Intrare adăugată în dicționar
11	ACGT AC GTACG	B.C
12	ACGT ACG TACG	ACG
13	ACGTAC G TACG	G.	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	ACG (( $\alpha _{5}$ ${\ displaystyle \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {5}}$ )))
14	ACGTAC GT ACG	GT
15	ACGTAC GTA CG	GTA
16	ACGTACGT A CG	LA	$\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$	GTA (( $\alpha _{6}$ ${\ displaystyle \ alpha _ {6}}$ ${\ displaystyle \ alpha _ {6}}$ )))
17	ACGTACGT AC G	B.C
18	ACGTACGT ACG	ACG
19	ACGTACGTACG		$\alpha _{5}$ ${\ displaystyle \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {5}}$

Dicţionar
Secvenţă	Cod
LA	LA
C.	C.
G.	G.
T.	T.
B.C	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$
CG	$\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$
GT	$\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$
TA	$\alpha _{4}$ ${\ displaystyle \ alpha _ {4}}$ ${\ displaystyle \ alpha _ {4}}$
ACG	$\alpha _{5}$ ${\ displaystyle \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {5}}$
GTA	$\alpha _{6}$ ${\ displaystyle \ alpha _ {6}}$ ${\ displaystyle \ alpha _ {6}}$

Șirul codat este ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ . Intrarea ACGT ACGT ACG este de 11 simboluri, în timp ce ieșirea ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ este de 7 simboluri, deci raportul de compresie este:

$\left(1-{\frac {7}{11}}\right)*100\approx 36\%$ ${\ displaystyle \ left (1 - {\ frac {7} {11}} \ right) * 100 \ approx 36 \%}$ ${\ displaystyle \ left (1 - {\ frac {7} {11}} \ right) * 100 \ approx 36 \%}$

Din acest exemplu se poate observa că, pentru a obține o compresie bună, datele de intrare trebuie să conțină numeroase repetări. Pe măsură ce lungimea datelor de comprimare crește, raportul de compresie tinde asimptotic la maxim. ^[2]

Pseudocodul de compresie este prezentat mai jos. Se presupune că dicționarul este deja inițializat cu simbolurile alfabetului):

 tampon = GOL
CICLU
CITIȚI SIMBOLUL k
DACĂ buffer + k EXISTĂ ÎN DICȚIONAR
tampon = tampon + k
IN CAZ CONTRAR
// Căutați tamponul în DICȚIONAR, returnând codul asociat
cod = DICȚIONAR [tampon]
Trimite codul
ADĂUGAȚI tampon + k LA DICȚIONAR
tampon = k
ÎNCHEI DACĂ
SFÂRȘITUL CICLULUI

Decompresie

Inițial, dicționarul decodorului este identic cu cel al codificatorului la începutul procesului de compresie și conține, de asemenea, doar intrări ale simbolurilor alfabetului.

Deci, în mod similar, dicționarul arată astfel:

Dicţionar
Secvenţă	Cod
LA	LA
C.	C.
G.	G.
T.	T.

Tamponul își asumă, de asemenea, aceeași stare inițială ca tamponul codificatorului, de fapt este în prezent gol, dar va fi folosit întotdeauna pentru intrări noi.

Decodorul începe procesul de decompresie analizând șirul comprimat, traducând și convertind fiecare simbol. În acest caz:

ACGT

\alpha _{1}\alpha _{3}\alpha _{5}

{\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}

{\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}

Iterațiile sunt după cum urmează:

Repetare	Intrare	Tampon curent	Presupunere	Simbol în ieșire	Intrare adăugată în dicționar
1	ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$	(gol)		(nimeni)	(nici unul)
2	Pentru CGT $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$	LA	A +?	LA
3	AC GT $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$	C.	C +?	C.	AC (( $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ )))
4	Un CG T $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$	G.	G +?	G.	CG (( $\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$ )))
5	AC GT $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$	T.	T +?	T.	GT (( $\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$ )))

Dicţionar
Secvenţă	Cod
LA	LA
C.	C.
G.	G.
T.	T.
B.C	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$
CG	$\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$
GT	$\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$

La fiecare iterație, decodificatorul citește un simbol X, îl trimite și îl introduce în buffer, compus din conjectura X +? unde este "?" este următorul simbol pe care decodorul nu îl cunoaște încă. Următorul simbol este întotdeauna primul din următoarea lectură, inclusiv cazul citirii articolelor noi: de exemplu, dacă următoarea lectură este un element nou care are ACG ca un șir de simboluri, numai A. Conținutul bufferului este adăugat ca unul nou. element și apoi este lăsat doar simbolul în curs de citire. Cu toate acestea, există un caz în care următorul simbol nu este prezent în dicționar (vezi caz special). Până în prezent, procesul de decompresie a urmat o procedură similară cu cea a compresiei, având în vedere faptul că primele simboluri nu au fost comprimate deoarece șirul inițial nu conținea secvențe care nu erau prezente în dicționar. Diferențele substanțiale de decompresie constau în utilizarea conjecturilor X +? tampon. Când decodificatorul ajunge la un simbol care coincide cu una dintre noile intrări din dicționar, îl traduce, îl trimite și-și aplică conjectura. Simbolul $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ în dicționar coincide cu AC, deci codificatorul transmite AC și aplică conjectura AC +?, așa cum se arată mai jos cu a 6-a iterație. Procesul de decompresie continuă în același mod până când se termină șirul.

Repetare	Intrare	Tampon curent	Presupunere	Simbol în ieșire	Intrare adăugată în dicționar	Conversie
6	ACG T $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ $\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {3} \ alpha _ {5}}$	B.C	AC +?	B.C	TA (( $\alpha _{4}$ ${\ displaystyle \ alpha _ {4}}$ ${\ displaystyle \ alpha _ {4}}$ )))	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ = AC
7	ACGT $\alpha _{1}\alpha _{3}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3}}$ $\alpha _{5}$ ${\ displaystyle \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {5}}$	ACG	GT +?	GT	ACG (( $\alpha _{5}$ ${\ displaystyle \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {5}}$ )))	$\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$ = GT
8	ACGT $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ $\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {3} \ alpha _ {5}}$	GTA	ACG +?	ACG	GTA (( $\alpha _{6}$ ${\ displaystyle \ alpha _ {6}}$ ${\ displaystyle \ alpha _ {6}}$ )))	$\alpha _{5}$ ${\ displaystyle \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {5}}$ = ACG
9	ACGT $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ $\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {3} \ alpha _ {5}}$

Dicţionar
Secvenţă	Cod
LA	LA
C.	C.
G.	G.
T.	T.
B.C	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$
CG	$\alpha _{2}$ ${\ displaystyle \ alpha _ {2}}$ $\ alfa _ {2}$
GT	$\alpha _{3}$ ${\ displaystyle \ alpha _ {3}}$ ${\ displaystyle \ alpha _ {3}}$
TA	$\alpha _{4}$ ${\ displaystyle \ alpha _ {4}}$ ${\ displaystyle \ alpha _ {4}}$
ACG	$\alpha _{5}$ ${\ displaystyle \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {5}}$
GTA	$\alpha _{6}$ ${\ displaystyle \ alpha _ {6}}$ ${\ displaystyle \ alpha _ {6}}$

Șirul obținut este, prin urmare, ACGTACGTACG (11 simboluri), care în comparație cu acel ACGT comprimat $\alpha _{1}\alpha _{3}\alpha _{5}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ ${\ displaystyle \ alpha _ {1} \ alpha _ {3} \ alpha _ {5}}$ (7 simboluri), are încă 4 simboluri (11-7 simboluri), raportând astfel aceeași dimensiune ca șirul inițial înainte de procesul de compresie și decompresie. La sfârșitul decompresiunii avem același dicționar final al compresiei, ajungând astfel la concluzia că nu este necesar să se trimită dicționarul, deoarece este reconstruit de decodor într-un mod complet independent. Aceasta confirmă validitatea metodei de compresie LZW fără a raporta pierderea simbolurilor sau, mai general, a datelor. Pseudocodul asociat cu decompresia este structurat după cum urmează:

 TRIMITE k
tampon = k
CICLU
CITIȚI codul
șir = DICȚIONAR [cod]
ieșire subșir
ADĂUGAȚI tampon + PRIMUL CARACTER AL subcordului LA DICȚIONAR
buffer = substring
SFÂRȘITUL CICLULUI

Caz special

Există un caz special de decompresie, în care decodorul primește un cod Z care nu este încă în dicționar. Atâta timp cât decodorul este întotdeauna un cod înapoi la codificator, Z poate fi în dicționarul codificatorului numai dacă codificatorul îl generează, atunci când emite codul X anterior pentru Y. Deci, codurile Z, unele ω care sunt Y +? iar decodificatorul poate determina caracterul necunoscut după cum urmează:

Decodorul citește X = C și apoi Z = alfa1
Cunoaște secvența lui X și Z identificată cu Y + unele secvențe unknown necunoscute
Decodorul știe că Z a fost adăugat în dicționarul codificatorului pentru Y + un caracter necunoscut „?”
Știi că "?" este prima literă a lui ω
Prima literă a lui ω = Y +? trebuie să fie și prima literă a lui Y
ω trebuie deci să fie Y + x, unde x este prima literă a lui Y (x =?)
Aceasta implică faptul că Z = ω = Y + x
Găsit Z, acesta este introdus în dicționar
Procedăm în același mod cu restul decompresiei

Această situație apare ori de câte ori codificatorul întâlnește intrări sub forma cScSc, unde c este un singur caracter și S este un șir; cS este deja în dicționar, dar cSc nu. Codificatorul transmite codul pentru cS, introducând un nou cod pentru cSc în dicționar. Apoi detectează prezența cSc în intrare, începând de la al doilea c al cScSc și emite noul cod abia introdus. Deși o intrare a acestui formular este rară, acest model devine destul de comun atunci când fluxul de intrare este caracterizat de repetări semnificative. În special, șirurile lungi de un singur caracter, care sunt frecvente în diferite tipuri de imagini, generează în mod repetat astfel de modele. Următorul exemplu clarifică acest caz:

„CCC”

Acesta este, de asemenea, un caz special în forma cScSc și cS, mai precis. Procesul de compresie a acestui șir are loc în mod regulat, așa cum se arată în următorul tabel:

Repetare	Intrare	Tampon curent	Simbol în ieșire	Intrare adăugată în dicționar
1	CCC	(gol)	(nimeni)	(nici unul)
2	C CC	C.
3	CC C	CC
4	C C C	C.	C.	CC (( $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ )))
5	C CC	CC
6	CCC		$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$

Dicţionar
Secvenţă	Cod
C.	C.
CC	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$

Prin urmare, șirul comprimat este:

„C

\alpha _{1}

{\ displaystyle \ alpha _ {1}}

\ alfa _ {1}

"

Pentru procesul de decompresie apar primele probleme deoarece lipsește $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ în dicționarul de decodare:

Repetare	Intrare	Tampon curent	Presupunere	Simbol în ieșire	Intrare adăugată în dicționar	Conversie
1	C. $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	(gol)		(nimeni)	(nici unul)
2	C. $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	C.	C +?	C.
3	C. $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$					$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ = ???

Dicţionar
Secvenţă	Cod
C.	C.

Prin urmare, este necesar să se adopte metoda menționată mai sus: intrarea lipsă se obține prin adăugarea simbolului decomprimat în iterația anterioară cu primul său caracter care îl compune. În acest caz, C este simbolul anterior decomprimat și deja trimis; primul său personaj nu poate fi decât el însuși, deoarece simbolul nu este o voce nouă. Deci intrarea lipsă este $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ = CC. Dacă decompresia anterioară era un simbol compus din caracterele AC, atunci intrarea lipsă a fost obținută adăugând la această intrare primul său caracter, și anume A: $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ = AC + A = ACA.

Revenind la exemplu:

Repetare	Intrare	Tampon curent	Primul personaj	Presupunere	Simbol în ieșire	Intrare adăugată în dicționar	Conversie
1	C. $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	(gol)			(nimeni)	(nici unul)
2	C. $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	C.		C +?	C.
3	C. $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	C.	C.			CC (( $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ )))
4	C. $\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$	CC		CC +?	CC		$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$ = CC

Dicţionar
Secvenţă	Cod
C.	C.
CC	$\alpha _{1}$ ${\ displaystyle \ alpha _ {1}}$ $\ alfa _ {1}$

În acest fel, obțineți același șir de pornire necomprimat, fără pierderi de date și rezolvând, de asemenea, problema codului lipsă din dicționar. Pseudocodul „alternativ” pentru acest caz special este după cum urmează:

 CITEȘTE k
TRIMITE k
tampon = k
CICLU
CITIȚI codul
DACĂ codul este prezent în dicționar
șir = DICȚIONAR [cod]
ieșire subșir
ADĂUGAȚI tampon + PRIMUL CARACTER AL subcordului LA DICȚIONAR
buffer = substring
IN CAZ CONTRAR
ADĂUGAȚI k + PRIMUL CARACTER AL lui K LA DICȚIONAR
șir = DICȚIONAR [cod]
substring outuput
buffer = substring
SFÂRȘITUL CICLULUI

Implementare

Implementarea concretă a algoritmului LZW prezintă câteva considerații / probleme care nu reies din exemplele anterioare. Până în prezent, de fapt, descrierea a făcut uz de instrumente „matematice” ideale .

În informatică, un simbol sau mai bine un caracter este reprezentat de o succesiune de biți de lungime prestabilită. De exemplu, simbolurile unui alfabet format din toate caracterele posibile pe 3 biți sunt:

Alfabet (3 biți / simbol)
Șir de biți	Valoare zecimală
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

Un șir de „0” și „1” poate fi interpretat ca un număr natural scris în baza 2, care este adesea folosit pentru a face referire în zecimal .

Numărul de simboluri care pot fi reprezentate cu n biți este dat de formulă $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ . Valorile zecimale corespunzătoare vor merge de la la $2^{n}-1$ ${\ displaystyle 2 ^ {n} -1}$ $2 ^ {n} -1$ .

Intrare

Datele de intrare ale ambelor faze ( codificare și decodare ) sunt în esență un flux de biți de orice lungime, totuși modul în care sunt interpretate poate fi diferit între cele două faze. De exemplu următorul șir

ar putea fi înțeles ca două simboluri de 3 biți,

 010 111

sau trei simboluri pe 2 biți:

 01 01 11

Prin urmare, este clar că codificatorul și decodificatorul pentru a citi un simbol trebuie să stabilească din câte biți constă.

Intrare codificator

Datele de intrare ale algoritmului de compresie ar putea fi:

 010101110100100101001011010010010101000001000101010001000100100101000001

O alegere tipică este de a utiliza șiruri lungi de 8 biți pentru a reprezenta fiecare personaj. Acest lucru se datorează în principal din două motive:

Pe baza arhitecturii sale, CPU poate manipula blocuri de date a căror lungime este un multiplu de 8 biți.
Codificarea ASCII standard, răspândită în toată lumea, folosește 8 biți pe caracter.

În exemplu, alfabetul inițial, pe care se bazează codificatorul pentru a citi intrarea, este alcătuit din toate simbolurile care pot fi reprezentate de această codificare, care sunt $2^{8}=256$ ${\ displaystyle 2 ^ {8} = 256}$ $2 ^ 8 = 256$ . Deci, fluxul de biți anterior trebuie citit în blocuri de 8 biți:

 01010111_01001001_01001011_01001001_01010000_01000101_01000100_01001001_01000001

Codificarea ASCII asociază un caracter fiecărui șir de 8 biți. De exemplu, litera „A” corespunde codului 65, în binarul 01000001.

Introducerea exemplului este reprezentarea codificată a scrierii.

 WIKIPEDIA

Ieșire codificator / intrare decodor

Ieșirea codificatorului constituie ceea ce decodificatorul citește în intrare, prin urmare este esențial ca cele două faze să fie în acord în modul în care datele sunt interpretate.

Ideea de bază a LZW este extinderea alfabetului inițial prin adăugarea de noi simboluri „speciale”, toate acestea putând fi folosite în dicționar.

Alfabetul extins trebuie să includă atât simbolurile alfabetului inițial, în exemplu cele ale codificării ASCII , cât și simbolurile „speciale”. În orice caz, toate simbolurile trebuie să fie reprezentate prin șiruri de biți diferite, altfel nu va fi posibil să se distingă un simbol de altul.

În exemplu, codificarea ASCII adoptată folosește deja toate șirurile posibile de 8 biți, deci nu există „spațiu” pentru adăugarea de noi simboluri pe 8 biți. În general, pentru a extinde alfabetul, este necesar să utilizați un număr mai mare de biți pentru a codifica fiecare simbol.

În publicația lui Welch din 1984, autorul alege să codifice simbolurile de 8 biți ale alfabetului inițial în simboluri de 12 biți cu lungime fixă. Primele 256 de combinații corespund simbolurilor inițiale, în timp ce restul de 3840 ( $2^{12}-2^{8}=4096-256=3840$ ${\ displaystyle 2 ^ {12} -2 ^ {8} = 4096-256 = 3840}$ ${\ displaystyle 2 ^ {12} -2 ^ {8} = 4096-256 = 3840}$ ) sunt folosite în dicționar ca simboluri speciale. În mod normal, atunci când extindeți un alfabet, vă asigurați că simbolurile alfabetului inițial și cele ale alfabetului extins au aceleași valori în zecimal. De exemplu, simbolul "A" pe 8 biți conform codului ASCII :

 0100 0001

în alfabetul extins de 12 biți devine:

 0000 0100 0001

În ambele cazuri, litera „A” corespunde numărului zecimal 65.

Prin urmare, există o distincție între:

Numărul de biți utilizați pentru a reprezenta fiecare simbol al alfabetului inițial (de exemplu, 8 biți pentru codificarea ASCII).
Numărul de biți utilizați pentru a reprezenta fiecare simbol al alfabetului extins (de exemplu, 12 biți).

Algoritmii de codificare și decodare trebuie să aibă convenții comune: numărul de biți pe simbol este unul dintre parametrii comuni conveniți în prealabil.

Comanda de biți

Același subiect în detaliu: ordinea biților .

Un alt parametru care trebuie convenit este ordinea în care biții sunt scrise / citite în memorie.

În exemplu, similar cu scrierea numerelor zecimale, un șir binar este scris de la cifra cu cea mai mare greutate ( MSB ) la cifra cu cea mai mică greutate ( LSB ) de la stânga la dreapta.

 MSB ---> 100011110100 <--- LSB

Implementarea algoritmului LZW prezintă necesitatea, în special pentru simbolurile alfabetului extins, de a lucra cu șiruri de orice lungime. Dacă se va emite un simbol pe 12 biți

100011110100

sunteți forțat să scoateți un șir lung de 16 biți (2 octeți) deoarece CPU nu poate manipula șiruri de orice lungime, ci doar un multiplu de 8 biți (adică un octet ).

Există două convenții pentru sortarea biților:

LSB-First („Cel mai puțin semnificativ bit întâi”, cel mai puțin semnificativ primul bit ).
MSB-First („Bitul cel mai semnificativ primul”, primul bit cel mai semnificativ ).

Fișierele GIF folosesc LSB-First , în timp ce fișierele TIFF și PDF folosesc MSB-First .

LSB-În primul rând

Cu metoda LSB-First , primii 8 biți cel mai puțin semnificativi (în exemplul 11110100) sunt aliniați cu LSB-ul primului octet. Restul de 4 biți cei mai semnificativi (1000) sunt aliniați cu LSB al celui de-al doilea octet. Orice biți rămași sunt completați cu zerouri (în acest caz 4). Dacă un nou simbol este trimis mai târziu, acesta va începe de la LSB-ul unui nou octet. Șirul de ieșire 100011110100 cu metoda LSB-First devine:

Octeți în ieșire
Primul octet	Al doilea octet
11110100	00001000

MSB-First

Cu metoda MSB-First , primii 8 biți cei mai semnificativi (în exemplul 10001111) sunt aliniați cu MSB-ul primului octet. Restul de 4 biți cel puțin semnificativi (0100) sunt aliniați cu MSB-ul celui de-al doilea octet. Orice biți rămași sunt completați cu zerouri (în acest caz 4). Dacă ulterior este trimis un nou simbol, acesta va începe de la MSB-ul unui nou octet. Șirul de ieșire 100011110100 cu metoda MSB-First devine:

Octeți în ieșire
Primul octet	Al doilea octet
10001111	01000000

Coduri de lungime variabilă

Codurile cu lungime variabilă sunt utilizate în diverse contexte de date. De exemplu, într-o imagine bazată pe un tabel de culori (sau paletă) alfabetul de font natural este un set de palete indexate; în 1980 mai multe imagini aveau palete mici, de ordinul a 16 culori. Pentru acest alfabet, codurile pe 12 biți au produs o compresie slabă dacă imaginea nu era mare; din această constrângere a început să fie introdus conceptul de cod cu lungime variabilă: codurile începeau de obicei cu o lungime de un bit mai mare decât simbolurile care urmează a fi codificate și, așa cum se utilizează în fiecare cod, lungimea crește progresiv cu un bit, în sus până la un maxim prescris, de obicei 12 biți. Un exemplu este un flux de coduri care începe de la 0 și merge până la 10000 (binar):

Cod bit	Numărul de biți
0	1
1	1
10	2
11	2
100	3
101	3
110	3
111	3
1000	4
1001	4
1010	4
1011	4
1100	4
1101	4
1110	4
1111	4
10000	5

Dacă se utilizează coduri cu lungime variabilă, codificatorul și decodificatorul trebuie să sincronizeze schimbarea lungimii astfel încât să aibă loc în același punct al unei date codificate, altfel nu vor fi de acord cu lungimile codului din cele două fluxuri. În versiunea standard, codificatorul

creșteți lungimea p p + 1 când întâlnește o secvență ω care nu este prezentă în dicționar, deci trebuie adăugat codul, dar următorul cod disponibil din dicționar are 2 ^p lungime (primul cod necesită p + 1 bit). Codificatorul trimite codul pentru ω cu lungimea p (până când codul necesită trimiterea p + 1 bit), apoi crește lungimea, astfel încât următorul cod să fie lung de p + 1 bit. Decodificatorul este întotdeauna un cod înaintea codificatorului în construcția dicționarului, astfel încât atunci când citește codul pentru ω, generează o intrare de lungime 2 ^p -1. Când codificatorul mărește lungimea codului, decodorul trebuie să-l mărească în același mod, astfel încât cel mai lung cod să fie conținut în p biți (aceeași lungime, deci, a celui mai lung cod al codificatorului).

Schimb anticipat

Primele implementări ale algoritmului cresc mai întâi lungimea codului și apoi trimit codul pentru ω, deci ω avea lungimea codului nou și nu cea veche; același lucru și pentru decodor, care schimbă lungimea unui cod prea devreme. Acest fenomen se numește „Schimbare timpurie”; această versiune în trecut a provocat o mulțime de confuzie în contextul fișierelor gestionate de exemplu de Adobe. Ora Adobe nei file PDF permette entrambe le versioni, ossia con o senza Cambio Anticipato, includendo un flag esplicito nell'intestazione di ogni flusso di compressione LZW per indicare il Cambio Anticipato. Per quanto riguarda i formati che gestiscono dati grafici, GIF o TIF per esempio, il Cambio Anticipato non è utilizzato. Quando il dizionario viene ripulito da un "clear code", sia l'encoder sia il decoder cambiano la lunghezza codice solo dopo che il "clear code" è ritornato alla lunghezza iniziale.

Affinamenti

Ulteriori affinamenti includono:

Un "clear code": un codice riservato ad indicare quando il dizionario deve essere ripulito. Tipicamente è il primo valore immediatamente successivo a tutti i valori di ogni carattere dell'alfabeto. Ad esempio se in totale l'alfabeto di ogni singolo carattere è 255, il clear code è 256. Il clear code permette di reinizializzare il dizionario, una volta pieno, in modo da permettere un adattamento della codifica, cambiando lo schema dei dati in input.
Uno "stop code": un codice per indicare la fine del dato. Tipicamente un valore più grande del clear code. Nel precedente esempio, lo stop code è 257.

Alcuni encoder sviluppati possono monitorare l'efficienza e ripulire la tavola ogni qualvolta il dizionario esistente non corrisponde all'input. È fondamentale che encoder e decoder siano in accordo alla varietà di LZW da utilizzare:

La dimensione dell'alfabeto
La lunghezza massima del codice
Quale lunghezza variabile è in uso
La dimensione del codice iniziale
Quali clear e stop code sono in uso ei loro valori.

Molti formati che impiegano l'LZW costruiscono queste informazioni in specifici formati oppure forniscono campi espliciti nell'intestazione della compressione.

Applicazioni

Il metodo divenne ampiamente usato in programmi di compressione e divenne più o meno un'utility standard nei sistemi Unix circa nel 1986. Da allora è scomparso da molti sistemi, per ragioni giuridiche e tecniche, ma a partire dal 2008 almeno FreeBSD comprende le utilità di compressione e decompressione come parte della distribuzione. Molti altri popolari programmi utilizzano anche questo algoritmo o metodi strettamente connessi. È diventato in uso in larga scala dopo che divenne parte del formato GIF nel 1987. È anche facoltativamente usato in file TIFF . La compressione LZW fornisce uno dei migliori livelli di compressione, in molte applicazioni, rispetto a qualsiasi metodo ben noto a disposizione fino a quel momento. È diventato il primo metodo di compressione di dati universale utilizzato ampiamente su computer. In genere comprime grandi testi in lingua inglese a circa la metà delle loro dimensioni originali. Oggi un'implementazione dell'algoritmo è contenuta nei popolari programmi software Adobe Acrobat . Comunque Acrobat per default usa l'algoritmo DEFLATE per molti testi ed immagini basati su tavole di colori.

Varianti

LZMW (1985, by V. Miller, M. Wegman) ^[3] - Cerca input per le stringhe più lunghe presenti nel dizionario (la corrispondenza "corrente"); aggiunge la concatenazione di precedenti corrispondenze con quella corrente al dizionario. Il dizionario si riempie più velocemente, ma questo schema è più complesso da implementare. Miller e Wegman inoltre consigliano di eliminare le voci con bassa ricorrenza dal dizionario quando si riempie.
LZAP (1988, by James Storer) ^[4] - modifica dell'LZMW: invece di aggiungere solo la concatenazione della corrispondenza precedente con quella corrente al dizionario, aggiunge le concatenazioni della corrispondenza precedente con ogni sottostringa iniziale di quella in corso.
LZWL è una variante dell'LZW basata su sillabe.

Note

^ Terry Welch, "A Technique for High-Performance Data Compression" , IEEE Computer , June 1984, p. 8–19.
^ Jacob Ziv and Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding , IEEE Transactions on Information Theory, September 1978.
^ David Salomon, Data Compression – The complete reference , 4th ed., page 209
^ David Salomon, Data Compression – The complete reference , 4th ed., page 212

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su Lempel-Ziv-Welch

Collegamenti esterni

Un applet JAVA che mostra passo passo il processo di compressione/decompressione di una stringa. , su projects.hudecof.net . URL consultato il 2 marzo 2010 (archiviato dall' url originale il 7 gennaio 2010) .
Welch, TA, A Technique for High-Performance Data Compression , Computer, vol. 17, no. 6, pp. 8–19, June 1984 (Link alternativo).
( EN ) – Un articolo sulla compressione LZW.
Un'implementazione ottimizzata in C++ dell'algoritmo di LZW, sorgenti e articolo dell'autore. , su oldwildweb.com .
( EN ) US4558302 , United States Patent and Trademark Office , Stati Uniti d'America. , Terry A. Welch, High speed data compression and decompression apparatus and method

Portale Informatica : accedi alle voci di Wikipedia che trattano di informatica

[WelchIEEE-1] Terry Welch, "A Technique for High-Performance Data Compression" , IEEE Computer , June 1984, p. 8–19.

[2] Jacob Ziv and Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding , IEEE Transactions on Information Theory, September 1978.

[3] David Salomon, Data Compression – The complete reference , 4th ed., page 209

[4] David Salomon, Data Compression – The complete reference , 4th ed., page 212

[1]

[2]

[3]

[4]