> lz77 | sliding | window <
// LZ77 – glidende vindueskomprimering med ordbogsreferencer
Ordbogskodning
Refererer gentagne mønstre med forskydning og længde.
Glidende vindue
Holder et bevægeligt vindue til mønstergenkendelse.
Grundalgoritme
Danner grundlaget for ZIP, GZIP, DEFLATE og PNG.
>> tekniske detaljer
Sådan fungerer LZ77:
LZ77 holder et glidende vindue over nyligt sete data. For hver position søger algoritmen i vinduet efter den længste matchende streng. Hvis der findes et match, udskrives en reference (forskydning, længde, næste tegn). Hvis ikke, udskrives et bogstaveligt tegn (0,0,tegn). Gentagelser erstattes dermed af korte referencer og giver tabsfri 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 bruge LZ77?:
- ▸Tabsfri komprimering
- ▸Kræver ingen forhåndsviden om data
- ▸Tilpasser sig datas mønstre
- ▸Relativt enkel implementering
- ▸Grundlag for moderne komprimeringsalgoritmer
>> ofte stillede spørgsmål
Hvad er LZ77?
LZ77 er en universel tabsfri datakomprimeringsalgoritme publiceret af Abraham Lempel og Jacob Ziv i 1977. Algoritmen erstatter gentagne sekvenser i datastrømmen med referencer til en tidligere forekomst i den ukomprimerede strøm.
Hvordan fungerer det glidende vindue?
Det glidende vindue består af en søgebuffer (allerede behandlede data) og en lookahead-buffer (data der skal komprimeres). Algoritmen søger i søgebufferen efter det længste match med starten af lookahead-bufferen og udskriver derefter enten en reference eller et bogstavligt tegn.
LZ77 vs. moderne komprimering?
LZ77 er fundamentet for mange moderne komprimeringsalgoritmer. DEFLATE, som bruges i ZIP og GZIP, kombinerer LZ77 med Huffman-kodning. LZSS reducerer overflødighed i LZ77, mens LZ78 og LZW opbygger ordbogen på andre måder men med samme grundidé.
Hvad er gode vinduesstørrelser?
Typiske vinduesstørrelser er 32–64 KB for generelle data. Større vinduer finder flere matches, men kræver mere hukommelse og tid. DEFLATE bruger 32 KB. Lookahead-bufferen er typisk 256–512 byte. Den optimale størrelse afhænger af gentagelsesmønstrene i dine data.
// Gennemregnet 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ørgsmål
S: Hvad betyder tripletten (offset, længde, tegn)?
S: Offsettet angiver, hvor langt tilbage i det allerede sete vindue, længden hvor mange byte der kopieres, og tegnet er den næste nye byte. Afkoderen opbygger således uddata trin for trin.
S: Hvorfor må kopien overlappe?
S: Hvis offsettet er mindre end længden, læser kopien byte, den lige har skrevet. Sådan opstår gentagelser: (1, 5, x) giver det foregående tegn fem gange.
S: Hvor bruges LZ77?
S: LZ77 findes i DEFLATE (gzip, zlib, PNG, ZIP) og i varianter i LZ4, Snappy, Zstandard og Brotli. Vinduesstørrelse og søgestrategi afgør komprimeringsgrad og hastighed.