> lz77 | sliding | window <
// LZ77 – komprimering med glidende vindu og ordbokreferanser
Ordbokkoding
Bruker referanser med forskyvning og lengde for gjentatte mønstre.
Glidende vindu
Holder et bevegelig vindu for å finne lengste treff.
Grunnalgoritme
Danner grunnlaget for ZIP, GZIP, DEFLATE og PNG.
>> teknisk info
Hvordan LZ77 fungerer:
LZ77 holder et glidende vindu over nylig sett data. For hver posisjon søker algoritmen i vinduet etter den lengste matchende delstrengen. Når den finner en, skriver den ut en referanse (forskyvning, lengde, neste tegn). Hvis det ikke finnes noen match, skriver den et bokstavelig tegn (0,0,tegn). Dette erstatter repeterte mønstre med korte referanser og gir tapsfri komprimering.
LZ77-eksempel:
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,)
Hvorfor bruke LZ77?:
- ▸Tapsfri komprimering
- ▸Krever ingen forhåndskunnskap om formatet
- ▸Tilpasser seg mønstrene i dataene
- ▸Relativt enkel implementasjon
- ▸Grunnlag for mange moderne komprimeringsalgoritmer
>> ofte stilte spørsmål
Hva er LZ77?
LZ77 er en universell tapsfri datakomprimeringsalgoritme publisert av Abraham Lempel og Jacob Ziv i 1977. Den erstatter gjentatte forekomster i datastrømmen med referanser til en tidligere kopi i den ukomprimerte strømmen.
Hvordan fungerer det glidende vinduet?
Det glidende vinduet består av en søkebuffer (allerede prosesserte data) og en lookahead-buffer (data som skal komprimeres). Algoritmen søker i søkebufferen etter den lengste matchen med starten av lookahead-bufferen, og skriver deretter ut en referanse eller et bokstavelig tegn.
LZ77 vs moderne komprimering?
LZ77 er fundamentet for mange moderne komprimeringsmetoder. DEFLATE, brukt i ZIP og GZIP, kombinerer LZ77 med Huffman-koding. LZSS reduserer redundans i LZ77, mens LZ78 og LZW bygger opp ordboken på andre måter, men med lignende prinsipper.
Hvilke vindusstørrelser anbefales?
Vanlige vindusstørrelser er 32–64 KB for generelle data. Større vinduer finner flere treff, men krever mer minne og tid. DEFLATE bruker 32 KB. Lookahead-bufferen er vanligvis 256–512 byte. Den beste størrelsen avhenger av repeteringsmønstrene i dataene dine.
// Gjennomregnet eksempel
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// Kodeeksempler
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> Flere spørsmål
S: Hva betyr tripletten (offset, lengde, tegn)?
S: Offsetet angir hvor langt tilbake i det allerede sette vinduet, lengden hvor mange byte som kopieres, og tegnet er neste nye byte. Dekoderen bygger dermed opp utdata trinn for trinn.
S: Hvorfor kan kopien overlappe?
S: Hvis offsetet er mindre enn lengden, leser kopien byte den nettopp skrev. Slik oppstår gjentakelser: (1, 5, x) gir forrige tegn fem ganger.
S: Hvor brukes LZ77?
S: LZ77 finnes i DEFLATE (gzip, zlib, PNG, ZIP) og i varianter i LZ4, Snappy, Zstandard og Brotli. Vindusstørrelse og søkestrategi avgjør komprimeringsgrad og hastighet.