LZ77

Lempel-Ziv 77, skracane zwykle do LZ77 (algorytm LZ77) – metoda strumieniowej słownikowej kompresji danych. Metoda LZ77 wykorzystuje fakt, że w danych powtarzają się ciągi bajtów (np. w tekstach naturalnych będą to słowa, frazy lub całe zdania) – kompresja polega na zastępowaniu powtórzonych ciągów o wiele krótszymi liczbami wskazującymi, kiedy wcześniej wystąpił ciąg i z ilu bajtów się składał; z punktu widzenia człowieka jest to informacja postaci „taki sam ciąg o długości 15 znaków wystąpił 213 znaków wcześniej”.

Algorytm LZ77 jest wolny od wszelkich patentów, co w dużej mierze przyczyniło się do jego popularności i szerokiego rozpowszechnienia. Doczekał się wielu ulepszeń i modyfikacji, dających lepsze współczynniki kompresji albo dużą szybkość działania. Na LZ77 opiera się m.in. algorytm deflate, używany jest również w formatach ZIP, gzip, ARJ, RAR, PKZIP, a także PNG.

Algorytm został opracowany w 1977 przez Abrahama Lempela i Ja’akowa Ziwa i opisany w artykule A universal algorithm for sequential data compression opublikowanym w IEEE Transactions on Information Theory (s. 8–19)^[1]. Rok później autorzy opublikowali ulepszoną wersję metody, znaną pod nazwą LZ78.

Organizacja IEEE uznała algorytm Lempel-Ziv za kamień milowy w rozwoju elektroniki i informatyki^[2].