LZW

Szerző: Sallai András
Copyright © 2014, Sallai András
Licenc: CC BY-SA 4.0
Web: https://szit.hu

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.