A betűnkénti kódolás hatékonysága korlátozott, könnyen találhatunk olyan adatot, amit sokkal tömörebb formában lehet reprezentálni, ha a kódolás nem karakterenként történik. Ezt használják ki a szótárkódok úgy, hogy egy kódszó nem csak egy karakter képe lehet, hanem egy szóé is. Az algoritmus a szöveg bizonyos szavaiból szótárat épít.

LZW tulajdonságai:

A szótárról három dolgot feltételezünk. A bemeneti abc minden betűje szerepel benne. Ha egy szó benne van a szótárban, akkor annak minden kezdődarabja is benne van. A tárolt szavaknak fix hosszúságú kódjuk van.

A tömörítendő szöveget a szótárbeli szavak egymásutánjára bontjuk. Az eredeti szöveg olvasásakor egyidőben épül a szótár és alakul ki a felbontás. Az LZW csak egyszer dolgozza fel az inputot.

Kódolás működése:

Az LZW kódolás egy kezdeti kódtáblát bővít lépésről-lépésre úgy, hogy egyre hosszabb már látott szavakhoz rendel új kódszót. A kezdeti kódtábla a bemeneti abc minden betűjét tartalmazza.

Az algoritmus karakterről karakterre halad végig a szövegen. Beolvas egy karaktert. Ezt hozzá vesszük az eddig beolvasott szavunkhoz. Ha a szavunkkal és az imént beolvasott karakterrel kapott új szó benne van a szótárban, beolvasunk még egy betűt. Ha nincs benne belerakjuk a szótárba és a szavunk most a legutoljára beolvasott karakter lesz önmagában.

Példa:

Legyen a tömörítendő szöveg: $ABABABAAC$. A kezdeti kódtábla (a szöveg karakterei alapján):

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$

Beolvasunk egy karaktert, ez az $A$. Ez már szerepel a kódtáblában, ezért beolvasunk még egyet, így a beolvasott szavunk az $AB$. Ez már nem szerepel a kódtáblában, ezért hozzávesszük és közben a tömörítendő szövegben jelöljük a leghosszabb olyan részt, ami szerepelt a kódtáblában, ez az $A$ volt. Ezek alapján a tömörítendő szöveg: $A|BABABAAC$, a kódtábla pedig a következő:

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$

Az eddig beolvasott szavunk most a $B$. A $B$ szerepel a kódtáblában, ezért olvasunk tovább. $BA$ nem szerepel a kódtáblában. ($A|B|ABABAAC$)

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$

Az eddig beolvasott szavunk, most az $A$. $A$ szerepel a kódtáblában, $AB$ is, $ABA$ még nem szerepel a kódtáblában. ($A|B|AB|ABAAC$)

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$
$ABA$	$6$

Az eddig beolvasott szavunk, most az $A$. $A$ szerepel a kódtáblában, $AB$ is, $ABA$ is, $ABAA$ még nem szerepel a kódtáblában. ($A|B|AB|ABA|AC$)

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$
$ABA$	$6$
$ABAA$	$7$

Az eddig beolvasott szavunk, most az $A$. $A$ szerepel a kódtáblában, $AC$ viszont nem, ezért hozzávesszük. Ezek alapján a tömörítendő szöveget, így tudtuk felbontani: $A|B|AB|ABA|A|C$. A tömörített szöveg a következő lesz: $1|2|4|6|1|3$.

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$
$ABA$	$6$
$ABAA$	$7$
$AC$	$8$

Az eredeti LZW-nél előre meghatározzuk, hogy a kódszavak hány bitesek, pl. $12$. Így persze a tömörítés során elfogyhatnak a lehetséges kódok. Ha pl. $12$ bitesek a kódok, akkor a legnagyobb lehetséges kód a $2^{12}-1=4095$. A legegyszerűbb, ha ilyenkor nem bővítjük tovább a szótárat, de vannak más módszerek is.

Mivel a Huffman-kódolás csak a betűnkénti kódolások között optimális az LZW eljárás könnyen eredményezhet rövidebb kódot. Az LZW eljárás egyszerűnek nevezhető összehasonlítva például a Huffman kódolással, mivel csak egyszer kell olvasni a bemenetet. Hatékony is amennyiben a kódszavak tárolása hatékony.

Dekódolás működése:

A dekódoláshoz ugyanazt a kezdeti kódtáblát használjuk, amelyben a bemeneti abc minden betűje benne van.

Példa:

Kezdetben ismerjük a kódolt szöveget, $124613$, és a kezdeti kódtáblát.

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$

A kódolt szövegünk elejét könnyedén vissza tudjuk fejteni a kódtábla alapján.

1	2	4	6	1	3
$A$

Vegyük a második kódot. A második kódot is könnyen dekódolni tudjuk.

1	2	4	6	1	3
$A$	$B$

Az első dekódolás kivételével minden lépésben frissíteni kell a kódtáblát. Ehhez vegyük az első dekódolt szót és a második dekódolt szó első karakterét és ezzel kell frissítenünk a kódtáblát. Ez jelen esetben az $AB$.

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$

Vegyük a harmadik kódot. Ezt is könnyen tudjuk dekódolni a frissített kódtáblával. Most is frissíteni kell a kódtáblát. Vegyük a második dekódolt szót és a harmadik dekódolt szó első karakterét és ezzel frissítsük a kódtáblát. Ez jelen esetben a $BA$.

1	2	4	6	1	3
$A$	$B$	$AB$

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$

Most egy olyan esethez értünk, amikor nem ismerjük a kódhoz tartozó szót. Ilyenkor vegyük az előző szót ($AB$) és konkatenáljuk hozzá az első karakterét, tehát az így kapott szó ($ABA$) lesz a kódhoz tartozó szó. Ez azért van így, mert ha fordítva gondolkozunk és kódolni szeretnénk az eddigi szöveget, akkor pont $ABA$ kerülne a kódtáblába.

1	2	4	6	1	3
$A$	$B$	$AB$	$ABA$

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$
$ABA$	$6$

Innen már gyorsan megkaphatjuk az eredeti szöveget, de közben frissíteni kell a kódtáblát is.

1	2	4	6	1	3
$A$	$B$	$AB$	$ABA$	$A$

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$
$ABA$	$6$
$ABAA$	$7$

1	2	4	6	1	3
$A$	$B$	$AB$	$ABA$	$A$	$C$

Szó	Kód
$A$	$1$
$B$	$2$
$C$	$3$
$AB$	$4$
$BA$	$5$
$ABA$	$6$
$ABAA$	$7$
$AC$	$8$

A gyakorlatban a kódszavak halmazát a fix kódhossz miatt korlátozzuk.

Gyakorlati alkalmazása:

LZW tömörítést alkalmaznak például a GIF-ek tömörítésénél, és opcionálisan a PDF és TIFF formátumú fájlok tömörítésénél is.