Egy kis történelem:

A tömörítôcsalád alkotóiról (Abraham Lempel és Jakob Ziv) kapta nevét, akik 1977-ben jelentették meg az alapalgoritmust (1977-et jelent a névben szereplô 77-es szám). Az LZ77 alapú tömörítôk letárolják az n db utolsó byte-ot, és amikor egy olyan byte-csoportot találnak, mely szerepel ebben a pufferben, akkor a byte-csoport helyett annak a pufferben lévô helyét és hosszát tárolják le. Az algoritmust sokan módosították, javították a jobb tömörítés érdekében, ezek közül a legismertebb megvalósítás James Storer és Thomas Szymanski nevéhez fûzôdik, ezt a tömörítést fogom most bemutatni.

Az LZ betûpár a névben a Lempel-Ziv párosra, az SS betûpár pedig a Storer-Szymanski párosra vonatkozik. Ez az algoritmus a "visszanézô" puffer (az utóbb letömörített n db byte-ot tartalmazza) mellett még egy "elôrenézô" puffert is alkalmaz, melybe a letömörítendô byte-ok kerülnek. Az algoritmus megkeresi a letömörítendô byte-ok és a "visszanézô" puffer leghosszabb egyezését, s ha annak hossza meghaladja a minimálisnak definiált, általában 3 byte-ot, akkor egy pozíció, hossz párt tárol le. Megoldandó probléma még, hogy ennyibôl a kitömörítô még nem tudná megállapítani, hogy a következô kód egy egyszerû byte-e, vagy pedig egy pozíció, hossz páros. Ezt az RLE-nél alkalmazott, az elôzôekben leírt, módszerekkel is megvalósíthatnánk, azonban a tapasztalat szerint egyszerûbb és jobb, ha minden kód elé egy plusz bitet írunk ki, mely azt jelzi, hogy a soron következô adat byte, vagy visszautaló kódpár. (A gyakorlatban ezeket a biteket 8-asával tárolják a könnyebb kezelhetôség érdekében, azonban ez a lényegen nem változtat. ) Az algoritmus vázlata a következô:

Az algoritmus több ötlettel is javítható, gyorsítható, pl. javulhat a tömörítés aránya, ha a következô pozícióra is megvizsgáljuk az egyezést, gyorsul a tömörítés, ha keresés során ún. HASH táblát alkalmazunk, stb. Mivel az algoritmus könnyen megvalósítható és jól tömörít, így gyorsan elterjedt.

Az család alapját képezô LZ78 algoritmust - mint az LZ77-et -, szintén a Lempel-Ziv páros publikálta (1978-ban). Az algoritmus alapja, hogy egy táblát épít fel folyamatosan, melybe mindig belehelyezi az aktuális byte-csoportokat. Ha egy olyan byte-csoportot talál, mely már szerepel a sztringtáblában, akkor a táblában elfoglalt helye kerül letárolásra. Az ezen alapuló algoritmusok csak a tábla kezelésében és tárolásában különböznek. A legismertebb változat az LZW algoritmus, melyrôl a következôkben fogok írni.

Az LZW az LZ78 finomított változata. Terry Welch publikálta 1984-ben, a W betû az ô nevére utal az elnevezésben. Az LZW algoritmus is széleskörûen elterjedt, legismertebb megvalósítása a fôleg UNIX rendszereken elterjedt COMPRESS program. Az LZW alapja azonos az LZ78-al. A kiírásra kerülô kódok általában 12 bitesek, így a sztringtáblába 4096 bejegyzés fér. Az elsô 256 bejegyzésbe elôzôleg az egyszerû ASCII karakterek, 256-tól 4095-ig pedig a tömörítés során a byte-csoportok kerülnek. Az algoritmus elônye, hogy ezt a táblát nem kell letárolni, ugyanis kitömörítés közben minden további nélkül felépíthetô. Az LZW a tábla tárolásában hozott forradalmi újítást, ugyanis az LZW táblájába nem az egész byte-csoport kerül bele, hanem csak a byte-csoport elsô byte-ja, majd egy, már a táblában szereplô byte-csoport indexe (a byte-csoport ebbôl a láncolatból könnyen felépíthetô). Az algoritmus a következô:

Az algoritmus megvalósításakor a sztringtábla méretének (bitek száma) kiválasztása jelenthet problémát és annak meghatározása, hogy mi történjen, ha megtelik a sztringtábla. A két variáció (melyek ötvözhetôek): vagy a bitek számát kell növelni ilyenkor, vagy törölni kell a táblát.

1.) az egybetûs szimbólumokhoz kódot rendelünk: A #0, B #1, C #2, D #3
2.) AB #4, BA #5, AC #6, CA #7, ABA #8, AD #9;

a kimeneten: #0, #1, #0, #2, #4, #0, #3

Az LZW veszteségmentes (lossless) tömörítés. Ha radikális fájlméretcsökkenést észlelsz, az azért van, mert a képed nagy összefüggô azonos színû foltokból áll (sok ismétlôdô pixel egymás után). Pl. egy 2000x2000 pixeles fehér felületet pár k-ban tárol, mert csak annyit ír le, hogy van 4millió fehér pixeled. Gyakran jobb eredményt ad, mint a jpeg, és veszteség nélkül. Fotóknál nem olyan hatékony, ha a felére összenyomja a képet, az már elég jó, viszont lassan írja és lassan olvassa a Photoshop (nyers szkennelés elmentésére hasznos, mert az árnyalatok korrekciója elôtt nem szabad veszteséges - lossy - tömörítést használni, mert késôbb a kontraszt növelésével vagy egy sharpen filterrel a jpeg kis hibái is óriásira nôhetnek). Szkennelt logóknál, 1 bites grafikáknál viszont remek az LZW. Készre korrigált , végleges fotók archiválására viszont már jó a jpeg, ha legalább 8-9-es minôségi faktort használsz - az egyes csatornákon látható a tömörítés (RGB-ben a kék, CMYK-ban a sárga csatornán), de a kompozit képen már emberi szem nem látja meg a hibát.