Codi de Ziv-Lempel
| Aquest article o secció necessita millorar una traducció deficient. |
El codi de Ziv-Lempel, també conegut com a LZW, és un algoritme de compressió que deriva de l'algoritme LZ78[1] i va ser publicat el 3 de maig del 1977 per part de Jacob Ziv i Abraham Lempe al IEEE Transactions on Information Theory, vol. IT-23.
Història modifica
L'algoritme ha d'anar complementat amb un algoritme de descompressió per a poder recrear exactament la compressió feta a l'inici. El codi LZW té tanta eficàcia gràcies a que l'algoritme de descomposició no ha de llegir les cadenes de caràcters, si no que les construeix directament i exactament com estaven durant la compressió, gràcies a la utilització dels components STRING i CHARACTER emesos durant la compressió. Això permet que el procediment sigui més fàcil, més ràpid i que les dades comprimides no tinguin la mateixa càrrega que tindrien si s'hagués de fer tota la traducció.[2]
Descripció del algoritme modifica
El codi Ziv - Lempel és un algoritme de compressió que es basa en la idea de reemplaçar les cadenes de caràcters per codis individuals. El funcionament que segueix per a fer-ho és buscant seqüències repetides entre les dades y, la reemplaça per una senyal on comença la primera seqüència, més la longitud que té aquella seqüència a partir de la primera posició. En cas que no hi hagi cap repetició, s'emet la seqüència tota sencera.[3] És a dir, s'emet un codi en comptes de tota una cadena de caràcters.[4]
El codi que segueix l'algoritme Ziv - Lempel pot ser de qualsevol longitud.[4]
El compresor LZW es un sistema de compresión/descompresión muy rápido que se basa en la multiplicidad de los caracteres en la cadena que se va a codificar. A partir de la cadena creaba unos patrones que los integraba en un diccionario. El LZW trabaja con bits y no con bytes, lo que consigue gran compatibilidad a la hora de procesar datos. Este formato es muy utilizado en la comprensión de imágenes TIFF o GIF. Por otra parte, el PNG utiliza el LZ77 por tanto es totalmente libre.
Funcionament modifica
Explicat en l'apartat anterior, la clau del codi és que comprimeix sobre la marxa y de forma automàtica creant un diccionari de cadenes de caràcters y al mateix temps fent la codificació.
El diccionari s'inicia pre-carregat amb 256 entrades, una per a cada caràcter (byte) possible juntament amb un codi ja creat per indicar el final del arxiu. A la cadena es van afegint el nous codis numèrics per cada parell de caràcters consecutius que es llegeixin (encara que no es sàpiga si aquest codi es reutilitzarà més endavant).
Gràcies a la creació del diccionari sobre la marxa la compressió es realitza de forma molt més ràpida i s'evita fer dues llegides del text: una per analitzar-lo i l'altre per codificar la informació.
L'única inconveniència del diccionari és que s'allarga de codis que no s'utilitzaran (ja que només apareixen un sol cop al arxiu).
Cada vegada que el diccionari llegeix un nou caràcter, el diccionari revisa si ja forma part d'ell. Si no forma part encara, el diccionari crea un nou codi. Si el caràcter si forma part del diccionari, es llegeix el caràcter previ i el nou per a veure si hi ha alguna coincidència al diccionari.
Un altre aspecte important del algoritme és que els codis es representen per cadenes de bits variables. El diccionari té a l'inici 256 codis per a 256 caràcters formats cada un per 8 bits més un últim codi que representa el final del arxiu. Aquest representaria que serien necessaris codis de 9 bits, pel que significa que encara són possibles 255 codis de 9 bits. Quan les 255 estan plenes, s'amplien els codis amb un nou bit i permet formar 512 entrades noves i, així successivament pel que si s'omplissin les 512 entrades s'afegiria un altre bit i s'obtindrien 1024 entrades noves.[5]
Exemple modifica
Posem un exemple iniciant el diccionari amb 3 caràcters amb la codificació del 1 al 3. (figura 1)
Després, agafem com a exemple la cadena: ABABBABCABABBA. (figura 2) L'algoritme farà el següent: Agafa el primer caràcter d'entrada (s) i el següent (c). La sortida (output) serà el codi que representarà la cadena original i serà l'equivalent al codi que te el caràcter s al diccionari. A partir d'aquí, el nou codi del nostre nou string va augmentant la unitat i, el nou string es guarda al diccionari per a poder llegir els patrons de caràcters que després es poden repetir.
El procés es va repetint fins que el contingut del arxiu s'acabi.[6]
Descompressió modifica
L'algoritme ha d'anar complementat amb un algoritme de descompressió per a poder recrear exactament la compressió feta a l'inici. El codi LZW té tanta eficàcia gràcies a que l'algoritme de descomposició no ha de llegir les cadenes de caràcters, si no que les construeix directament i exactament com estaven durant la compressió, gràcies a la utilització dels components STRING i CHARACTER emesos durant la compressió. Això permet que el procediment sigui més fàcil, més ràpid i que les dades comprimides no tinguin la mateixa càrrega que tindrien si s'hagués de fer tota la traducció.[2]
Exemple modifica
Per a la descompressió es crea una taula semblant a la del exemple de compressió ja que l'algoritme seguirà el mateix procès. La diferència és que en la descompressió, la cadena de Output és la cadena original que s'introdueix.
L'algoritme de descodificació inicia el procés analitzant la cadena comprimida i, paral·lelament, traduint i transformant els codis. El contingut del diccionari va afegint noves entrades repetint el procés fet a la compressió però al inrevés. No obstant, hi ha un cas especial de caràcter que no està al diccionari (anar al apartat de símbols especials).
Cas especial modifica
Hi ha un cas especial quan es fa la descompressió, quan el descodificador rep un codi que no existeix al diccionari. Mentre que el descodificador sigui sempre un codi de tornada del codificador, significa que existeix, pel que fa que el codi que no esta al diccionari, per exemple amb el nom Z, només pot estar al diccionari emet el codi X anterior de Y.
Aquesta situació es produeix quan el codificador troba una entrada en forma de aBaBa, on nomes hi ha un caràcter i B és una cadena. aB ja existeix al diccionari però aBa no. El codificador emet el codi per cS, inserint un nou codi per a CSC al diccionari. A continuació, detecta la presència de cSc a l'entrada, a partir del segon c de cScSc, i emet el nou codi que s'acaba d'introduir. Encara que les dades d'entrada d'aquesta forma són rares, aquest patró es torna bastant comú quan el flux d'entrada es caracteritza per repeticions significatives. En particular, les cadenes llargues d'un sol caràcter, que són comuns en diversos tipus d'imatges, generen repetidament patrons d'aquest tipus.
Ús modifica
L'algoritme es va convertir en el mètode de compressió més utilitzat per ordinadors. Es va convertir en el programa utilitzar per a comprimir en domini públic al 1986 i es va estendre molt quan va passar a formar part del format d'imatge GIF al 1987. No obstant, l'algoritme ha desaparegut de moltes distribucions ja que gzip va millorar el seu algoritme DEFLATE basat en LZ77 i, des del 2008 almenys FreeBSD inclou tant la compressió com la descompressió com a part de la distribució.
- Imatge GIF
- Arxiu TIFF
- Arxiu PDF
- Imatges basades en text
- Taules de color en arxius PDF
Referències modifica
- ↑ Mayordomo, Elvira «El algoritmo de compresión de datos LZ78». juny 2003, 29-11-2019, p. 60.
- ↑ 2,0 2,1 Delgado Huaynalaya, Edwin «COMPRESION Y DESCOMPRESION». , 01-12-2019, p. 7.
- ↑ Programacion en Castellano, S. L. «Introducción a la compresión de datos: Lempel-Ziv, Gzip» (en castellà). [Consulta: 1r desembre 2019].
- ↑ 4,0 4,1 Dr. Dobb's Journal «LZW Data Compression». 1 d'octubre de 1989, 29-12-2019, p. 1.
- ↑ Gastaldo Ramon, Borja «ESTUDIO DE IMPLEMENTACIÓN DEL ALGORITMO LZW (Lempel-Ziv-Welch) EN UNA PLATAFORMA ZYNQ 7000 DE XILINX». 24 de juliol de 2014, 15-12-2019, p. 26.
- ↑ «[http://users.ece.utexas.edu/~ryerraballi/MSB/pdfs/M2L2.pdf Lossless Compression Multimedia Systems (Module 2 Lesson 2)]». , 16-12-2019, p. 7.