Compressione

Concetto base


Nei computer, i caratteri vengono codificati usando il codice ASCII che assegna un codice di 8 bits ad ogni simbolo. Ad esempio il codice ASCII 97 (01100001 in binario) rappresenta la lettera a. In questo codice standard tutti i caratteri sono trattati allo stesso modo, quindi anche quelli usati più frequentemente (ad esempio la e o la a) vengono codificati come quelli usati più raramente (ad esempio il carattere ü). Un file di 100 caratteri quindi occuperà sempre 800 bits (8 bits * 100 caratteri = 800) sia esso composto da 100 caratteri differenti piuttosto che da 100 identici.

Visto che in tutti i file testo alcuni caratteri appaiono con una frequenza maggiore di altri non avrebbe senso assegnare a questi un codice composto da un numero inferiore di bits in modo da risparmiare spazio nella codifica ?? Questa idea è in fondo la stessa usata da Samuel Morse nel suo famoso codice in cui le lettere a frequenza maggiore vengono rappresentate da sequenze più piccole mentre quelle meno usate con dei codici più lunghi. Ecco alcuni codici di esempio del codice Morse:
e = ·
a = · -
q = - - ·-
j = ·- - -


L'idea di usare codici più corti fu introdotta nell'ambito informatico da Claude Shannon e R. Fano negli anni 50 che inventarono il famoso algoritmo di compressione Shannon-Fano. Tale algoritmo fu comunque migliorato da D.A. Huffman qualche anno dopo e di fatto sostitui il precedente. L'algoritmo di Huffman viene applicato ancora oggi nei migliori software di compressione ed è possibile vederne un esempio pratico nelle pagine seguenti.

Per capire i vantaggi di questo tipo di algoritmo consideriamo un file di 40 caratteri in cui le lettere abbiano la seguente frequenza: A: 20 volte, B: 5 volte, E: 3 volte, C: 7 volte, O: 5 volte.

Usando la codifica standard ASCII, il nostro file occuperà 40*8 bits ovvero 320 bits. Se invece usiamo una codifica a lunghezza variabile, potremmo rappresentare le lettere con frequenza maggiore (la A e la C nel nostro esempio) con un numero inferiore di bits rispetto a quelle con bassa frequenza (la E la B e la O), risparmiando così spazio ed ottenendo un file con lunghezza inferiore ai 320 bits!