LZW

LZW (Lempel-Ziv-Welch) és un algorisme de compressió sense pèrdua, desenvolupat per Terry Welch el 1984 com una versió millorada de l'algorisme LZ78, desenvolupat per Abraham Lempel i Jacob Ziv.

Descripció de l'algorisme

La majoria dels mètodes de compressió es basen en una anàlisi inicial del text per identificar cadenes repetides per armar un diccionari d'equivalències, assignant codis breus a aquestes cadenes. En una segona etapa, es converteix el text utilitzant els codis equivalents per a les cadenes repetides. Això requereix dues etapes, una d'anàlisi i una segona de conversió i també requereix que el diccionari es trobi juntament amb el text codificat, incrementant la mida del fitxer de sortida.

La clau del mètode LZW es pot crear sobre la marxa, de manera automàtica i en una única passada d'un diccionari de cadenes que es trobin dins del text a comprimir, mentre que -a la vegada- es procedeix a la seva codificació. Aquest diccionari no és transmès amb el text comprimit, ja que el descompressor pot reconstruir-lo usant la mateixa lògica amb què ho fa el compressor i, si està codificat correctament, tindrà exactament les mateixes cadenes que el diccionari del compressor tenia.

El diccionari comença precarregat amb 256 entrades, una per a cada caràcter (byte) i és possible més d'un codi predefinit per indicar el final d'arxiu. A aquesta taula se li van afegint successius codis numèrics per cada nou parell de caràcters consecutius que es llegeixin (això no és literalment cert, segons es descriu tot seguit), encara que no sigui possible preveure si aquest codi es reutilitzarà més endavant o no.

És en aquest detall on es troba la brillantor del mètode: en armar el diccionari sobre la marxa s'evita fer dues passades sobre el text, una analitzant i l'altra codificant. Atès que la regla d'armat del diccionari és tan simple, el descompressor pot reconstruir a partir del text comprimit mentre el llegeix, evitant així incloure el diccionari dins del text comprimit. Es pot objectar que el diccionari estarà ple de codis que no s'utilitzaran i per tant, serà innecessàriament gran, però a la pràctica el diccionari no creix massa i encara si ho fes, no importa molt perquè l'objectiu és que l'arxiu comprimit sigui petit encara que els processos de compressió i descompressió poguessin ocupar molta memòria amb el diccionari.

Les entrades del diccionari poden representar seqüències de caràcters simples o seqüències de codis de tal manera que un codi pot representar dos caràcters o pot representar seqüències d'altres codis prèviament carregats que al seu torn representen, cada un d'ells, altres codis o caràcters simples, o sigui que un codi pot representar des d'un a un nombre indeterminat de caràcters. En realitat, l'algoritme no discrimina entre codis i caràcters simples, ja que el diccionari es carrega inicialment de codis que representen els primers 256 caràcters simples per la qual cosa aquests no són més que altres codis dins del mateix diccionari.

Cada vegada que es llegeix un nou caràcter es revisa el diccionari per veure si forma part d'alguna entrada prèvia. Tots els caràcters estan inicialment predefinits al diccionari així que sempre hi haurà almenys una coincidència, però el que es busca és la cadena més llarga possible. Si el caràcter llegit no forma part de més d'una cadena més llarga, llavors s'emet la més llarga que s'hagués trobat i s'agrega al diccionari una entrada formada per qualsevol que hagués estat el codi previ i aquest nou codi. Si el caràcter llegit sí forma part de més d'una cadena del diccionari, es llegeix un nou caràcter per veure si la seqüència formada pel caràcter previ i el nou és alguna de les trobades en el diccionari. Mentre els caràcters successius que es vagin llegint ofereixin més d'una entrada possible al diccionari, se segueixen llegint caràcters. Quan la cadena només té una entrada al diccionari, llavors s'emet el codi corresponent a aquesta entrada i s'incorpora al diccionari una nova entrada que representa l'últim codi emès i el nou.

Una altra característica important de l'algorisme és que els codis a la sortida es representen per cadenes de bits variables. El diccionari conté inicialment 257 codis, 256 codis per als 256 caràcters simples possibles de 8 bits i un codi que representa la fi d'arxiu. Per això serien necessaris codis de 9 bits, la qual cosa vol dir que encara hi ha disponibles 255 codis de 9 bits per representar cadenes de caràcters. Quan s'omplen aquestes 255 entrades del diccionari, s'amplien els codis amb un nou bit, la qual cosa permet 512 noves entrades. Quan es completen aquestes 512 entrades, s'afegeix un bit i es disposen de 1.024 noves entrades i així successivament. A la pràctica, es verifica que les primeres entrades, corresponents a codis de 12 bits de longitud (4.096 entrades) s'omplen ràpidament pel que és habitual començar el procés no amb codis de 9 bits sinó directament amb codis de 12 bits.

Al seu torn, s'ha comprovat empíricament que la informació en un fitxer presenta 'regionalitat', és a dir, que diferents regions d'un mateix arxiu presenten diferents regularitats, la qual cosa fa que el diccionari que s'hagués format per una regió d'un arxiu pugui no ser útil en una altra regió diferent. L'algoritme preveu que, quan una cadena fora a forçar l'ampliació del diccionari a 17 bits, el diccionari s'esborri del tot, s'inicialitzi novament amb els 256 codis inicials més el codi de fi d'arxiu i es reprengui el procés.

Observeu que donat aquest límit de codis de 16 bits, això vol dir que un diccionari mai no podrà contenir més de 65.536 entrades, cadascuna d'elles de 2 codis de 16 bits, és a dir quatre octets per entrada. El diccionari, llavors, s'arma com una taula on el codi és l'índex i les cadenes que representa són les entrades d'aquesta taula. Cal advertir que el codi no s'emmagatzema a la taula, sinó que és l'índex de la mateixa per la qual cosa no s'emmagatzema sinó que es calcula per la posició a la taula. En total, una taula plena ocupa 65.536 entrades de 4 bytes cadascuna, és a dir, 262.144 caràcters (256 kbytes) el que és absurdament poc per als ordinadors actuals.

Que la mida dels índexs pugui ser incrementada de manera variable és una de les contribucions de Welch. Una altra d'elles va ser especificar una estructura de dades eficient per guardar el diccionari.

Un exemple simple de l'algoritme LZW de compressió

Atès que l'algorisme serveix per comprimir qualsevol seqüència de bits, independentment de si és text o qualsevol altre tipus d'informació, l'exemple a continuació no ha estat traduït de l'original en anglès. En ell se suposa que els textos a comprimir es componen només de lletres majúscules sense espais, per a això n'hi ha prou (en anglès) 26 codis, de l'1 al 26, per a les majúscules més un codi (en aquest cas s'ha adoptat el zero, encara que en la pràctica el 0 és un caràcter vàlid) per representar la fi d'arxiu, que s'ha representat gràficament pel símbol #. El text a comprimir és:

TOBEORNOTTOBEORTOBEORNOT #

i el procés de compressió queda representat per la taula següent. Per interpretar-la, se suggereix ignorar la representació binària, que s'inclou simplement per comptabilitzar la mida del fitxer de sortida. Els codis de l'1 al 26 es corresponen amb caràcters individuals 1 = A, 2 = B, ... 26 = Z i 27 = "fi de fitxer". Del 28 en endavant cada codi representa més d'un caràcter.

Caràcter: Codi emès Entrada al diccionari:
(sortida):

T 20 = 10100
O 15 = 01111 28: TO
B 2 = 00010 29: OB
E 5 = 00101 30: BE
O 15 = 01111 31: EO ←- es van esgotar els codis de 5 bits
R 18 = 010010 32: OR ←- es comença a utilitzar codis de 6 bits
N 14 = 001110 33: RN
O 15 = 001111 34: NO
T 20 = 010100 35: OT
TO 28 = 011100 36: TT
BE 30 = 011110 37: TOB
OR 32 = 100000 38: BEO
TOB 37 = 100101 39: ORT
EO 31 = 011111 40: Tobe
RN 33 = 100001 41: EOR
OT 35 = 100011 42: RNO
#0 = 000000 43: OT #

El text original està compost de 25 caràcters que poden representar-se amb 5 bits cada un i ens donaria 125 bits. El resultat comprimit produeix 5 codis de 5 bits més 12 codis de 6 bits, la qual cosa resulta en 97 bits, una reducció a menys del 78% de l'original. Noteu que cada caràcter llegit genera una nova entrada al diccionari, independentment de si es farà servir o no. Aquesta simplicitat per part de l'algorisme de compressió permet que el descompressor pugui reconstruir el diccionari sense errors.

Quan es comença a utilitzar 6 bits per codi, tots els codis s'emeten amb 6 bits, fins i tot els que originalment només usessin 5 bits, completant amb zeros per esquerra.

Usos

El mètode va arribar a ser utilitzat de forma moderada, però en tota la seva amplitud en el programa compress que va arribar a ser més o menys la utilitat estàndard de compressió en sistemes Unix al voltant del 1986 (ara ha desaparegut pràcticament tant per assumptes legals com tècnics). Altres utilitats de compressió també utilitzen aquest mètode o altres relativament propers.

Es va usar àmpliament des que es va convertir en part del format gràfic GIF l'any 1987. Pot ser també usat, encara que opcionalment, en arxius TIFF.

La compressió LZW proporcionava una relació de compressió millor en moltes aplicacions que altres mètodes de compressió coneguts en aquesta època. Va arribar a convertir-se en el primer mètode de propòsit general de compressió de dades utilitzat àmpliament. En textos llargs, comprimeix aproximadament a la meitat de la mida original. Altres tipus de dades són també comprimits útilment en molts casos.

L'assumpte de les patents

Diverses patents han estat concedides als Estats Units d'Amèrica i altres països per l'algoritme LZW i similars. El LZ78 estava sota la patent 4.464.650, demanada per Lempel, Ziv, Cohn i Eastman i assignada a Sperry Corporation, més tard Unisys Corporation, el 10 d'agost del 1981. Dos patents dels Estats Units van ser creades per al LZW: la patent dels EUA 4.814.746 per Victor S. Miller i Mark N. Wegman i assignada a IBM, originalment l'1 de juny del 1983, i la patent nord-americana 4.558.302 per Welch, assignada a Sperry Corporation, més tard Unisys Corporation, el 20 de juny del 1983.

La patent nord-americana 4.558.302 és la que ha causat la controvèrsia més gran. Unisys un cop va garantir llicències lliurea de patents als desenvolupadors de programari lliure i programari propietari freeware (gratuït, sense finalitats comercials). La companyia va finalitzar aquestes llicències a l'agost del 1999.

Molts experts en lleis conclouen que la patent no cobreix dispositius que només descomprimim LZW i no puguin comprimir dades usant-lo, per aquesta raó el popular programa gzip pot llegir arxius. Z però no escriure'ls.

Es va informar a Weekly News d'acord amb un fil de % 40posting.google.com comp.compression thread, que la patent d'Unisys als EUA va expirar a desembre del 2002 - 17 anys i 10 dies després de ser patentat. No obstant això, la majoria de les fonts informen que va expirar el juny del 2003, 20 anys després de ser arxivada, perquè 35 USC § 154 (c) (1) especifica que les patents subsisteixen 20 anys després de l'Uruguai Round Agreements Act.

D'acord amb una declaració a la web de Unisys, les patents de LZW al Regne Unit, França, Alemanya, Itàlia i Japó han expirat en juny del 2004 i la patent canadenca en juliol del 2004. La patent d'IBM als EUA va expirar l'agost del 2006.

Lempel-Ziv-Welch vs. Ziv-Lempel-Welch

Tot i que l'acrònim LZW es deu, òbviament, als inventors com Lempel, Ziv i Welch, alguna gent opina que el dret de propietat intel·lectual va a Ziv primer, de manera que el mètode s'ha d'anomenar algorisme Ziv - Lempel-Welch, i no algorisme Lempel-Ziv-Welch.

Enllaços externs

• 558,302. WKU. & OS = PN/4.558.302 & RS = PN/4.558.302 United States Patent 4.558.302.

• "LZW Data Compression", by Mark Nelson (DDJ Article amb codi font).

• Sad day ... GIF patent dead at 20 (Article curt i possiblement amb una simplificació de la veritable història; es pot trobar alguna cosa més detallada a la pàgina de GIF).

• Bringing back LZW compression per Nathan Willis.

• List of LZW libraries, papers and other resources.