LZ78

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

LZ78 je slovníková kompresní metoda, kterou v roce 1978 publikovali Abraham Lempel a Jacob 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[editovat | editovat zdroj]

  • LZ77 – předchůdce LZ78
  • LZW – varianta LZ78