LZSS

De Viquipèdia
Dreceres ràpides: navegació, cerca

L'algorisme de compressió LZ77 pertany a la família de compressors sense pèrdua, també anomenats compressors de text, als quals se'ls diu així perquè no ometen Informació 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, el qual és el cas dels fitxers MP3, MPG, 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 19 77 Abraham L Empel i Jacob Z iv 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, Perquè 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, encara 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 desplaçament/grandària i aquest algorisme és el que actualment fem servir, però el LZSS és comunament anomenat LZ77, així que l'anomenarem 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 "Finestra corredissa") i es fa referència a ella amb parells desplaçament/mida. Aquesta versió de LZ77, fa servir una finestra corredera, 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".

LZ78[modifica | modifica el codi]

Si bé l'algorisme LZ77 treballa en les dades anteriors, l'algorisme LZ78 intents de treballar en les dades futurs. Per això, l'exploració en avanç del buffer d'entrada i la congruència contra un diccionari que manté. Es buscarà al memòria intermèdia fins que no pot trobar un partit en el diccionari. En aquest punt és 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 popular, la popularitat de LZ78 després humitejat, possiblement perquè durant les primeres dècades després de la seva introducció, les parts de LZ78 van ser de patents protegits als Estats Units. La forma més popular de compressió LZ78 va ser el LZW algorisme, una modificació de l'algorisme LZ78 feta per Terry Welch.

Comprimint[modifica | modifica el codi]

Imaginem que estem comprimint el text "ab ab", llegim fins a "ab" i ho escrivim sense comprimir, després llegim "ab" i escrivim el següent: amb el "desplaçament" de 0 es va trobar una coincidència de doble byte repetits.

Decomprimint[modifica | modifica el codi]

És bastant simple. Primer llegim "ab" i després copiem 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"

Com funciona?[modifica | modifica el codi]

Però, com sap el descompressor si el que llegeix és un parell desplaçament/mida o un byte sense comprimir?. La resposta és simple, fem 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 vénen 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 el nostre cas són parells mida/desplaçament.
  3. Banderes : simplement ens indiquen si les dades que hi ha a continuació són literals o paraules clau.

Ara, com a exemple, veiem 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 necessitem un bit per representar-la. Ara no hauríem de representar l'banderes com bytes complets, hauríem 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.

Finestra corredissa[modifica | modifica el codi]

Si s'observa l'exemple anterior novament que hauríeu de preguntar: On busquem les coincidències per a una frase? La resposta és buscar cap enrere, en les dades que ja hem 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é al 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 no ens preocupem de llegir més bytes.

Parlem ara sobre la finestra corredissa, quina mida hauria de tenir? Podríem treballar amb l'arxiu complet, però hem de 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 lloc 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 necessitarem per emmagatzemar el punter, de manera que hem de triar una mida per la finestra corredissa. 4K és una mida utilitzat 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, escollim una mida de 8K necessitarem 13 bits per al desplaçament.

Mides[modifica | modifica el codi]

Un altre aspecte que hem de triar és el mida de la longitud. Així que, quants bits utilitzem per la longitud? Podem triar qualsevol mida que desitgem, però hem de considerar d'afinar els bits de la mida de la longitud i els bits del punter de desplaçament podem millorar la compressió en alguns arxius i empitjorar en altres, així que si estem dissenyant un compressor per a un únic arxiu, haurien de trobar-se els valors més adients, en cas contrari farem 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 el nostre cas hem 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 s'usa 18 bits per emmagatzemar la cadena s'utilitzen 2 bits més que si ho guardem com un literal.

Després s'aixeca una altra pregunta. Si mai tindrem 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. El nostre mida encara serà representat amb 5 bits, però el seu rang en lloc de ser 0-32 serà 3-35. Com ho fem? Simplement restem a la mida (abans de guardar) 3, i el descompressor ho llegirà i afegirà 3.

Marcador de Cap[modifica | modifica el codi]

Ara que sabem com es fa la descompressió hem de 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-nos a evitar alguns problemes. De qualsevol manera, si es vol utilitzar un marcador de fi de dades podríem 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 hem de restar a la mida (quan el guardem) 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 del arxiu.

Treballar amb bits[modifica | modifica el codi]

Com es pot veure, els desplaçaments i mides són de longitud variable, i les banderes prenen únicament un bit, de manera que hauríem de fer servir bits en lloc 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 fem un ús intel·ligent d'algunes instruccions .

Per fer això es pot usar llenguatge d'assemblador, o si no, pot ser implementat en C. Continuarem 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 de 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 presentem 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 a ser escrits, així que si hi ha alguns ( total_bits ! = 0) escrivim _byte_out, i incrementem tots els punters de manera que no deixem dades sense escriure.

Arxiu de Sortida[modifica | modifica el codi]

Ara hem de definir el format del fitxer de sortida, el qual serà simple, només ha d'omplir les nostres necessitats, les dades comprimits 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.

Pseudo Codi[modifica | modifica el codi]

Recordem com treballa LZ77, un es troba en una posició donada i tracta de trobar cap enrere (perquè s'està segur que el descompressor ja ja 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.

Seqüència bàsica: Compressor[modifica | modifica el codi]

  • 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 Si:
    • Comparem el següent byte des de la posició actual amb el 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 Si:
      • Escriure el desplaçament del PRIMER byte trobat i el nombre de bytes repetits (mida).
      • Movem el punter a la posició amb el nombre de bytes repetits (perquè no els hem "salvat") i seguim 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.

Seqüència bàsica: Descompressor[modifica | modifica el codi]

  • 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".

Cercant coincidències[modifica | modifica el codi]

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 gasten dos bits per especificar el desplaçament) i tenim 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, hem de cuidar la mida de la finestra corredissa.

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]