Come funziona la compressione dei file

Nel nostro esempio precedente, abbiamo scelto tutte le parole ripetute e le abbiamo messe in un dizionario. Per noi, questo è il modo più ovvio di scrivere un dizionario. Ma un programma di compressione lo vede in modo diverso: Non ha alcun concetto di parole separate – cerca solo dei modelli. E per ridurre il più possibile le dimensioni del file, seleziona attentamente quali schemi includere nel dizionario.

Se ci avviciniamo alla frase da questa prospettiva, ci ritroviamo con un dizionario completamente diverso.

Se il programma di compressione scandisse la frase di Kennedy, la prima ridondanza che incontrerebbe sarebbe lunga solo un paio di lettere. In “ask not what your,” c’è uno schema ripetuto della lettera “t” seguita da uno spazio — in “not” e “what.” Se il programma di compressione lo scrivesse nel dizionario, potrebbe scrivere un “1” ogni volta che una “t” fosse seguita da uno spazio. Ma in questa breve frase, questo schema non si verifica abbastanza per renderla una voce utile, così il programma alla fine la sovrascriverebbe.

La prossima cosa che il programma potrebbe notare è “ou”, che appare sia in “your” che in “country”. Se questo fosse un documento più lungo, scrivere questo modello nel dizionario potrebbe far risparmiare molto spazio — “ou” è una combinazione abbastanza comune nella lingua inglese. Ma mentre il programma di compressione lavorava su questa frase, avrebbe rapidamente scoperto una scelta migliore per una voce del dizionario: Non solo “ou” è ripetuto, ma le intere parole “your” e “country” sono entrambe ripetute, e sono effettivamente ripetute insieme, come la frase “your country”. In questo caso, il programma sovrascriverebbe la voce del dizionario per “ou” con la voce per “your country.”

Anche la frase “can do for” è ripetuta, una volta seguita da “your” e una volta seguita da “you”, dandoci uno schema ripetuto di “can do for you. Questo ci permette di scrivere 15 caratteri (spazi inclusi) con un valore numerico, mentre “your country” ci permette di scrivere solo 13 caratteri (spazi inclusi) con un valore numerico, quindi il programma sovrascriverebbe la voce “your country” come solo “r country”, e poi scriverebbe una voce separata per “can do for you”. Il programma procede in questo modo, raccogliendo tutte le informazioni ripetute e poi calcolando quali modelli dovrebbe scrivere nel dizionario. Questa capacità di riscrivere il dizionario è la parte “adattiva” dell’algoritmo LZ basato sul dizionario adattivo. Il modo in cui un programma fa questo è abbastanza complicato, come puoi vedere dalle discussioni su Data-Compression.com.

Non importa quale metodo specifico usi, questo sistema di ricerca approfondita ti permette di comprimere il file in modo molto più efficiente di quanto potresti fare scegliendo solo le parole. Usando i modelli che abbiamo scelto sopra, e aggiungendo “__” per gli spazi, otteniamo questo dizionario più grande:

E questa frase più piccola: “1not__2345__–__12354”

La frase ora occupa 18 unità di memoria, e il nostro dizionario occupa 41 unità. Quindi abbiamo compresso la dimensione totale del file da 79 unità a 59 unità! Questo è solo un modo di comprimere la frase, e non necessariamente il più efficiente. (Vedi se riesci a trovare un modo migliore!)

Quanto è buono questo sistema? Il rapporto di riduzione del file dipende da una serie di fattori, tra cui il tipo di file, la dimensione del file e lo schema di compressione.

Nella maggior parte delle lingue del mondo, certe lettere e parole appaiono spesso insieme nello stesso schema. A causa di questo alto tasso di ridondanza, i file di testo si comprimono molto bene. Una riduzione del 50% o più è tipica per un file di testo di buone dimensioni. La maggior parte dei linguaggi di programmazione sono anche molto ridondanti perché usano una collezione relativamente piccola di comandi, che spesso vanno insieme in uno schema fisso. I file che includono molte informazioni uniche, come la grafica o i file MP3, non possono essere compressi molto con questo sistema perché non ripetono molti schemi (di più su questo nella prossima sezione).

Se un file ha molti schemi ripetuti, il tasso di riduzione tipicamente aumenta con la dimensione del file. Lo si può vedere semplicemente guardando il nostro esempio: se avessimo un maggior numero di discorsi di Kennedy, saremmo in grado di fare riferimento agli schemi nel nostro dizionario più spesso, e quindi ottenere di più dallo spazio di file di ogni voce. Inoltre, modelli più pervasivi potrebbero emergere nel lavoro più lungo, permettendoci di creare un dizionario più efficiente.

Questa efficienza dipende anche dall’algoritmo specifico usato dal programma di compressione. Alcuni programmi sono particolarmente adatti a cogliere i pattern in certi tipi di file, e quindi possono comprimerli in modo più succinto. Altri hanno dizionari all’interno di dizionari, che potrebbero comprimere in modo efficiente i file più grandi ma non quelli più piccoli. Mentre tutti i programmi di compressione di questo tipo lavorano con la stessa idea di base, c’è in realtà una buona dose di variazione nel modo di esecuzione. I programmatori cercano sempre di costruire un sistema migliore.