Codi de Ziv-Lempel

De Viquipèdia
Salta a la navegació Salta a la cerca

El codi de Ziv - Lempel, també conegut com 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.

Com funciona?[modifica]

El codi Ziv - Lempel és un algoritme de compressió que es basa en l'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.[2] És a dir, s'emet un codi en comptes de tota una cadena de caràcters.[3]

El codi que segueix l'algoritme Ziv - Lempel pot ser de qualsevol longitud.[3]

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.

Història[modifica]

L'algoritme de compressió tenia l'objectiu de ser una alternativa a l'algoritme LZ78. Els creadors de l'algoritme van ser Abraham Lempel i Jacob Ziv l'any 1977 i van crear el codi LZ77. Un any més tard van treure una modificació del seu algoritme i el van anomenar LZ78 aquest, permetia comprimir imatge o qualsevol dada que fos binaria.[4]

Al 1978, Terry Welch (un enginyer de l'empresa Unisys) va modificar el codi LZ78 i seguint els estudis fets d'Abraham Lempel i Jacob Ziv i el nou algoritme creat es va anomenar codi Ziv-Lempel (o LZW) en honor als seus creadors.[5] Aquesta ultima modificació va ser feta per a poder implementar el codi dins dels controladors dels discos durs.[4]

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ó.[6]

  1. Mayordomo, Elvira «El algoritmo de compresión de datos LZ78». juny 2003, 29 novembre del 2019, pàg. 60.
  2. Programacion en Castellano, S. L. «Introducción a la compresión de datos: Lempel-Ziv, Gzip» (en spanish). [Consulta: 1r desembre 2019].
  3. 3,0 3,1 Dr. Dobb's Journal «LZW Data Compression». 1 d'octubre de 1989, 29 desembre del 2019, pàg. 1.
  4. 4,0 4,1 Loachamin, Publicado por Robinson. «Lempel-Ziv (T.I.C)» (en castellà). [Consulta: 1r desembre 2019].
  5. «Lempel-Ziv-Welch. Histoire, Concepts de base, Introduction, description LZW». [Consulta: 1r desembre 2019].
  6. Delgado Huaynalaya, Edwin «COMPRESION Y DESCOMPRESION». , 1 desembre del 2019, pàg. 7.