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