Tartalomjegyzék

< Algoritmusok

LZ78 algoritmus

Terminológia

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