Dimostratore di compressione
Come può un file diventare più piccolo senza perdere una sola lettera? Accorgendosi che si ripete. Incolla un testo o scegli un esempio e guarda all'opera tre metodi classici: LZ77 rimanda al testo comparso prima, LZW impara un dizionario di stringhe mentre legge e la codifica run-length conta le sequenze dello stesso carattere. Ogni metodo viene decompresso di nuovo per mostrare che non si è perso nulla, e un grafico li confronta con ZIP e con il limite dell'entropia. Scrivi o incolla un testo, oppure scegli un esempio, e scegli un metodo. LZ77 sostituisce le ripetizioni con riferimenti al testo precedente: fai clic su una parte evidenziata per vedere che cosa copia. LZW costruisce un dizionario di stringhe mentre legge e ne invia i numeri. RLE comprime le sequenze dello stesso carattere. Il grafico confronta ogni metodo con ZIP e con il limite dell'entropia, e l'app decomprime di nuovo il risultato per verificare che non sia andato perso nulla.
Come funziona
- Scrivi o incolla un testo, oppure scegli un esempio: un paragrafo, una canzone con ritornello, una riga di pixel, una tabella di dati, lettere casuali o DNA.
- Scegli LZ77, LZW o RLE. Per LZ77, imposta quanto indietro può guardare, e fai clic su un riferimento evidenziato per vedere il testo precedente che copia.
- Confronta le dimensioni nei riquadri e nel grafico con ZIP e con il limite dell'entropia; il controllo sotto il testo conferma che la decompressione restituisce l'originale.
Le ripetizioni sono la chiave
La compressione senza perdita funziona perché i dati reali si ripetono. LZ77 tiene una finestra del testo appena letto; ogni volta che i caratteri successivi sono già comparsi in quella finestra, scrive un breve riferimento, “torna indietro di tanto e copia tanti caratteri”, al posto dei caratteri stessi. Un riferimento costa un numero fisso di bit, per quanto lunga sia la copia, quindi sono le ripetizioni lunghe e frequenti a far risparmiare di più. LZW ottiene lo stesso effetto in modo diverso: costruisce un dizionario di ogni nuova stringa che incontra e da quel momento invia il numero della stringa.
Perché alcuni dati non si riducono
Un metodo che rimpicciolisce alcuni file deve per forza ingrandirne altri: i file corti sono meno di quelli lunghi, quindi non possono accorciarsi tutti. La compressione vince sui dati con schemi ricorrenti, come testi, tabelle e immagini semplici, e perde su quelli che non ne hanno. Lettere casuali, dati cifrati e file già compressi non offrono ai metodi nulla a cui rimandare, e il risultato è grande quanto l'input, o anche di più. La codifica run-length lo mostra nel modo più chiaro: su un testo senza sequenze raddoppia la dimensione.
Domande frequenti
Qual è la differenza tra compressione senza perdita e con perdita?
La compressione senza perdita restituisce esattamente l'originale, bit per bit; è indispensabile per testi, programmi e dati, e questo dimostratore mostra solo metodi senza perdita. La compressione con perdita, come nelle foto JPEG, nella musica MP3 e nei video, elimina dettagli che quasi non si notano e ottiene file molto più piccoli, ma l'originale non si può più recuperare.
Come comprime i file ZIP?
ZIP e gzip usano deflate, che prima applica LZ77 con una finestra di 32 KB e poi scrive i letterali e i riferimenti con i codici di Huffman: codici brevi per i valori comuni e lunghi per quelli rari. È questo secondo passaggio che di solito fa battere a ZIP il semplice LZ77 mostrato qui, che spende un numero fisso di bit per ogni token.
LZ77 può scendere sotto l'entropia?
L'entropia mostrata conta i caratteri uno alla volta, senza contesto. LZ77 e LZW usano il contesto, perché un riferimento copia un intero tratto di testo precedente, quindi su un testo ripetitivo possono battere quel valore di molto. Non possono mai battere la vera entropia della sorgente, che tiene conto di tutto il contesto.
Perché le dimensioni sono diverse da quelle di un vero file ZIP?
Il dimostratore conta solo i bit dei dati codificati. Un vero file ZIP aggiunge intestazioni, il nome del file, un checksum e le tabelle di Huffman, che rendono i file molto piccoli più grandi anziché più piccoli.
Il mio testo viene inviato da qualche parte?
No. Ogni metodo, compreso il confronto con ZIP, viene eseguito nel tuo browser, e il tuo testo resta nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor