Словарное кодирование

Использует ссылки по смещению и длине для повторяющихся шаблонов.

Скользящее окно

Поддерживает подвижное окно поиска наиболее длинных совпадений.

Базовый алгоритм

Лежит в основе ZIP, GZIP, DEFLATE и PNG.

Как работает LZ77

LZ77 поддерживает скользящее окно из недавно просмотренных данных. Для каждой позиции алгоритм ищет в окне самую длинную совпадающую подстроку. Если совпадение найдено, выводится ссылка (смещение, длина, следующий символ). Если нет — выводится литерал (0,0,символ). Так повторяющиеся участки заменяются короткими ссылками, обеспечивая без потерь сжатие.

Пример LZ77

Text: "ABCABCABC"
Window=4, Lookahead=4

Position 0: 'A' - no match
  → (0,0,A)

Position 1: 'B' - no match
  → (0,0,B)

Position 2: 'C' - no match
  → (0,0,C)

Position 3: 'ABC' - matches at offset 3
  → (3,3,A)

Position 7: 'BC' - matches at offset 3
  → (3,2,)

Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)