> lz77 | sliding | window <
// LZ77 – compressione con finestra scorrevole e riferimenti di dizionario
>> funzionalità
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.