[[oktatas:programozás:algoritmusok|< Algoritmusok]]

====== LZ78 algoritmus ======

  * **Szerző:** Sallai András
  * Copyright (c) 2014, Sallai András
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]]
  * Web: https://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 =====

<code>
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
</code>

===== 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/lz