Codificação por dicionário

Referência padrões repetidos usando deslocamento e comprimento.

Janela deslizante

Mantém uma janela móvel para encontrar o maior padrão correspondente.

Algoritmo base

Fundamento de ZIP, GZIP, DEFLATE e PNG.

Como o LZ77 funciona

LZ77 mantém uma janela deslizante de dados vistos recentemente. Para cada posição, o algoritmo procura dentro da janela a maior substring que coincide. Se encontrar, emite uma referência (deslocamento, comprimento, próximo caractere). Caso contrário, emite um literal (0,0,caractere). Assim, padrões repetidos são substituídos por referências curtas, proporcionando compressão sem perdas.

Exemplo de 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,)