Comprimere
i files del PC
La
necessità di comprimere i files nasce principalmente da due esigenze:
-
dall’esigenza di risparmiare spazio su disco;
-
dall’esigenza di ridurre le loro dimensioni per la relativa trasmissione via
internet. Sappiamo tutti che più
un
file è di dimensioni ridotte più la sua velocità di trasmissione via web
aumenta.
Scopo
quindi delle tecniche di compressione è quello di ridurre il peso in byte dei
files per aumentarne la
loro
velocità di trasmissione o per risparmiare lo spazio occupato su disco.
Esistono
essenzialmente due tipi di compressione:
-
Il primo tipo rispetta l’integrità dei dati evitando di perdere dati durante il
processo di riduzione dello
spazio
occupato. I dati così compressi non possono essere immediatamente utilizzati ma
devono prima
venire
ricostruiti (in gergo estratti).
-
Il secondo comporta una leggera perdita d’accuratezza delle informazioni
soprattutto audiovideo
limitata
però a dettagli non percepibili (es. files audiovideo: Mp3 e Jpeg).
Tecniche
di questo tipo sono utilizzate per la creazione di siti internet più leggeri o
per download più veloci
dei
files via Web.
Sul
mercato esistono molti programmi a disposizione che fungono anche da
archiviatori, ciascuno dei quali
funziona
con l’ausilio di algoritmi matematici particolari che codificano i files
producendo altri files
riconoscibili
dall’estensione .sit .targ.gz o zip (contraddistinti da un’icona raffigurante
una piccola morsa).
Questi
programmi si fondano sull’eliminazione della ridondanza e della ripetizione
d’informazioni non
necessarie;
maggiori sono le ripetizioni contenute più le tecniche di riduzione del peso
risulteranno efficienti.
La
compressione ottenuta si misura con il rapporto tra le dimensioni del file
ridotto e quello originario. La
maggior
parte di questi software lavorano dunque analizzando le occorrenze ripetute di
simboli o, nel caso
di
file testuali, di lettere.
L'‘algoritmo di Huffman
stila un elenco delle volte in cui nel file analizzato compaiono ripetuti i
diversi
simboli.
Successivamente viene composto una sorta di vocabolario che associa ad ogni
simbolo un numero
sulla
base della classifica redatta e quindi il tutto viene tradotto con questa
codifica, creando così un
alfabeto
ridotto capace di dare le stesse informazioni con un numero minore di
caratteri.
L'‘algoritmo di Shannon-Fano
crea invece il vocabolario costruendo una serie di sottoinsiemi sempre più
piccoli
e associando a ciascuno di questi insiemi una stringa composta da 0 e da 1.
Un'ulteriore
tecnica di codifica è quella conosciuta come Lz dalle iniziali degli inventori Lempel e Ziv, da cui deriva l'algoritmo
Lzss
progettato nel 1982 da James Storer e Thomas Szymanski; metodo che più avanti
sarà alla base del
programma
Winzip.
Esistono
comunque altri programmi di compressione meno utilizzati ma non per questo meno
validi come
Win
Rar, Pkware, Mpag-4, Win Ace, E-vue Image Studio.
Nelle
pagine più avanti ci soffermeremo solamente sul Winzip nella sua ultima
versione 8 in quanto ritenuto
il
programma di compressione più diffuso al momento. Vi segnaliamo comunque che la
nuova versione Windows Millenium è dotata di una funzione che è già in
grado,
grazie ad apposite estensioni, di leggere e trattare il contenuto degli archivi
zip compressi senza la
necessità
di adottare software esterni sviluppati da terzi.
Vorrei
concludere il preambolo dedicando questo mio piccolo contributo al geniale Phillip W. Katz che fu
pioniere
in materia sviluppando il suo programma Pkware, il primo in assoluto di
compressione e
decompressione
di files ( a cui tutti hanno cercato di attingere a piene mani per sviluppare
analoghi software
)
ma che morì di stenti e alcoolizzato per non aver saputo sfruttare
commercialmente la sua intuizione
ritenuta
fondamentale per il progresso dell’informatica.
L'algoritmo
Huffman.
Quest'algoritmo
non distruttivo fu inventato nel 1952 dal matematico D.A. Huffman ed è un
metodo di compressione particolarmente ingegnoso. Funziona in questo modo:
analizza il numero
di ricorrenze di ciascun elemento costitutivo del file da comprimere: i singoli
caratteri in un file di testo, i pixel in un file grafico.
Accomuna i due
elementi meno frequenti trovati nel file in una categoria-somma che li
rappresenta entrambi. Così ad esempio se A ricorre 8 volte e B 7 volte, viene
creata la categoria-somma AB, dotata di 15 ricorrenze. Intanto i componenti A e
B ricevono ciascuno un differente marcatore che li identifica come elementi
entrati in un'associazione.
L'algoritmo
identifica i due successivi elementi meno frequenti nel file e li riunisce in
una nuova categoria-somma, usando lo stesso procedimento descritto al punto 2.
Il gruppo AB può a sua volta entrare in nuove associazioni e costituire, ad
esempio, la categoria CAB. Quando ciò accade, la A e la B ricevono un nuovo
identificatore di associazione che finisce con l'allungare il codice che
identificherà univocamente ciascuna delle due lettere nel file compresso che
verrà generato.
Si crea per
passaggi successivi un albero costituito da una serie di ramificazioni binarie,
all'interno del quale appaiono con maggiore frequenza e in combinazioni
successive gli elementi più rari all'interno del file, mentre appaiono più
raramente gli elementi più frequenti. In base al meccanismo descritto, ciò fa
sì che gli elementi rari all'interno del file non compresso siano associati ad
un codice identificativo lungo, che si accresce di un elemento ad ogni nuova associazione.
Gli elementi invece che si ripetono più spesso nel file originale sono anche i
meno presenti nell'albero delle associazioni, sicché il loro codice
identificativo sarà il più breve possibile.
Viene generato il
file compresso, sostituendo a ciascun elemento del file originale il relativo
codice prodotto al termine della catena di associazioni basata sulla frequenza
di quell'elemento nel documento di partenza.
Il guadagno di
spazio al termine della compressione è dovuto al fatto che gli elementi che si
ripetono frequentemente sono identificati da un codice breve, che occupa meno
spazio di quanto ne occuperebbe la loro codifica normale. Viceversa gli
elementi rari nel file originale ricevono nel file compresso una codifica
lunga, che può richiedere, per ciascuno di essi, uno spazio anche notevolmente
maggiore di quello occupato nel file non compresso.
Dalla somma
algebrica dello spazio guadagnato con la codifica breve degli elementi più
frequenti e dello spazio perduto con la codifica lunga degli elementi più rari
si ottiene il coefficiente di compressione prodotto dall'algoritmo Huffman. Da
quanto detto si deduce che questo tipo di compressione è tanto più efficace
quanto più ampie sono le differenze di frequenza degli elementi che
costituiscono il file originale, mentre scarsi sono i risultati che si
ottengono quando la distribuzione degli elementi è uniforme.
Un'ottima
dimostrazione del funzionamento di questo algoritmo è visionabile su Internet
all'indirizzo http://www.cs.sfu.ca/CC/365/li/squeeze/Huffman.html. Qui
troverete un'applet java in grado di eseguire la generazione dell'albero delle
associazioni, di produrre il codice compresso e di calcolare il coefficiente
finale di compressione. Nelle due immagini sotto riportate, tratte dall'uso di
questa applet, potete osservare l'albero generato dalla frequenza di
ricorsività delle lettere costituenti un noto scioglilingua ed il risultato
della compressione Huffman ottenuta.
ShannonFanoCode(L)
if |L| == 1 then
return 0
if |L| >= 2 then
"dividere L in due sottoliste L1 ed L2 , considerando le coppie
nell'ordine in cui si presentano in L1 , in modo tale che la differenza tra
(x,n) n e (x,n) n sia minima"
"aggiungere uno 0 alla parola di codice wx per tutti i caratteri x :
(x,n) L1"
"aggiungere uno 1 alla parola di codice wx per tutti i caratteri x :
(x,n) L2"
if
|L1| == 1 then
return wx
else
ShannonFanoCode(L1)
if |L2| == 1 then
return wx
else
ShannonFanoCode(L2)
L'algoritmo LZW (Lempel-Ziv-Welch)
L'algoritmo non
distruttivo che va sotto il nome di LZW è il risultato delle modifiche
apportate nel 1984 da Terry Welch ai due algoritmi sviluppati nel 1977 e nel
1978 da Jacob Ziv e Abraham Lempel, e chiamati rispettivamente LZ77 e LZ78.
Il funzionamento
di questo metodo è molto semplice: viene creato un dizionario delle stringhe di
simboli ricorrenti nel file, costruito in modo tale che ad ogni nuovo termine
aggiunto al dizionario sia accoppiata in modo esclusivo un'unica stringa.
Esiste un dizionario di partenza costituito dai 256 simboli del codice ASCII,
che viene incrementato con l'aggiunta di tutte le stringhe ricorrenti nel file,
che siano maggiori di un carattere. Ciò che viene memorizzato nel file
compresso è un codice breve che rappresenta in modo inequivocabile la stringa
inserita nel dizionario così creato.
Esiste,
naturalmente, un insieme di regole non ambigue per la codifica del dizionario,
che permetterà in seguito al sistema di decompressione di generare un
dizionario esattamente uguale a quello di partenza, in modo tale da poter
effettuare l'operazione inversa a quella di compressione, consistente nella
sostituzione del codice compresso con la stringa originale. La reversibilità
completa e precisa dell'operazione è indispensabile al fine di riottenere
l'esatto contenuto del file originale.
Il risparmio di
spazio in un file compresso con LZW dipende dal fatto che il numero di bit
necessari a codificare il "termine" che rappresenta una stringa nel
dizionario è inferiore al numero di bit necessari a scrivere nel file non
compresso tutti i caratteri che compongono la stringa. Quanto più numerose e
lunghe sono le stringhe che è possibile inserire nel dizionario, tanto maggiore
sarà il coefficiente di compressione del file. I formati grafici più noti che
utilizzano l'algoritmo LZW sono il TIFF e il GIF. Esso è utilizzato anche dallo
standard V.42bis, implementato su tutti i modem di ultima generazione come uno
dei protocolli per la trasmissione di dati compressi.
Per avere una
dimostrazione pratica di come funziona questo tipo di codifica per mezzo di
dizionari di simboli, potete collegarvi su Internet alla pagina
http://www.cs.sfu.ca/CC/365/li/squeeze/LZW.html, dalla quale è possibile
accedere ad una interessante applet java. La sua interfaccia, molto intuitiva,
vi consentirà di effettuare in prima persona una codifica di stringhe di testo
con LZW, verificando direttamente la creazione del dizionario, la sua
ricostruzione in un'altra finestra ed il coefficiente finale di compressione
ottenuto.