> lz77 | sliding | window <
// LZ77 – compressione con finestra scorrevole e riferimenti di dizionario
Codifica a dizionario
Riferisce i pattern ripetuti tramite offset e lunghezza.
Finestra scorrevole
Mantiene una finestra mobile per la ricerca del match più lungo.
Algoritmo di base
Costituisce la base per ZIP, GZIP, DEFLATE e PNG.
>> informazioni tecniche
Come funziona LZ77:
LZ77 mantiene una finestra scorrevole dei dati visti di recente. Per ogni posizione l'algoritmo cerca nella finestra la sottostringa più lunga che coincide. Se la trova, emette un riferimento (offset, lunghezza, carattere successivo). In caso contrario emette un letterale (0,0,carattere). In questo modo i pattern ripetuti vengono sostituiti da riferimenti più corti ottenendo una compressione senza perdita.
Esempio 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,)
Perché usare LZ77?:
- ▸Compressione senza perdita
- ▸Non richiede conoscenza preventiva del formato dei dati
- ▸Si adatta ai pattern dei dati
- ▸Implementazione relativamente semplice
- ▸Base di molti algoritmi di compressione moderni
>> domande frequenti
Che cos'è LZ77?
LZ77 è un algoritmo universale di compressione dati senza perdita pubblicato da Abraham Lempel e Jacob Ziv nel 1977. Sostituisce le sequenze ripetute nel flusso di dati con riferimenti a una singola copia apparsa prima nel flusso non compresso.
Come funziona la finestra scorrevole?
La finestra scorrevole è composta da un buffer di ricerca (dati già elaborati) e da un buffer di lookahead (dati da comprimere). L'algoritmo cerca nel buffer di ricerca il match più lungo con l'inizio del lookahead e quindi emette un riferimento o un letterale.
LZ77 rispetto alla compressione moderna?
LZ77 è la base di molti algoritmi moderni. DEFLATE (utilizzato in ZIP e GZIP) combina LZ77 con la codifica di Huffman. LZSS riduce la ridondanza di LZ77, mentre LZ78 e LZW costruiscono il dizionario in modo diverso mantenendo gli stessi principi.
Quali dimensioni di finestra sono consigliate?
Per dati generici le finestre tipiche vanno da 32 KB a 64 KB. Finestre più grandi trovano più corrispondenze ma richiedono più memoria e tempo. DEFLATE usa 32 KB. Il buffer di lookahead è in genere 256–512 byte. La dimensione migliore dipende dai pattern di ripetizione dei tuoi dati.
// Esempio svolto
| # | 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 |
// Esempi di codice
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
>> Altre domande
D: Cosa significa la tripla (offset, lunghezza, carattere)?
R: L’offset indica quanto si torna indietro nella finestra già vista, la lunghezza quanti byte si copiano, e il carattere è il prossimo byte nuovo. Il decodificatore ricostruisce così l’uscita passo dopo passo.
D: Perché la copia può sovrapporsi?
R: Se l’offset è minore della lunghezza, la copia legge byte appena scritti. Così nascono le ripetizioni: (1, 5, x) produce cinque volte il carattere precedente.
D: Dove si usa LZ77?
R: LZ77 è alla base di DEFLATE (gzip, zlib, PNG, ZIP) e, in varianti, di LZ4, Snappy, Zstandard e Brotli. Dimensione della finestra e strategia di ricerca determinano rapporto e velocità.