Tartalomjegyzék

< Algoritmusok

LZW

Az LZW kódolásról

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.

Működés

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)

Példa

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

Java megvalósítás

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.