La compressione dei dati rappresenta un argomento decisamente anziano considerando i tempi dell’informatica: per esempio, la codifica di Huffman è una tecnica che risale addirittura agli inizi degli anni '50. Si potrebbe presumere che, essendo trascorsi circa quarant’anni dalla sua presentazione, molto o tutto lo scenario sia radicalmente cambiato, invece questo algoritmo è ancora utilizzato; esso è stato affiancato da altri quale lo LZW che prende il nome dai suoi realizzatori, Lempel e Ziv nonché Welch che apportò sostanziali modifiche.
Dopo tanti anni i cercatori sono unanimemente giunti ad una sola considerazione: non esiste, o per lo meno non è ancora stato realizzato, un algoritmo che fornisca un rapporto di compressione ottimale in tutti i casi e tutte le situazioni e che, conseguentemente, sia dunque da preferire in qualunque situazione.
Così anche i più famosi e blasonati compressori fanno largo impiego di tecniche largamente conosciute: la vera differenza si gioca nel riuscire ad applicare di volta in volta l’algoritmo più idoneo il quale sia stato realizzato nella maniera più ottimizzata possibile, nonché minimizzare la quantità di informazioni ridondanti quali il CRC, il nome originario del file, la relativa directory, eccetera.
Si potrebbero prendere i vari programmi compressori quali il PkZip, Arj, Lha, Zoo, Pack e costruire una tabella comparativa per analizzare i valori di compressione ottenuti, ma, a sorpresa, i rapporti non si discosterebbero significativamente da programma a programma.
Molto più interessante è invece la comparazione dei rapporti di compressione che i vari programmi ottengono in relazione al tipo di dato che devono comprimere: l’efficienza di ogni algoritmo dipende quasi direttamente dalle caratteristiche di ciò che deve essere compresso e quindi la tabella comparativa andrebbe costruita specificando, per ogni programma, il tipo di dato su cui opera: file Ascii, eseguibile, immagine a colori, immagine in toni di grigio, immagine in bianco e nero, wave e Midi. Ma l’utilità di questo lavoro sarebbe relativa in quanto la stragrande maggioranza degli utenti informatici scelgono un compressore e lo utilizzano per ogni circostanza.
La domanda classica che a questo punto viene posta è inerente a quale programma adottare, ma ad essa non esiste una risposta bensì solo linee di principio.
La disponibilità shareware e la diffusione del formato sono quindi alcuni dei parametri che influenzano maggiormente la scelta. Come funziona in concreto un compressore rappresenta un aspetto poco conosciuto: lo scopo di questo articolo è fornire una visione d’insieme dell’argomento sotto il profilo teorico e studiare nella pratica, attraverso alcuni programmi che verranno via via presentati, come si realizzano questi software.

La lunghezza dei codici

I sistemi di codifica sfruttano vari modi di rappresentazione dei dati, ma questi ultimi sono suddivisi in due categorie soltanto: quelli a lunghezza variabile e quelli a lunghezza fissa. L’algoritmo che rientra per antonomasia nella prima categoria è quello di Huffman.
In esso ogni carattere viene rappresentato da una sequenza di bit la cui lunghezza è in funzione della ripetizione del carattere all’interno del file. Così troveremo che in un file di testo il carattere che si ripete maggiormente sarà lo spazio, probabilmente seguito dai caratteri "L", "N", "R" ed "S" in quanto essi sono quelli con maggior diffusione nella lingua italiana; conseguentemente l’algoritmo di Huffman attribuirà a questi caratteri un codice binario più corto di quello utilizzato per caratteri quali la "Q". La codifica a lunghezza fissa prevede, invece, un numero costante di bit per rappresentare i vari caratteri: sfruttando alcuni accorgimenti è possibile ricorrere a sette o anche meno bit per poter memorizzare un documento. Lievemente differente, come vedremo più avanti, è lo LZW che utilizza almeno nove bit per carattere, ma li sfrutta per rappresentare combinazioni di caratteri, conseguendo in tal modo guadagni decisamente sostanziali.

Il subsetting

Il concetto che costituisce la base della compressione consiste nell’applicare un sistema per rappresentare ogni informazione in un formato che occupi uno spazio inferiore a quello normalmente necessario. Ad esempio, all’interno di un file dati in formato solo testo si possono trovare circa cinquanta diversi caratteri: le ventisei lettere dell’alfabeto, le dieci cifre, la virgola, le virgolette, l’accento, il Carriage Retum, il Line Feed, eccetera. Per rappresentare tutti questi caratteri è sufficiente un set ristretto che utilizzi una codifica su sei bit. Comprimendo il file con questa tecnica si ottiene un risparmio di due bit ogni carattere e quindi la dimensione finale del file sarà pari a sei ottavi di quella iniziale. Uno sviluppo di questa tecnica prevede la costruzione di una libreria comprendente solo i caratteri che appaiono nel file: determinando quali essi siano è possibile stabilire quanti bit sono necessari a costruire un subset specifico per ogni file. Ad esempio, se nel file mancano alcune lettere (quelle che hanno una scarsissima probabilità di presenza sono la "X", "Y", "W’, "K", "J" ) e il numero complessivo di caratteri sono solamente trenta o meno, il subset richiede cinque bit. Il caso peggiore ricorre quando il numero di caratteri è superiore a 128: in questo caso il subset necessita di 8 bit e conseguentemente non vi sarà nessun guadagno e, inoltre, inserendo la variabilità del subset da file a file, diventa indispensabile memorizzarlo all’interno del l’archivio con il risultato che quest’ultimo avrà una dimensione superiore a quella del file non compresso.
Per meglio comprendere quanto descritto e poterlo vedere applicato in pratica, sul dischetto è presente un programma in C++ i nome Subset; esso è comunque facilmente convertibile in C. E' ridotto ai minimi termini, ma consente di vedere le parti essenziali per un programma di questo tipo:

• memorizzazione di alcune informazioni del file quali la dimensione originaria;
• memorizzazione del subset in una libreria interna all’ archivio;
• memorizzazione del file compresso;
• tutte le operazioni necessarie alla de codifica del file compresso;

inoltre le funzioni consentono di studiare l’accesso ai file bit per bit. La sintassi di questo programma è semplicissima; per applicare la compressione lo si lancia utilizzando come primo parametro la lettera ‘C’ (indicante Compressione) seguito dal nome del file origine e dal nome dell’archivio. Per ottenere la decompressione, il programma deve essere lanciato con una ‘D’ (Decompressione) come primo parametro seguito dal nome del l’archivio e dal nome del file che deve essere creato da questa operazione. Esso opera quindi come il comando COPY che vuole il file origine e poi quello di destinazione. Il sistema utilizzato per eseguire la compressione è il seguente:

• il file origine viene analizzato per costruire un array di 256 elementi di nome Array contente il numero di vol te che ogni carattere è presente nel file
• viene costruito il subset di nome Libreria: esso è un array di 256 elementi nel quale vengono memorizzati i caratteri che appaiono nel file
• viene calcolato il numero di bit necessari per rappresentare il subset
• il file compresso viene generato memorizzando la lunghezza originaria del file, il numero di elementi costituenti la libreria, la libreria, i dati compressi

al fine di poter analizzare meglio il file origine e come questo tecnica opera, la funzione scritturaRipetizioni() genera un file di nome Risult.txt nel quale appare il numero complessivo di volte che ogni carattere si ripete.

L’algoritmo basato su indice di ripetizione

Si tratta di un algoritmo non molto utilizzato in quanto non è molto efficiente.
Esso si basa su un principio semplicissimo: sostituire le ripetizioni dei caratteri con un solo carattere seguito da un indice riportante il numero di volte che appare.
Ad esempio, la stringaAAABBBB CC sarebbe codificata come A3B4C2.
Ovviamente sono rare le situazioni in cui questa tecnica consegua un soddisfacente rapporto di compressione per cui il vero algoritmo prevede l’inserimento dell’indice solo quando esso produce un guadagno: generalmente sono necessari almeno quattro caratteri contigui identici in quanto il file compresso deve consentire di comprendere se il byte che viene letto rappresenta un carattere oppure un indice e questo viene reso possibile facendo precedere il primo carattere da un particolare byte. E la stessa situazione che ricorre nei comandi modem che sono preceduti dai caratteri AT o dalle sequenze di escape che si inviano alla stampante che iniziano con il carattere ESC.
Poiché non è molto utilizzato ed è estremamente banale non ci soffermeremo ulteriormente.

L’algoritmo run lenght encoding (RLE)

L’algoritmo Run Lenght Encoding si basa su due tabelle precostituite che sono note sia al programma di compressione che a quello di scompattamento. Le due tabelle prendono rispettivamente il nome di White run code lenght e Black run code lenght, al cui interno sono memorizzati dei codici che rappresentano la lunghezza di ogni ripetizione di bit identici, suddivise per tipo di bit: zero ed uno.
Conseguentemente non opera sui caratteri, bensì sulle sequenze di bit.
Questa caratteristica lo pone come indicato soprattutto per il trattamento di immagini monocromatiche. Infatti, un documento Ascii ha delle sequenze di bit identici abbastanza ridotte, ma, ciò nonostante, questo algoritmo consente comunque di ottenere delle compressioni anche su questi tipi di dato. Invece, un disegno in bianco e nero conterrà lunghissime sequenze di bit bianchi e molte di bit neri permettendo di raggiungere interessanti rapporti di compressione.
L’RLE impone che il primo codice si riferisca ad una sequenza White (bit uguale a True, uno), perciò se i dati iniziano con un bit di valore False è necessario utilizzare il codice White che identifica una sequenza di bit True avente lunghezza pari a zero.
Nella pratica questo algoritmo lavora come segue:

• acquisisce il primo bit che viene utilizzato come base di riferimento
• verifica se il bit è False, in al caso memorizza il White Code indicante la lunghezza zero ed il bit di riferimento rimane invariato
• acquisisce tutti i bit successivi uguali a quello di riferimento conteggiando in tal modo quante volte esso è ripetuto, fermandosi non appena il valore del bit letto è diverso da quanto atteso
• memorizza il codice che indica il numero di volte che il bit era consecutivamente ripetuto; in relazione al tipo di bit viene utilizzata la tabella White o Black
• il bit che ha causato l’interruzione del conteggio (bit con valore diverso da quello del bit di riferimento) diventa esso stesso il bit di riferimento e si ricomincia con l’operazione di conteggio dei bit identici.

Evidentemente le tabelle White run code lenght e Black run code lenght sono di fondamentale importanza. Come abbiamo già detto, esse contengono dei codici a lunghezza variabile, per cui i valori con più alta probabilità di ripetizione vengo no codificati con codici più brevi. La cosa più importante consiste nel fatto che non è presente alcun segnale o separazione fra i vari codici. Infatti, dallo schema precedente si è vista la semplicità di eseguire una codifica con questo sistema in quanto non si deve far altro che conteggiare quanti sono i bit identici fra loro e memorizzare un codice che indica questo valore. La decodifica è più semplice di quanto non possa apparire a prima vista.
Entrambe le tabelle sono state create come se fossero degli alberi binari, per cui ogni bit che si legge dal file compresso rappresenta una direzione nell’albero.
Quando si raggiunge una foglia, significa che si è acquisito tutto il codice e che si può ottenere il valore contenuto nella foglia stessa.
Questo valore rappresenta quanti bit devono essere scritti sul file di output.
Il tipo di bit (zero oppure uno) è definito a priori in quanto la prima sequenza fa sempre riferimento a bit di tipo White e poi si succedono, alternandosi, sequenze Black e White.
La routine di decodifica di un messaggio codificata in RLE può essere esemplificato come segue:

• il programma crea un puntatore all’inizio dell’albero binario e, ad ogni bit acquisito, lo percorrere finché non si raggiunge una foglia; a questo punto si acquisisce il valore contenuto nell’elemento raggiunto e si rincomincia il ciclo fino a quando vi saranno dei bit nel file.

L’albero binario si comporta esattamente come una serie di bivi che guidano in una strada obbligata il programma di decodifica. Questo sistema è comunque abbastanza delicato in quanto è sensibile agli errori di trasmissione o lettura e quindi il suo impiego è indicato in quei contesti in cui un errore di trasmissione non provoca un danno grave: la sua più nota implementazione è sui telefax del gruppo 3 [CCITT-T3] [CCITT-T6]

L’algoritmo di Huffman

L’algoritmo di Huffman si basa sul semplice principio di attribuire ad ogni carattere un codice la cui lunghezza in bit sia proporzionale alle ripetizioni del carattere all’interno del file che si vuole elaborare. Molto simile all’algoritmo del subsetting, si differenzia da questo in quanto utilizza un numero di bit variabili per ogni carattere e ogni carattere che ha una maggiore distribuzione viene codificato con maggiore brevità.
Per esempio se in un documento composto da mille caratteri avente la lettera "A" è presente cento volte e la "Q" dieci volte, un subsetting su cinque bit compatterà la lettera "A" in 62,5 byte (100 caratteri per 5 bit diviso 8) e la "Q" in 3,125 bit totalizzando poco più di 65 byte, mentre l’algoritmo di Huffman potrebbe codificare la "A" con tre bit e la "Q" con sei per un totale di 45 byte (37.5+7.5).
Questo algoritmo può essere implementato in due modi diversi.
Il primo lo si può definire dinamico, ovvero la codifica varia da file a file; con questo sistema è necessario memorizzare all’interno del file compresso anche i codici con il loro significato, altrimenti la scompattazione risulterebbe impossibile.
Utilizzando invece delle tabelle standard si ottengono buoni risultati, ma non soddisfacenti quanto quelli raggiungibili con il precedente sistema, ma, per controparte, per mette tempi di compressione minori in quanto il programma non deve scorrere tutto il file origine per studiare la distribuzione dei caratteri al fine di generare l’opportuna tabella.
Un notissimo e datato esempio di questo sistema di codifica è l’alfabeto Morse (vedi riquadro).
Questa sua caratteristica di realizzare tabelle specifiche per ogni situazione lo pone in assoluto come il migliore algoritmo nel l’area della codifica a lunghezza variabile.
Per poter scrivere un programma di compressione e scompattamento basato su questo algoritmo è sufficiente avere dimestichezza con gli alberi binari.
Il flow dovrebbe essere simile al seguente:

• creazione di una tabella di 256 elementi:
• lettura sequenziale di ogni carattere del file e totalizzazione delle volte che ogni singolo carattere ricorre;
• creazione di una linked list nella quale i caratteri più frequenti appaiono più vicini alla radice;
• creazione della tabella dei codici di 256 elementi inserendovi il codice che corrisponde al percorso binario per raggiungere ogni elemento (i caratteri non presenti nel file non avranno nessun codice di compressione);
• memorizzazione della tabella di codifica all’interno del file di output;
• riposizionamento del file di input suo inizio;
• lettura di ogni singolo carattere scrittura sul file di output del corrispondente valore codificato;
• chiusura dei file.

Appare evidente che questo algoritmo così implementato non è applicabile alle trasmissioni dati in quanto esso deve necessariamente conoscere la distribuzione dei caratteri, cosa che in quest’ambito non è possibile; per questo motivo esso è più idoneo alla compressione dei file.

L’algoritmo LZW

L’algoritmo LZW (Lempel, Ziv, Welch) si basa su una tecnica contraria al subsetting. Anziché ridurre il numero di caratteri facenti parte dei dati, esso provvede a creare un alfabeto esteso che possa memorizzare anche le sequenze dei caratteri. Esso è basato su almeno 9 bit e questo gli consente di gestire un numero di combinazioni vicino a 2 elevato alla 9 potenza.
Si basa su un principio di memorizzazione delle sequenze dei caratteri come nuovi caratteri; ad ogni ripresentazione della sequenza essa viene codificata occupando un solo carattere. Ad esempio la sequenza:

AAABBAABBAABBAA

causerà la codifica della doppia "A" e della doppia "B"; ogni volta che saranno presenti due "A", verranno memorizzate in un solo carattere da nove bit anzi ché in due da otto con un guadagno corrispondente quasi al 50%.
Vediamo meglio questa operazione. Innanzi tutto si deve definire il numero massimo di bit che la tabella dei caratteri può gestire e si provvede alla sua creazione inserendovi contemporaneamente i 256 caratteri Ascii nei primi elementi numerati da zero a 255; nell’elemento 256 trova posto un nuovo carattere di nome di "Clear Code" e nel 257esimo l"End of Information".
Dal 258esimo verranno inseriti i nuovi pseudocaratteri, ovvero le nuove sequenze di byte che vengono trovate durante l’elaborazione.
La tecnica sfrutta l’idea di combinare più caratteri fra loro, per cui vengono generati dei nuovi elementi nella tabella per ogni nuova sequenza trovata affinché le successive identiche sequenze siano memorizzabili attraverso il codice precedentemente generato.
Per comprendere questo algoritmo nei suoi vari aspetti è necessario descriverlo con attenzione e, per meglio facilitare questa operazione, sul dischetto è presente un file di nome LZWEXE con i relativi sorgenti in C++; esso è una parziale implementazione di questo sistema di compressione che è estremamente utile a comprendere direttamente come l’algoritmo LZW operi concretamente.
Esso accetta dalla linea di comando una stringa che provvede a codificare generando un file di nome LZW_CODE.OUT e poi legge questo file, lo scompatta e ne visualizza il risultato.
Il file LZW_CODE.OUT non contiene i dati compressi come accadeva col programma SUBSET.EXE (il quale è in programma completo e totalmente funzionante), bensì i codici che l’algoritmo di compressione deve gestire prima si scriverli sul file di output.
Con qualche semplice modifica anche il programma LZW.EXE può essere utilizzato come vero e proprio programma di compressione e decompressione, ma il suo scopo principale consiste nell’illustrare quanto più chiaramente possibile il funzionamento dell’algoritmo. Infatti, eseguendo un Type del file di output si possono studiare i codici che vengono creati e gestiti.
Passiamo adesso ad analizzare la codifica in metalinguaggio raffrontandola alle varie funzioni in linguaggio C che potrete trovare nel programma:

• creare una stringa che dovrà contenere la sequenza; nel programma esemplificativo viene utilizzato una variabile di tipo unsigned long int di nome cod che permette di gestire sequenze di quattro caratteri
inizializzazione della tabella dei caratteri (array Table) come precedentemente descritto tramite la funzione initTable()
• scrivere sul file di output il carattere "Clear Code" (questa operazione il programma la omette)
eseguire un ciclo finché nel file di input ci sono dei caratteri da acquisire, durante il quale si eseguiranno i passi descritti qui di seguito
• verificare se il carattere appena letto (la variabile c) concatenato ai precedenti (variabile cod) costituisce una sequenza già nota: in caso affermativo memorizzare il carattere nella sequenza e tornare all’inizio del ciclo, altrimenti si deve estrarre dalla tabella Table il corrispondente codice mediante la funzione codeFromTable(), memorizzare nella tabella la nuova sequenza composta da cod e c, impostare il valore dell’at tuale sequenza (cod) uguale al carattere appena letto (c)
• al termine del file di input si memorizza la sequenza rimasta in elaborazione e si chiude il file con il carattere "End of Information".

Il programma provvede a limitare la lunghezza delle sequenze a quattro caratteri attraverso il contatore byteLen, perciò sono presenti nella routine anche delle if che gestiscono questo limite.
Per meglio comprendere questo sistema di compressione è consigliabile vederlo in pratica: se il programma LZW.EXE viene lanciato senza parametri provvede ad elaborare una stringa interna, altrimenti utilizzerà il primo argomento della command line.
L’LZW originale non prevede che il programma memorizzi all’interno del file la tabella, ma che essa sia generata autonomamente durante la fase di scompattazione; ciò avviene considerando che se la sequenza è già nella tabella allora si può scompattare direttamente, altrimenti essa sarà decodificata eliminando l’ultimo inserito (in quanto prima del suo inserimento essa era stata riconosciuta) e decodificando l’ultimo carattere da solo.
Anche se appare complicata, questa procedura consente considerevoli risparmi di spazio in quanto permette di non memorizzare la tabella perché verrà generata automaticamente durante la fase di decompressione.
L’algoritmo LZW è considerato come uno dei migliori fra gli algoritmi di compressione basati sui codici a lunghezza costante [CCITT-T4] [CCITT-T6]

Conclusioni

La compressione delle informazioni rappresenta certamente un’area poco gratificante per la sperimentazione, in quanto si percorrono quasi sempre dei sentieri già tracciati da qualcun altro. Sebbene rivesta spesso una scarsa utilità pratica la sua comprensione e conoscenza algoritmica, è altrettanto vero che costituisce un bagaglio culturale importante.
Esistono numerosi programmi specifici per la compressione che hanno oramai raggiunto lo status di standard del mercato; questa considerazione è importante in quanto varie software house mettono a disposizione delle librerie e DLL dietro pagamento dei diritti oppure gratuitamente o shareware: questo permette al programmatore di implementare le funzionalità di compressione e decompressione all’interno dei propri programmi impiegando strumenti già funzionanti e collaudati che gli consentono di non investire tempo nella loro realizzazione.
Come sviluppatori di software raramente vi capiterà di incontrare situazioni nelle quali esiste la reale esigenza di costruire un compressore, ad ogni modo ora avete un bagaglio culturale che consente di affrontare l’argomento con una discreta cognizione di causa. Non mi resta altro che augurarvi buon lavoro.

Bibliografia

[1] Welch: Terry A. Weich, "A tecnique for High performance Data compression", IEEE Computer, Vol.7 num.6, Giugno 1984
[2] CCITT-T4: "Standardization of Group 3 facsimile apparatus for document transmission", Recommendation T.4, Volume VII, Fascicolo VIII.3, Terminal Equipment and Protocols for Telematic Services, The International Telegraph and Telephone Consultative Committee (CCITT), Ginevra, 1985, da pagina 16 a 31.
[3] CCITT-T6: "Facsimile coding schemes and coding control function for group 4 facsimile apparatus", Raccomendation T.6, Volume 7 del fascicolo VII.3, "Terminal equipment and protocol for telematic services, CCITT, 1985, pagina 40 e seguenti.

Tratto da:
Paolo Guccini
Rivista DEV Computer Programming
Edizioni Infomedia
Luglio 1996