LZ77 kokkupakkimise demo

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.

Kui algoritm näeb teksti, mille on juba lugenud, ei kirjuta ta seda uuesti tähthaaval välja — ta märgib lühidalt: „mine offset märki tagasi ja kopeeri neist length." Iga token on siin (offset, length, literal): tagasiviide pluss üks uus märk. Praktikas kahaneb korduvate sõnade või mustritega tekst tugevalt, samas kui juba juhuslikud andmed peaaegu ei tihene.

Vaste võib osutada vaid ühe märgi taha ja ikkagi kopeerida rohkem märke, kui neid sinna veel jõudnud on. offset 1 korral kopeerib dekooder iga baidi kohe, kui selle kirjutab, nii et üksainus token nagu (1, 5, ...) avab ühest a-st sõna aaaaaa. Nõnda tuleneb klassikaline seeriapikkuse kodeerimine (RLE) LZ77-st tasuta — „koopia" kattub tekstiga, mida alles luuakse. Proovi korduvat näidet, et näha, kuidas vastepiirkond ulatub praegusest positsioonist kaugemale.