LZ78

Algoritmus LZ78 eliminuje potrebu použitia druhej zložky pri metóde posúvania okien. Tiež používa zakódovaný text ako slovník, ale trocha inou metódou. Veľkosť slovníka pri tomto algoritme môže byť teoreticky neobmedzená, pretože každým krokom algoritmu sa jeho veľkosť zväčší. Maximálny výkon by dosiahol, keby kódovaný text bol nekonečne dlhý. V praxi však veľmi veľký slovník vedie k negatívnej efektívnosti tohto algoritmu. Preto po dosiahnutí určitej veľkosti slovníka sa prestane zväčšovať, prípadne sa môže vynulovať. Namiesto trojíc (tripletov), ktoré používa algoritmus LZ77, LZ78 používa iba dvojice, ktorých postupnosť je výsledkom komprimácie.

Kompresia a dekompresia

Tak, ako to bolo pri LZ77, tak aj tu si priebeh algoritmu vysvetlíme na príklade.

Vytváranie slovníka pri kompresii sa dá rozdeliť na niekoľko krokov. Na začiatku je slovník prázdny, prípadne, ak ho reprezentujeme pomocou -árneho stromu, je tam iba koreň s hodnotou 0. Postup je nasledovn Postup je nasledovný:

• nájdi čo najdlhšiu zhodu v slovníku, ako sa dá. Nech jej dĺžka je , pozícia na ktorej sme v zdrojom reťazci začínali , dĺžka už existujúceho slovníka a pozíciu v slovníku, kde bola nájdená zhoda .
• do slovníka pridaj (teda na pozíciu ) položku , kde je -ty znak v komprimovanom reťazci. Pokiaľ máme slovník reprezentovaný tak ako v tabuľke 3.3, potom do slovníka môžeme pridať aj reťazec, ktorý sme zakódovali. Robí sa to pre lepšiu orientáciu. Pokiaľ je slovník reprezentovaný ako strom, potom hľadanie najdlhšej zhody je iba traverzovanie stromu od koreňa k listom po ohodnotených hranách a pridanie záznamu je iba pridanie jedného syna (prislúchjúca hrana bude mať hodnotu s syn ) pod nájdený uzol (má hodnotu ).
• ako dvojicu na výstup kódera uveď .

Tabuľka 3.3: Príklad kompresie LZ78 algoritmu

Index	Dvojica	Kódovaný reťazec
1
2
3
4
5
6
7
8
9
10
11

Obrázok 3.10: LZ78 graf

Vidíme, že pre prvé tri znaky sa v slovníku postupne nenájde žiadna zhoda, takže výstupom sú trojice , , . Ďalším znakom je , kde je nájdená zhoda v slovníku na treťom mieste, takže sa pridáva ďalší symbol . Pre reťazec už zhoda v slovníku neexistuje a preto je tento reťazec zakódovaný ako dvojica a je pridaný do slovníka. Na vstupnom reťazci sa posunieme o dva symboly doprava. V tomto postupe by sme pokračovali až do konca kódovaného reťazca. V každom kroku veľkosť slovníka narastie o jednu položku a postupnosti znakov, ktoré jednotlivé položky v ňom kódujú, sa stávajú dlhšími. To znamená, že jeho efektivita postupne rastie.

Dekompresia je o niečo jednoduchšia. Tu sa tiež začína s prázdnym slovníkom. To znamená, že slovník pri prenose netreba posielať, pretože sa postupne buduje. Dvojica hovorí, že nebola nájdená žiadna zhoda, dekóduje sa znak a táto dvojica sa pridá do slovníka. Podobný postup platí pre nasledujúce dve dvojice , . Pri dvojici vie, že na výstup má dať text, ktorý je zakódovaný v slovníku na pozícii (tu je pri každej položke vhodné si zapamätať, aký reťazec kódujeme, aby sme nemuseli rekurzívne hľadať v slovníku, prípadne prechádzať strom. Urýchľuje to prácu algoritmu) a na koniec pridať znak a túto dvojicu znova pridať do slovníka.

Záverečné poznámky

Koľko bitov potrebujeme na zakódovanie každej dvojice? Je to na druhý symbol. Počet bitov na prvý symbol závisí od veľkosti slovníka, ktorý, samozrejme, musí byť väčší ako počet rôznych zdrojových symbolov. Na druhej strane, keď je príliš vysoká horná hranica, pri krátkych textoch sa prejaví skôr negatívna kompresia. Ako je vidieť, v prvých krokoch prevláda negatívna kompresia a účinnosť tohto algoritmu sa prejavuje až po niekoľkých desiatkach krokov.