< Algoritmusok

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.