Demo do compressor LZ77

The LZ77 compression algorithm eliminates structural redundancy by substituting repeating data sequences with relative mathematical pointers. Utilizing a sliding operational window, it encodes data as length-distance pairs referencing previously processed buffers. This deterministic referencing dictates the foundation of DEFLATE protocols. The algorithm relies strictly on the statistical probability of repetitive strings, maximizing entropy reduction without fundamentally altering the original mathematical information.

Quando o algoritmo encontra texto que já leu, não volta a escrevê-lo letra por letra — anota algo curto como «volte offset caracteres e copie length deles». Aqui cada token é (offset, length, literal): uma referência anterior mais um caractere novo. Na prática, um texto cheio de palavras ou padrões repetidos encolhe bastante, enquanto dados já aleatórios quase não comprimem.

Uma correspondência pode apontar apenas um caractere para trás e ainda assim copiar mais caracteres do que existem ali. Com offset 1, o decodificador copia cada byte no exato instante em que o escreve, de modo que um único token como (1, 5, ...) desdobra aaaaaa a partir de um só a. Assim a clássica codificação run-length (RLE) surge de graça no LZ77 — a «cópia» se sobrepõe a texto ainda em produção. Experimente o exemplo repetitivo para ver uma região de correspondência estender-se além da posição atual.