Lempel-Ziv 77, skracane zwykle do LZ77 (algorytm LZ77), to metoda strumieniowej bezstratnej kompresji słownikowej. Zostala opracowana w 1977 roku przez Abrahama Lempela i Jacoba Ziv i opisana w arykule "A universal algorithm for sequentaial data compression" opublikowanym w IEEE Transactions on Information Theory (str. 8-19). Obrazowo patrząc, wykorzystuje ona fakt, iż poszczególne słowa, albo przynajmniej ich części powtarzają się w danym tekście. Na LZ77 opiera się m.in. algorytm deflate. Poza tym LZ77 jest wolny od wszelkich patentów co także w dużej mierze przyczyniło się do jego popularności i szerokiego rozpowszechnienia.
Algorytm: Metoda LZ77 korzysta z bufora, który logicznie podzielony jest na dwie części:
  • bufor słownikowy (słownik), przechowujący k ostatnio przetwarzanych symboli;
  • bufor wejściowy, przechowujący n symboli do zakodowania.
Bufor słownikowy obejmuje indeksy 0...k-1, bufor wejściowy k...k+n-1. Rozmiary n i k są dobierane tak, aby były całkowitymi potęgami dwójki. Rozmiar bufora słownikowego wynosi w praktyce kilka-kilkadziesiąt kilobajtów, słownik wejściowy jest dużo mniejszy. Algorytm przebiega następująco:
  • Bufor słownikowy jest wypełniany pierwszym symbolem wejściowym i ten symbol jest zapisywany na wyjście.
  • Do bufora wejściowego wstawiane jest n pierwszych symboli wejściowych.
  • Dopóki w buforze wejściowym są jakieś dane:
    1. W obrębie bufora słownikowego wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego. Wynikiem wyszukiwania jest indeks początku wyszukanego podciągu oraz jego długość C, ograniczona z góry przez n − 1. Część podciągu może być wspólna z buforem wejściowym! Jeśli podciągu nie uda się znaleźć, to P może mieć dowolną wartość, natomiast C = 0.
    2. Na wyjście wyprowadzana jest trójka (P, C, symbol S z bufora wejściowego następujący po dopasowanym podciągu).
    3. Cały bufor przesuwany jest w lewo o C + 1 pozycji i na koniec bufora dopisywane jest tyleż kolejnych symboli wejściowych (o ile jeszcze są jakieś).

Wadą metody jest ciągle zmieniający się słownik - jeśli kodowanych danych jest więcej niż może pomieścić bufor (a tak na ogół jest), to przy przesuwaniu bufora (punkt 3. algorytmu) dane ze słownika są bezpowrotnie tracone, więc nie będą mogły zostać ponownie użyte. (Metoda LZ78 i pochodne powiększają słownik w miarę napływania danych). Zatem stopień kompresji LZ77 w dużej mierze zależy od długości słownika, prędkość kompresji natomiast jest uzależniona głównie od efektywności procedury wyszukującej najdłuższy wspólny podciąg. Współczynnik kompresji danych tekstowych dla algorytmu LZ77 mieści się w granicach 40-50%
Source: Wiki