LZ78

LZ78 je slovníková kompresní metoda, kterou v roce 1978 publikovali Abraham Lempel a Ja'akov Ziv. Metoda je nástupcem LZ77, na rozdíl od které ale nemá pohyblivé okno, ale jen vyhledávací okno a slovník. Slovník obsahuje fragmenty nekomprimovaného souboru. Každý řetězec ve slovníku má svůj index (identifikátor). Kompresor hledá ve vyhledávacím okně nejdelší řetězec obsažený ve slovníku. Čte tedy vstupní tok symbol po symbolu až do okamžiku, kdy načte symbol, který způsobí neshodu. Značky produkované touto kompresní metodou mají tvar (index, symbol), kde index je ukazatel na řetězec ve slovníku a symbol je následující symbol, který způsobil neshodu. Každá taková značka udává nový řetězec, který se umístí do slovníku. Slovník je na počátku komprese prázdný. Dekodér buduje svůj slovník ve shodě s kodérem.

Metoda je náročná na paměť, což lze řešit různě. Vhodná datová struktura k udržování slovníku je trie.

Související články

LZ77 - předchůdce LZ78 * LZW - varianta LZ78

Kategorie:Kompresní algoritmy