LZ78 jest nazwą słownikowej metody bezstratnej kompresji danych. Została opracowana w 1978 roku przez J. Ziva i A. Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. "Compression of individual sequences via variable-rate encoding" (str. 530-536). Kompresja polega na zastępowaniu ciągów symboli indeksami do słownika przechowującego ciągi symboli, które wcześniej wystąpiły w kompresowanych danych. Dzięki temu wielokrotnie powtarzające się ciągi symboli (np. te same słowa w tekście) są zastępowane o wiele krótszymi indeksami (liczbami). Panowie Ziv i Lempel rok wcześniej opracowali metodę LZ77, w której słownik miał stałą wielkość, co powodowało, że jego zawartość zmieniała się cały czas wraz z napływaniem nowych danych. Skutkiem tego, jeśli na wejściu powtórzył się pewien ciąg, który co prawda występował wcześniej, ale w słowniku już go nie było, musiał zostać zapamiętany raz jeszcze. Ogólnie metoda LZ78 jest bardzo zbliżona do LZ77, z tym jednak wyjątkiem, że słownik jest rozszerzany w miarę potrzeb i żaden ciąg występujący w przetwarzanych już danych nie jest "zapominany". Dzięki temu uzyskuje się lepszy współczynnik kompresji kosztem skomplikowania dostępu do słownika. W LZ77 słownik jest zwykłą tablicą, w LZ78 - ze względu na szybkość dostępu do poszczególnych słów - realizowany jest jako drzewo (binarne, trie) albo tablica haszująca. W praktyce najpowszechniej używany jest wariant LZ78 nazywany LZW. Pewną wadą metody jest to, że kod kompresujący i dekompresujący praktycznie nie różnią się pod względem złożoności.
Algorytm:Kompresowany jest ciąg S zawierający n symboli.
1. Wyczyść słownik.
2. i: = 0 (i - indeks pierwszego, nieprzetworzonego symolu w S).
3. Dopóki i < n wykonuj:
  • Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych jeszcze symboli (podciąg S[i...] ).
  • Jeśli udało się znaleźć taki podciąg, to wynikiem wyszukiwania jest jego indeks k w słowniku; dodatkowo słowo wskazywane przez ten indeks ma pewną długość m. Na wyjście wypisz parę (indeks, pierwszy niedopasowany symbol), czyli (k, S[i + m]) oraz dodaj do słownika znaleziony podciąg przedłużony o symbol S[i + m] (innymi słowy podciąg S[i...i+m]). Zwiększ i: = i + m.
  • Jeśli nie udało się znaleźć żadnego podciągu, to znaczy, że w słowniku nie ma jeszcze symbolu S[i]. Wówczas do słownika dodawany jest ten symbol, a na wyjście wypisywana para (0, S[i]). Indeks 0 jest tutaj umowny, w ogólnym przypadku chodzi o jakąś wyróżnioną liczbę. Zwiększ i o jeden.

Source: Wiki