Az LZ77, majd az LZ78 továbbfejlesztett verziója. Abraham Lempel, Jacob Ziv és Terry Welch munkája. 1984-ben publikálta Terry Welch.
A Unix compress parancsa ezzel az algoritmussal tömörít, de használjuk a GIF képekben is.
Szemben az LZ78 kódolással, az LZW kódoló szótára induláskor nem üres. Tartalmaz minden egyedi karaktert, ami a kódolandó szövegben megtalálható. Ugyanakkor a kibontáshoz nem szükséges tárolni a szótárt, mert az újból felépíthető a kód alapján. Az alapszótár, azonban egységes kell legyen a kibontás és tömörítés során egyaránt. Mivel minden karakter benne van kezdéskor a szótárban, ezért a kódolás minden lépése egy prefix karakterrel történik. Így az első keresés után két karakterünk van.
Induláskor, a könyvtár tartalmaz minden lehetséges karaktert, az S pedig üres.
s <- üres ciklus amíg van adat ch <- adat[következő] ha szotar.tartalmazza(s + ch) akkor s <- s + ch ellenben kimenet.hozzáfűz(lekerIndex(s)) szotar.hozzáfűz(s + ch) s <- ch ha vége ciklus vége kimenet.hozzáfűz(lekerIndex(s)
| A kódolandó karakterfolyam | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Pozíció | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Karakter | A | B | B | A | B | A | B | A | C |
| Kezdőszótár |
|---|
| (1) A |
| (2) B |
| (3) C |
| A kódolás folyamat | |||
|---|---|---|---|
| Lépés | Pozíció | Szótár | Kimenet |
| 1 | 1 | (4) A B | 1 |
| 2 | 2 | (5) B B | 2 |
| 3 | 3 | (6) B A | 2 |
| 4 | 4 | (7) A B A | 4 |
| 5 | 5 | (8) A B A C | 7 |
| 6 | – | – | 3 |
static String lzwCompress(String text, ArrayList<String> dic) { StringBuilder output= new StringBuilder(); String s = ""; for(int i= 0; i<text.length(); i++) { Character ch = text.charAt(i); if( dic.contains(s+ch.toString())) { s = s + ch.toString(); }else { output.append(dic.indexOf(s) + " "); dic.add(s + ch.toString()); s = ch.toString(); } } output.append(dic.indexOf(s)); return output.toString(); }
A metódust meglehet úgy is írni, hogy egy byte összes variációja eleve szerepel a szótárban, ekkor nem szükséges második paraméter.