Questo tipo di compressione è stata sviluppata nel
1952, ed è ancora utilizzatissima in numerosi programmi di
compressione . Il suo funzionamento è piuttosto semplice.
Supponimao di avere un file di testo . Esso sarà composto
da lettere maiuscole, lettere minuscole, numeri, spazi bianchi,
segni di interpunzione e via dicendo. Se facciamo un esame
delle ricorrenze dei vari simboli nel documento, otteniamo
un diagramma di questo tipo :
Scopriamo
che il carattere che ricorre più spesso è lo space, seguito
da alcune lettere minuscole . Ora, ogni carattere è codificato
secondo lo standard ASCII, che richiede 8 bit. Ad esempio,
la "A" vale 65, la barra spaziatrice 32, e così via. La codifica
ASCII tratta tutti i caratteri alla stessa maniera, non si
cura cioè di sapere se un carattere in un testo ricorre 100
volte mentre un altro solo 5 volte. Ad entrambi associa una
stringa lunga 8 bit. In genere , oltre il 90% di un file di
testo consiste di soli 31 caratteri : lo spazio bianco, le
lettere minuscole, la virgola, il return, e il punto. Allora
posso pensare di utilizzare 5 bit per codificare questi 31
elementi .Ciò permette di ridurre fino a 5/8 oltre il 90%
del testo(supponiamo il 95%).. La 32esima stringa, 11111,
sarà un "flag", cioè un simbolo che serve a capire che i bit
che seguono(e sono 8) non apparetengono ai 5 caratteri du
cui sopra. Il rimanente 5% dei caratteri richiederà allora
5 + 8 = 13 bit per essere codificato. In breve, si assegnano
pochi bit ai caratteri più ricorrenti, e un maggior numero
di bit ai caratteri meno frequenti.
Se volessimo portare questo ragionamento all'estremo,
come avviene effettivamente nella codifica di Huffman, possiamo
assegnare uno o due bit allo spazio e al punto, mentre a caratteri
che non compaiono praticamente mai come la tilde o la chiocciolina
possiamo assegnare oltre una dozzina di bit! La codifica di
Huffman si può chiaramente applicare anche la caso di file
che non siano di testo, giacchè è sufficiente considerare
un byte(=8 bit) come rappresentabile tramite un carattere
e quindi applicare le considerazioni viste sopra: ai byte
più frequenti, verranno associati pochi bit, a quelli meno
frequenti invece un numero maggiore di bit.
Lorenzo
Marchetti
LITHIUM.IT, tutta la tecnologia della rete .
