LZW

L'algoritme de Lempel Ziv i Welch, o abreviadamente com millor se li coneix Algoritme LZW, és un algoritme de compressió sense pèrdua basat en diccionari, desenrollat per Terry Welch en 1984 prou temps despuix que fora publicat l'algoritme LZ78 del que és una versió millorada, que a la seua volta era una millora substancialment distinta de l'algoritme LZ77.

Si be, a la llum de l'aparició dels algoritmes de Zip i Lempel va sobrevindre un resorgiment de la compressió, que permaneixia atollada i llimitada en els algoritmes estadístics, este algoritme obri el camí cap a una major eficiència i velocitat.

Estat previ de l'art

La majoria dels métodos de compressió basats en diccionari requerixen dos etapes, una d'anàlisis i una segona de conversió.

L'etapa d'anàlisis inicial té per objecte identificar cadenes repetides per a armar el diccionari de equivalència, assignant còdics breus a estes cadenes. En una segona etapa, es convertix el text utilisant els còdics equivalents per a les cadenes repetides.

Dits algoritmes també requerixen que el diccionari s'almagasene junt en el text codificat, incrementant el tamany de l'archiu d'eixida.

l'Algoritme LZ77 desenrollat per Abraham Lempel i Jacob Ziv precisava guardar 3 senyes (Index, Count i Offset), per a almagasenar una seqüència. Les crítiques constructives abocades sobre dit algoritme influencien la creació del Algoritme LZ78, desenrollat també pels mateixos autors, que solament precisa 2 senyes per a almagasenar la referència de la seqüència comprimida (count i Offset). L'algoritme LZW millora els previs en dit aspecte, puix solament precisa guardar com a senya per a referenciar la seqüència comprimida 1 senya (index), lo que a la seua volta simplifica i accelera tota l'operativa.

Descripció de l'algoritme

La gran ventaja de l'algoritme LZW és que permet crear sobre la marcha el diccionari de cadenes que es troben dins del text a comprimir i al mateix temps (sense requerir una atra etapa) es procedix a la seua codificació.

Ademés, dit diccionari no precisa ser transmés en el text comprimit, ya que el descompresor pot reconstruir-ho, seguint el mateix procediment que fa el compressor. Si està codificat correctament, tindrà exactament les mateixes cadenes que tenia el diccionari del compressor.

El diccionari

El diccionari sol començar en un tamany predefinit, i d'entrada es precarga en les primeres 256 entrades, una per a cada caràcter (byte) possible, més un còdic predefinit usat com un indicador de final de ficher.

Quan el diccionari s'ompli en comprimir, es deu elegir entre buidar el diccionari i tornar a precargarlo i escomençar de nou, o deixar el diccionari fix. L'opció d'aumentar el tamany del diccionari és equivalent a si al principi s'establix eixe tamany al que es vaja a aumentar. El compressor deurà emetre un còdic especial senyalant l'opció elegida si no està prefixada (no elegible). Originalment en el disseny de l'algoritme, el tamany del diccionari venia determinat per la llimitació de la memòria, era puix freqüent que en les primeres implementacions de l'algoritme el diccionari tinguera solament 4096 entrades (12 bits), que després es varen ser ampliant a 14, 15 i 16 bits (64kb). El tamany del diccionari en les implementacions recents (a data de 2022) de l'algoritme, és elegible per l'usuari.

Durant la descompressió se seguix el mateix procediment que durant la compressió. El diccionari es precarga i quan s'ha omplit deu prendre's la mateixa acció que va prendre el compressor. Si no està prefixada per convenció en l'algoritme, en comprimir es deu emetre un còdic especial que el descompresor deu poder reconéixer, per a realisar exactament la mateixa acció.

L'algoritme originalment contempla que, quan una seqüència fòra a forçar l'ampliació del diccionari per damunt del llímit de bits prefixat, el diccionari es borre per complet, es inicialice novament en els 256 còdics inicials més el còdic de fin d'archiu i es recomience el procés.

Note's que donat un llímit teòric de còdics de n bits, un diccionari mai podrà contindre més de 2ⁿ entrades.

El diccionari s'arma com una taula a on el còdic que s'emet com a eixida, és l'índex i les cadenes que representa són les entrades d'esta taula. Advertixca's que el còdic en sí no s'almagasena en la taula sino que és l'índex de la mateixa per lo que es calcula per la posició en la taula.

L'entrades noves al diccionari

Una atra característica important de l'algoritme és que els còdics en l'eixida es representen per cadenes de bits variables. El diccionari conté inicialment 257 còdics, 256 còdics per als 256 caràcters simples possibles en 8 bits i un còdic que representa el fi d'archiu.

Com les 256 entrades precargadas exigixen 8 bits per a ser referides per l'índex a on es localisen, la següent entrada al diccionari començarà a almagasenar a ficher els índexs en 9 bits (en el còdic pot usar-se per comoditat sancers de 16 o 32 bits), lo que dona per a omplir el diccionari fins a l'entrada 511. En aplegar a la posició 512, es precisarà usar 10 bits, i seguint el mateix esquema en cada potència de 2 (l'entrades realisades es dupliquen), es requerirà 1 bit més.

En la pràctica, es verifica que les primeres entrades, corresponents a còdics de 12 bits de llongitut (4096 entrades) s'omplin ràpidament per lo que és habitual començar el procés no en còdics de 9 bits sino directament en còdics de 12 bits.

Aixina cada volta que es duplica el tamany del diccionari exigix un bit més. No cal emetre un còdic especial d'eixida per a reconéixer la situació, basta simplement considerar-ho en el còdic per a reconéixer el cas, tant en el compressor com en el descompresor, puix van sincronisats sobre la llògica, lo que es coneix en l'argot com lockstep. El modo adequat de reconéixer dita situació és precisament assignar un còdic especial, al començ serà el valor 512, després 1024, 2048, etc. comprovant en cada entrada que quan s'alcança dit valor se suma 1 als bits que es tindran que guardar.

A esta taula se li van agregant successius còdics numèrics per cada nou parell de caràcters consecutius que es lligguen que encara no consten en el diccionari.

És en este detall a on residix la lluentor del método: en armar el diccionari sobre la marcha s'evita fer dos passades sobre el text, una analisant i l'atra codificant i ya que la regla d'armat del diccionari és tan simple, el descompresor pot reconstruir-ho a partir del text comprimit mentres ho llig, evitant aixina la necessitat d'incloure el diccionari dins del ficher comprimit. Es pot objectar que el diccionari contindrà còdics que no s'utilisaran i per tant contribuïx a un tamany gran del mateix, pero l'objectiu és que el ficher comprimit siga chicotet aun cuando els processos de compressió i descompressió pogueren ocupar molta memòria en el diccionari.

Les entrades del diccionari poden representar seqüències de caràcters simples o seqüències de còdics de tal forma que un còdic pot representar dos caràcters o pot representar seqüències d'atres còdics prèviament carregats que a la seua volta representen, cada u d'ells, atres còdics o caràcters simples, o siga que un còdic pot representar des d'un a un número indeterminat de caràcters. En realitat, l'algoritme no discrimina entre còdics i caràcters simples puix el diccionari es carrega inicialment de còdics que representen els primers 256 caràcters simples per lo que estos no són més que atres còdics dins del mateix diccionari.

Tots els caràcters estan inicialment predefinits en el diccionari aixina que sempre hi haurà a lo manco una coincidència, no obstant, lo que es busca és la seqüència més llarga possible. Cada volta que es llig un nou caràcter es revisa el diccionari per a vore si forma part d'alguna entrada prèvia. Quan el caràcter llegit no trobe una seqüència més llarga, llavors s'emet la més llarga que s'haguera trobat i s'agrega al diccionari una entrada formada per qualsevol que haguera segut el còdic previ i este nou còdic. En tant els caràcters successius que es vagen llegint oferixquen més d'una entrada possible en el diccionari, se seguixen llegint caràcters. Quan la cadena només té una entrada en el diccionari, llavors s'emet (guarda, escriu) el còdic corresponent a eixa entrada i s'incorpora al diccionari una nova entrada que representa l'últim còdic emés i el nou.

S'ha comprovat empíricamente que l'informació en un archiu presenta 'regionalidad', o siga, que diferents regions d'un mateix archiu presenten distintes regularitat, la qual cosa fa que el diccionari que s'haguera format per a una regió d'un archiu puga no ser útil en una atra regió distinta.

Que el tamany dels índexs puga ser incrementat de manera variable és una de les contribucions de Welch. Una atra d'elles va ser especificar una estructura de senyes eficient per a guardar el diccionari.

Còdics especials

Com s'ha vingut comentant, el diccionari pot incloure còdics especials que es reserven una posició en el diccionari i que d'incloure'ls, formen part de la inicialización del diccionari (com a entrades 256 i 257).

Tals còdics són el de diccionari ple i el de fi de ficher.

1. Diccionari ple: Indicarà al descompresor que deu fer l'acció que s'espera, típicament borrar i inicializar el diccionari. Com s'ha indicat més dalt, pot optar-se en comprimir per deixar el diccionari fix o alguna atra opció, d'haver vàries opcions, podria seguir-li un atre còdic (que no és interpretable per a descomprimir), referint l'acció a prendre (típicament valors: 0,1,2,3... que identifica l'acció seguida pel compressor).
2. Fi de ficher: Senyala que es va alcançar el final de la descompressió. Si existix contingut darrere no pertany al ficher a descomprimir. Típicament pot ser un comentari que s'acompanya al ficher comprimit.
3. Aumente del tamany del còdic en 1 bit més: Quan les entrades en el diccionari han ocupat totes les posicions que són direccionables en els bits actuals, pot emetre's un còdic especial per a indicar al descompresor que faça lo mateix. Tenint en conte que el descompresor recrea el diccionari en la mateixa mida, l'emissió d'este còdic no és estrictament necessària. Si be és possible elegir escomençar directament en 12 bits o un atre valor que el descompresor no tinga previst, després si un descompresor considera que sempre s'escomença en 9 bits, podria rebre abans que res varis d'estos còdics per a escomençar a usar els bits que el compressor haja estimat com el valor inicial. Aixina mateix este valor inicial de bits podria ser consignat en la capçalera del ficher. Per lo que definitivament no té una utilitat pràctica si en el disseny del sistema s'ha previst la situació.

Compressió

De forma resumida l'algoritme de compressió seguix estos passos:

1. Inicializar el diccionari en totes les entrades prefixades. Bits = 9; EntradasPrefijadas = 257 (256 bytes + 1 còdic especial); LimiteDupSecuencias = 512; index = EntradasPrefijadas
2. Fer: Llegir l'entrada actual.
3. Repetir mentres es localise en el diccionari la seqüència més llarga que ademés continga l'entrada actual.
4. Emetre a l'eixida l'índex de la seqüència més llarga localisada (és la senya a guardar en l'actual tamany de Bits).
5. Afegir al diccionari (en posició index) l'entrada actual apuntant a l'índex de la seqüència guardada. index +=1
6. Si el diccionari està ple, buidar el diccionari i tornar al pas 1.
7. Si l'ocupació del diccionari = LimiteDupSecuencias (duplica el tamany) a partir d'ara els còdics que s'emeten usaran un bit més. Bits +=1; LimiteDupSecuencias *=2
8. Tornar al pas 2 fins a fi de ficher
9. Emetre el còdic especial de fin de ficher.

El diccionari comença inicialment afegint molts còdics, perque les seqüències en eixe punt són curtes, a mida que el diccionari creix, les seqüències van sent cada volta més llargues, lo que implica que el còdic emés està comprimint més bytes (caràcters) que lo que succeïa al començ, si be la cantitat de bits, inclús per a índexs baixos, és major (puix com s'ha indicat anteriorment, es requerix un bit més cada volta que es duplica el tamany ocupat del diccionari).

L'algoritme és tant més eficaç quant més seqüències estiguen parcialment repetides i més llargues siguen. El ràtio de compressió sol descriure una curva a mida que el diccionari creix i mentres es mantinga la regionalidad vigent.

Descompressió

De forma resumida l'algoritme de descompressió seguix estos passos:

1. Inicializar el diccionari en totes les entrades prefixades. Bits = 9; EntradasPrefijadas = 257 (256 bytes + 1 còdic especial); LimiteDupSecuencias = 512; index = EntradasPrefijadas
2. Llegir el còdic actual comprimit (en el tamany de bits actual).
3. Si còdic actual = fi de ficher. Eixir.
4. Fer: mentres (còdic actual > EntradasPrefijadas)
5. Concatenar valor en la posició index del diccionari a la seqüència.
6. còdic actual = el còdic al que apunta el còdic actual en la posició del diccionari
7. Repetir
8. Concatenar valor en la posició index del diccionari a la seqüència.
9. Emetre a l'eixida la seqüència concatenada en orde invers.
10. Afegir al diccionari (en posició index) l'entrada actual apuntant a l'índex de la seqüència guardada. index +=1; Buidar seqüència (la seqüència concatenada).
11. Si el diccionari està ple, buidar el diccionari i tornar al pas 1.
12. Si l'ocupació del diccionari = LimiteDupSecuencias (duplica el tamany) a partir d'ara els còdics que s'emeten usaran un bit més. Bits +=1; LimiteDupSecuencias *=2
13. Tornar al pas 2 fins a fi de ficher

Durant la descompressió, el diccionari és inicializado en totes les seqüències de tamany 1 (byte, caràcter) i és reconstruït a mida que es van descomprimiendo les entrades, lo que fa innecessari tindre que guardar o enviar el diccionari en les senyes comprimides.

El procés de descompressió va llegint de l'entrada un còdic de cada volta, del tamany dels bits que estiguen vigent. Com el diccionari està inicializado, sempre troba el primer i segon còdics, que són usats per a afegir una entrada nova al diccionari. Més alvance les entrades o referixen a còdics precargados o als còdics que s'han anat afegint al diccionari durant la descompressió.