Hogyan működik az LZW tömörítési algoritmus

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ő:

• ByteOlvas(Sztring)
• Ciklus amíg nem filevége
• ByteOlvas(Karakter)
• Ha (Sztring+Karakter) benne van a táblában akkor
• Sztring:=Sztring+Karakter
• különben
• Kiír(Sztring)
• TáblaHozzáad(Sztring+Karakter)
• Sztring:=Karakter
• Elágazás vége
• Ciklus vége
• Kiír(Sztring)

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.

példa: ABACABAD tömörítése:

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

LZW-Compress algoritmus

• Eljárás LZW_C
• string:= olvass_1_karaktert
• Ciklus amíg_van_input_karakter
• ch:= olvass_1_karaktert
• Ha string+ch benne_van_a_kódtáblában
• Akkor string:= string+ch
• Különben
• írd_ki_a string kódját
• Add_hozzá_a string+ch a_kódtáblához_új_kóddal
• string:= ch
• Elágazás vége
• Ciklus vége
• írd_ki_a string kódját
• Eljárás vége
•  

LZW-Decompress algoritmus

• Eljárás LZW_D
• Olvass régikód
• írd_ki régikód
• Ciklus amíg_van_input
• Olvass újkód
• string:= értelmezd_az újkódot
• írd_ki string
• ch:= string elsô_karaktere
• Add_hozzá_a régikód+ch a_kódtáblához
• régikód:= újkód
• Ciklus vége
• Eljárás vége

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.