< Algoritmusok

LZ78 algoritmus

Szerző: Sallai András

Copyright © Sallai András, 2014

Licenc: GNU Free Documentation License 1.3

Web: http://szit.hu

Terminológia

karakterfolyam - a kódolandó adatsor

karakter - a karakterfolyam egy eleme

prefix - karaktersorozat, amit megelőz egy karakter

string - a prefix és a karaktersorozat amit megelőz

kódszó - alapelem a kódfolyamban; egy string a szótárból

kódfolyam - karakterek és kódszavak sorozata; a kódolási algoritmus kimenete

szótár - stringek táblázata; minden string egy kódszó, amennyiben van indexe a szótárban

aktuális prefix - az aktuális prefix, ahol elkezdjük a kódolást; jele: P

aktuális karakter - adott karakter; rendszerint az a karakter, amit megelőz az aktuális prefix; jele: C

aktuális kódszó - az aktuális kódszó a visszafejtő algoritmusban; jele: W

Kódolás

A kódolás kezdetén a szótár üres.

Az elemzést egy új prefixel kezdjük a karakterfolyamban. Kezdéskor nincs prefix. Ha van egyező string a szótárban (prefix + karakter - P+C), a prefix kiterjeszti a karaktert, C-t. Ezt a kiterjesztést addig ismételjük, amíg nem találunk a szótárban egy nemegyező stringet. Ezen a ponton két dolgot írunk a kimenetre: a kódszó, amit a P prefix reprezentál, és a karaktert, C-t. Hozzáadjuk a P+C stringet a szótárhoz. Ezt követően a folyamat újraindul a következő prefixtől a karakterfolyamban.

A kódoló algoritmus

induláskor a szótár és az s üres
ciklus 0 i .. input_vége
ch <- következő karakter
ha a szótárban van s + ch akkor
s <- s + ch
ellenben
ha s üres akkor
index=0;
szótár.hozzáad(ch)
ellenben
index = szotár.lekerIndex(s)
szótár.hozzáad(s + ch)
s = üres
ha vége
kimenet.hozzáfűz( index + ch + " ")
ha vége
ciklus vége

Példa

A kódolandó karakterfolyam
Pozíció	1	2	3	4	5	6	7	8	9
Karakter	A	B	B	C	B	C	A	B	A
A kódolás folyamat
Lépés	Pozíció	Szótár	Kimenet
1	1	A	0,A
2	2	B	0,B
3	3	B C	2,C
4	5	B C A	3,A
5	8	B A	2,A

Példa 2

Kódszöveg: abgacadabga

Kódszöveg	Könyvtár
Index	Bejegyzés
0, a	1	a
0, b	2	b
0, g	3	g
1, c	4	ac
1, d	5	ad
1, b	6	ab
3, a	7	ga

Segédeszköz

https://szit.hu/lz77