LZSS

L'algorisme de compressió LZ77 pertany a la família de compressors sense pèrdua, també anomenats compressors de text, els quals són així anomenats perquè no ometen ienformació de l'arxiu al comprimir, al contrari que els compressors que utilitzen algorismes del tipus lossy, que ometen una mica d'informació però que disminueixen considerablement la mida del fitxer original, aquest és el cas dels fitxers MP3, MPEG-1, jpeg, etc. Els compressors basats en algorismes sense pèrdua s'utilitzen quan la informació a comprimir és crítica i no es pot perdre informació, per exemple en els arxius executables, taules de bases de dades, o qualsevol tipus d'informació que no admeti pèrdua. El model LZ77 és molt usat perquè és fàcil d'implementar i és força eficient.

En 1977 Abraham L Empel i Jacob Z va presentar el seu model de compressió basat en diccionari, per compressió de text-compressió de text es refereix a compressió sense pèrdua per a qualsevol tipus de dades. Fins ara tots els algorismes de compressió desenvolupats eren bàsicament compressors estàtics. El nou model va ser anomenat LZ77 (per raons òbvies). La sortida consistia sempre en desplaçaments o esllavissades i mides del text, vist anteriorment. També s'incloïa a la sortida el següent byte després d'una coincidència, perquè el context (últims bytes vistos) d'aquest byte és la frase, i si no era part de la frase (la coincidència), després, potser, no s'havia comprimit. Així que, tenint això en compte, per què malbaratar temps tractant de trobar una coincidència (o espai) per a ell?

El 1982 James Storer i Thomas Szymanski basats en el treball de Lempel i Ziv, van presentar el seu model, LZSS. La diferència principal és a la sortida, LZ77 sempre donava un per desplaçament/grandària, fins i tot si la coincidència era d'un sol byte (que feien servir més de vuit bits per representar un byte), de manera que el LZSS fa servir un altre truc per millorar-lo: utilitza banderes (flags), que ocupen un sol bit i informen del que ve després, una literalment o un parell de desplaçament/grandària i aquest algorisme és el que actualment s'utilitza, però el LZSS és comunament anomenat LZ77, així que s'anomenarà LZ77 d'aquest punt en endavant, però és important recordar que també pot ser anomenat LZSS. LZSS també pot utilitzar arbres binaris o arbres de sufixos per fer cerques més eficients.

La teoria és molt simple i intuïtiva. Quan es troba una coincidència (també anomenada frase o conjunt de bytes que ja han estat vistos a l'arxiu d'entrada), en comptes d'escriure aquests bytes s'escriu el desplaçament o mida de la repetició: on és i la seva longitud.

Aquest és un model basat en diccionari, perquè es manté un diccionari (que en aquest cas es coneix com a "Finestra corredissa") i es fa referència a ella amb parells desplaçament/mida. Aquesta versió de LZ77, fa servir una finestra corredissa, la qual té una mida màxima, de manera que la finestra no pot ser l'arxiu complet, en el seu lloc, la finestra corredissa manté els últims bytes "vistos".

Si bé l'algorisme LZ77 treballa en les dades anteriors, l'algorisme LZ78 intenta treballar en les dades futures. Per això, hi ha una exploració en avanç del buffer d'entrada i la congruència contra un diccionari que manté. Es buscarà la memòria intermèdia fins que no pugui trobar un partit en el diccionari. En aquest punt té lloc la sortida de la ubicació de la paraula en el diccionari, si està disponible, la longitud de partit i el caràcter que va causar un error de partit. La paraula resultant s'afegeix al diccionari.

Tot i que inicialment, la popularitat de LZ78 fou després humitejada, possiblement perquè durant les primeres dècades, després de la seva introducció, les parts de LZ78 van ser de patents protegides als Estats Units. La forma més popular de compressió LZ78 va ser l'LZW algorisme, una modificació de l'algorisme LZ78 feta per Terry Welch.

L'usuari ha de suposar que s'està comprimint el text "ab ab", es llegeix fins a "ab" i s'escriu sense comprimir, després es llegeix "ab" i s'escriu el següent: amb el "desplaçament" de 0 es va trobar una coincidència de doble byte repetits.

És bastant simple. Primer es llegeix "ab" i després es copien els bytes d'aquí així:

Obtenir 'a'. "A"
Obtenir 'b'. "Ab"
Obtenir . "Ab"

Obtenir desplaçament/mida. Copia doble byte des de la posició 0. ("Ab")
"Ab ab"

Però, com sap el descompressor si el que llegeix és un parell desplaçament/mida o un byte sense comprimir?. La resposta és simple, es fa servir un prefix, un bit que actua com una bandera, de manera semblant a un interruptor amb dos estats que ens permet saber quin tipus de dades venen a continuació.

Si el prefix és 0, llavors el que ve és un byte sense comprimir. Si, per contra, el prefix és 1, llavors el que segueix a continuació és un parell desplaçament/mida. A aquests prefixos també se'ls anomena "banderes".

El parell desplaçament/grandària és anomenat una paraula clau. Una paraula clau és un grup de bits (o bytes) que contenen alguna classe d'informació utilitzada pel compressor i el descompressor. L'altra sortida possible d'LZ77 és un literal, la qual és simplement un byte sense comprimir, de manera que la sortida de LZ77 pot ser de tres formes:

1. Literals : són simplement bytes sense comprimir.
2. Paraules clau : en aquest cas són parells mida/desplaçament.
3. Banderes : simplement indiquen si les dades que hi ha a continuació són literals o paraules clau.

Ara, com a exemple, s'observa de nou la nostra cadena i una sortida real d'un algorisme LZ77 :

Obtenir 'a'. Sense coincidència. Bandera 0. Literal 'a'.
Obtenir 'b'. Sense coincidència. Bandera 0. Literal 'b'.
Obtenir . Sense coincidència. Bandera 0. Literal .
Obtenir 'a'. Coincidència. Bandera 1. Paraula clau: desplaçament = 0, mida = 2.

Com es pot veure la bandera només té dos estats possibles, de manera que només es necessita un bit per representar-la. Ara no s'hauria de representar les banderes com bytes complets, s'hauria de treballar amb bits. La sortida d'aquesta compressió s'anomena un flux de bits, perquè és un flux de símbols de mida variable, i la unitat mínima és el bit.

Si s'observa l'exemple anterior novament, el que l'usuari s'hauria de preguntar és: On es busquen les coincidències per a una frase? La resposta és buscar cap enrere, en les dades que ja s'han processat. Això és conegut com la finestra corredissa. La finestra corredissa és un buffer que manté els bytes que estan abans de la posició actual al fitxer. Tots els bytes no comprimits de la sortida (les literals) s'afegeixen a la finestra corredissa i també els bytes que formen una coincidència.

En l'exemple novament:

Obtenir 'a'. VC: "". Sense coincidència. Bandera 0. Literal 'a'.

Obtenir 'b'. VC: "a". Sense coincidència. Bandera 0. Literal 'b'.

Obtenir . VC: "ab". Sense coincidència. Bandera 0. Literal .

Obtenir 'a'. VC: "ab". Coincidència. Bandera 1. Paraula clau: desplaçament = 0, mida = 2.

Quan es busquen coincidències, es comparen les dades que hi ha a la finestra corredissa (VC) amb les dades a la posició actual.

Així que hem de mantenir un buffer amb les dades en la posició actual i un buffer amb la finestra corredissa? En algunes implementacions això pot ser veritat, però la implementació que es mostra aquí no és la manera com es fan les coses, perquè tots dos, la finestra corredissa i els bytes en la posició actual, no són més que el fitxer mateix. Només mantenim un buffer, el qual conté a l'arxiu. Després només ens hem de preocupar del punter a la posició actual, i la finestra corredissa aquesta just abans d'aquest punter. De fet es recomana tenir l'arxiu complet (o almenys un bloc gran del mateix) i comprimir, de manera que l'usuari no s'ha de preocupar de llegir més bytes.

Parlem ara sobre la finestra corredissa, quina mida hauria de tenir? Es pot treballar amb l'arxiu complet, però cal pensar en el desplaçament necessari per especificar la posició o la coincidència. Aquest desplaçament no és des de la posició 0 (el principi de l'arxiu) a la coincidència, és des de la posició actual cap enrere. De manera que en l'exemple el desplaçament ha de ser de 3 en comptes de 0 (de manera que, quan es descomprimeix, el descompressor obté un tres i el resta del desplaçament actual). Com és d'esperar, com més gran sigui la mida de la finestra, major nombre de bits caldran per emmagatzemar el punter, de manera que s'ha de triar una mida per a la finestra corredissa. 4K és una mida utilitzada normalment, però se sap que com més gran és la finestra corredera, millor és la compressió. De manera que quan s'implementa es pot triar qualsevol mida i considerar que si, per exemple, s'escull una mida de 8K es necessitaran 13 bits per al desplaçament.

Un altre aspecte que cal triar és la mida de la longitud. Així que, quants bits s'han d'utilitzar per a la longitud? Es poden triar qualsevol mida que es vulgui, però s'ha de considerar d'afinar els bits de la mida de la longitud i els bits del punter de desplaçament es poden millorar la compressió en alguns arxius i empitjorar en altres, així que si es dissenya un compressor per a un únic arxiu, haurien de trobar-se els valors més adients, en cas contrari es faran servir una mida de 0-32, de només 5 bits.

Un altre aspecte important és la longitud mínima d'una coincidència. En aquest cas s'ha escollit utilitzar 13 bits en el desplaçament i 5 a la longitud de la coincidència, 18 bits en total, de manera que una coincidència hauria de ser de, almenys, 3 octets. Perquè si es codifica una coincidència amb dos bytes (16 bits) i es fa servir 18 bits per emmagatzemar la cadena s'utilitzen 2 bits més que si ho es guarda com un literal.

Després s'aixeca una altra pregunta. Si mai es tenen coincidències de 0, 1 o 2 bytes, llavors per què tenim espai per a elles en la longitud? Per treure el major profit possible. La mida encara serà representada amb 5 bits, però el seu rang en comptes de ser 0-32 serà 3-35. Com ho es fa, doncs? Simplement es resta la mida (abans de guardar) 3, i el descompressor ho llegirà i afegirà 3.

Ara que ja se sap com es fa la descompressió, cal notar que el descompressor hauria de saber com acabar o quan parar. Això es pot fer de dues maneres: es té un símbol que marca el final de les dades. Es guarda al costat de la cadena de bits la mida del fitxer d'entrada.

Potser el segon mètode sigui preferible. És una mica més lent, però al mateix temps que es fa servir per conèixer el final dels dades. Pot ser utilitzat en una possible interfície i pot ajudar a evitar alguns problemes. De qualsevol manera, si es vol utilitzar un marcador de fi de dades es poden utilitzar mida zero per a això. La forma en què es fa és la següent: el rang serà de 3-34, en aquest cas s'ha de restar a la mida (quan es guardi) 2. De manera que el rang 1-32 es converteix 3-34, i el compressor només ha d'ocupar d'això en comprimir l'arxiu, un cop la compressió és finalitzada, la sortida desplaçament/grandària té mida de 0. El descompressor ha de llavors verificar cada vegada que llegeix una mida si aquesta mida és 0, per saber si s'ha arribat al final de l'arxiu.

Com es pot veure, els desplaçaments i mides són de longitud variable, i les banderes prenen únicament un bit, de manera que s'hauria de fer servir bits en comptes de bytes. Això és molt important en la majoria dels algorismes de compressió.

La majoria d'operacions treballen amb bytes i quan s'escriu informació a un arxiu la unitat mínima és el byte, llavors, per escriure bits es fa un ús intel·ligent d'algunes instruccions. Per fer això es pot usar llenguatge d'assemblador, o si no, pot ser implementat en C. Es continuen les operacions amb bits a llenguatge d'assemblador. La idea principal és mantenir un byte i un comptador amb els bits escrits, després quan tenim 8 bits, escrivim aquest byte a l'arxiu i comencem de nou amb el següent byte . A continuació es presenta un exemple utilitzant instruccions de llenguatge d'assemblador del microprocessador 8086.

put_bits_loop:
push cx, el nombre de bits a escriure
mov bh, _byte_out, el byte de sortida (on escriure)
mov bl, _byte_in, el byte d'entrada (els bytes a escriure)
mov al, bl, al; emmagatzemem el byte a llegir en l'
shr al, 1; desplacem al a la dreta, first bit in the carry flag
xor ah, ah, ah = 0
aC ah, 0; ah 0 i el ròssec
mov bl, al; guarda el byte d'entrada
mov cl, _total_bits; bits que hem escrit
SHL ah, cl; posa el bit en la seva posició desplaçant a l'esquerra
or bh, al; posa el bit en el byte de sortida
mov _byte_out, bh; guardar
inc _total_bits; bits escrits
cmp _total_bits, 8; Hem d'escriure tot el byte?
JNE no_write_byte; nop E-)
mov di, ptr_buffer, el punter al buffer
mov es: [OT], bh, el byte (s és el segment del buffer)
inc di; byte al buffer
mov ptr_buffer, di; guardat per a la propera vegada
inc bytes_writed, quan el buffer està ple escriure
mov _byte_out, 0; a file or something like that so the next time is clear
no_write_byte:; l'hem guardat
pop cx; ¿més bits per a escriure?
dec cx; sí, repetir tot
jnz put_bits_loop

Es presenta la rutina putbits, els noms de les variables s'expliquen per si sols però encara i tot es presenta aquí una descripció:

• _byte_out : L byte que serà escrit en el buffer de sortida, manté els bits que estem escrivint actualment.
• _byte_in : L byte que conté els bits que volem escriure.
• _total_bits : El nombre de bits que s'han escrit actualment, zero al principi.
• Ptr_buffer : desplaçament de l buffer .

Quan s'ingressa aquesta rutina cx ha de tenir el nombre de bits a escriure, i _bite_in els bits a escriure. Cal tenir cura, després d'ingressar el cicle cal provar si cx és 0 perquè si és zero i no es prova escriurà un bit, després faria cx - 1, el que donaria 255 amb la conseqüència d'escriure 255 bits .

Recordeu:

Test cx, cx
jz put_bits_end

Aquesta és l'estructura (com són escrits els bits) per a un byte :

Bit 8

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Quan s'han escrit tots els bits (la compressió ha finalitzat) s'ha de provar si hi ha encara bits esperant per ser escrits, així que si hi ha alguns (total_bits ! = 0) escrivim _byte_out, i s'incrementen tots els punters de manera que no queden dades sense escriure.

Ara s'ha de definir el format del fitxer de sortida, el qual serà simple, només ha d'omplir les necessitats de l'usuari, les dades comprimides es veuran com:

• Primer una paraula amb la mida del fitxer original i si es vol alguns números com a identificació.
• Després el flux de bits, el qual constitueix i conté les dades comprimits.

Cal recordar com treballa LZ77, un es troba en una posició donada i tracta de trobar cap enrere (perquè s'està segur que el descompressor ja ha descodificat aquests bytes quan un es troba en aquesta posició) una coincidència, bytes que són iguals als bytes en la posició actual, si es troben s'escriu una paraula clau, d'una altra manera s'escriu una literal per poder seguir comprimint.

• Guardar la mida del fitxer a comprimir.
• Repetir fins que no hagin més bytes per comprimir.
• Escanejar el memòria intermèdia d'entrada començant a posición_actual - tamaño_de_ventana_corredissa a l byte actual que estem comparant. (Noteu que el descompressor no es poden copiar bytes d'una posició des d'on les seves bytes no han estat prèviament definits).
• Hem trobat un byte igual a l'actual?
• Cas Sí:
  • Comparem el següent byte des de la posició actual amb l'octet en la posició següent d'on trobem un byte igual al primer.
  • Continuar comparant fins que trobem un byte que no és igual.
  • S'ha trobat un byte que no és igual. És el nombre de bytes més gran que tres?
  • Cas Sí:
    • Escriure el desplaçament del PRIMER byte trobat i el nombre de bytes repetits (mida).
    • Es mou el punter a la posició amb el nombre de bytes repetits (perquè no s'han "salvat") i se segueix buscant.
    • També s'escriu una bandera 1.
  • Cas No:
    • Continua la recerca.
• Cas No:
  • Si no es troba cap coincidència, simplement s'escriu un byte sense comprimir (també s'escriu un literal si no hi ha dades a la finestra corredissa).
  • Cal recordar posar la bandera a 0.

• Es llegeix la mida del fitxer sense comprimir.
• Es repeteix fins que s'ha descomprimit tot el fitxer.
• Es llegeix un bit (la bandera).
• Si és 0 es llegeixen 8 bits, s'escriuen al buffer de sortida (recordar que són un byte descomprimit) i s'incrementa el punter a la sortida.
• Si és 1, es llegeix el desplaçament complet (13 bits), després la mida, copiar "mida" bytes de "desplaçament" a la posició actual, i afegir al punter a la sortida "mida".

La forma en què es busquen les coincidències és la següent: es manté un punter a la posició actual. Al principi de qualsevol iteració, es computa el desplaçament a la finestra corredissa. Això es pot fer fàcilment obtenint el punter a la posició actual i restant-li la mida de la finestra corredissa, en cas que sigui menys que zero (negatiu) simplement s'ajusta a zero. Si es té una finestra corredissa de 4 bytes de llarg (així que la despesa és de dos bits per especificar el desplaçament) i es té la següent cadena: "1.234.567"

Pa: 0. Pvc = 0-4 = 0. Actual: "1234567" Finestra corredissa: "..."
Pa: 1. Pvc = 1-4 = 0. Actual: "234.567" Finestra corredissa: "1"
Pa: 2. Pvc = 2-4 = 0. Actual: "34.567" Finestra corredissa: "12"
Pa: 3. Pvc = 3-4 = 0. Actual: "4.567" Finestra corredissa: "123"
Pa: 4. Pvc = 4-4 = 0. Actual: "567" Finestra corredissa: "1234"
Pa: 5. Pvc = 5-4 = 1. Actual: "67" Finestra corredissa: "2.345"
Pa: 6. Pvc = 6-4 = 2. Actual: "7" Finestra corredissa: "3.456"

On Pa és el punter al byte actual, i Pvc és el punter l'inici de la finestra corredissa. Quan s'usen punters al fitxer d'entrada complet, s'ha de tenir compte amb la mida de la finestra corredissa.

• 7z
• LZW

• LZ77/LZSS and derivatives Arxivat 2004-08-03 a Wayback Machine. (anglès)
• Algorisme de Compressió LZ77 Arxivat 2008-02-09 a Wayback Machine.