SANC: Sound Adaptive Neural Compression - Compressore di campioni sonori a reti neurali

Contenuto                                                                                                                                Prefazione
8
Nel quarto capitolo viene descritto il funzionamento dell algoritmo di compressione Sound
Adaptive Neural Compression.
Nella sua prima parte sono riportati degli schemi a blocchi con una descrizione qualitativa del
funzionamento, senza indagare  il loro contenuto.
Nei paragrafi seguenti sono esposte le caratteristiche specifiche di ciascuno.
Sono riportati, inoltre, alcuni risultati ed alcuni confronti con altri sistemi esistenti; il confronto Ł
stato effettuato considerando delle prestazioni ipotetiche ottenibili dal sistema.
Sarebbe stato interessante vederne un esemplare in funzione, ma dati i costi sembra per ora
impossibile.
Come si vedr , infatti, uno dei limiti fondamentali di questo sistema Ł rappresentato dalle
dimensioni e dal costo stesso. Non Ł detto, peraltro, che in futuro la potenza di calcolo sia tale da
permettere una realizzazione contenuta fisicamente e nel prezzo.
L algoritmo Ł stato comunque verificato realizzandone una versione «software». La costosa
realizzabilit  «hardware» non limita quindi l applicabilit  dello stesso, pena, ovviamente, tempi di
elaborazione decisamente piø lunghi.
Nel quinto capitolo vengono descritti i blocchi del sistema di decompressione per il recupero del
segnale musicale, in quanto come ovvio al processo di compressione deve essere abbinato un
algoritmo di decompressione dedicato. La trattazione non Ł approfondita, poichØ molte parti
derivano in modo diretto dal sistema di compressione
Nel corso del lavoro si Ł sempre cercato di tenere presente la realizzazione pratica dell algoritmo;
questa scelta ha, a volte, limitato le possibilit  di progetto come quella di non poter lavorare nel
dominio del tempo (come, invece, inizialmente si era fatto) e di dover introdurre i blocchi che
effettuano la FFT e la FFT
-1
.
I risultati di queste considerazioni sono esposte nell Appendice A.
Questo capitolo Ł il risultato della prima fase del lavoro in cui si pensava ancora di voler realizzare
un prototipo del sistema. I costi ci hanno poi costretto ad accantonare l idea ed alcune delle parti
che erano state lasciate parzialmente incomplete non sono state piø approfondite.
Nell Appendice B sono riportati alcuni concetti di acustica classica, indispensabili per poter
comprendere a fondo il SANC.
Si Ł inoltre cercato di simulare l intero algoritmo o alcune sue parti con alcuni programmi
disponibili quali SPICAD ed HP VEE.
I risultati piø interessanti sono stati ottenuti con quest ultimo.
Simulazioni concrete si sono effettuate per le reti neurali con il programma per PC NeuralWork che
ha fornito risultati molto soddisfacenti. I risultati sono esposti nell Appendice C.
In questa compaiono anche i dati che sono stati utilizzati per l istruzione della rete e le
caratteristiche di ciascuna rete. Le tabelle di istruzione non sono state inserite tutte in quanto alcune
sono di dimensioni eccessive.
,,5LQJUD]LDPHQWL
Fare un ordine di ringraziamenti Ł sempre spiacevole comunque da qualcuno bisogner  pur iniziare.
I primi ringraziamenti vanno senz altro al Prof. Santomauro e all Ing. Giancarlo Storti Gajani
relatore di questa tesi, che ha seguito il lavoro con estrema disponibilit  ed ha accettato le incursioni
nel suo ufficio anche nelle ore piø impensabili.
Ringraziamenti vanno al Prof. Giorgio Padovini, per la disponibilit  mostrata nel mettere a
disposizione la sua manualistica.
Ringraziamenti vanno sicuramente anche ai miei genitori e alla mia ragazza (Nadia Antonelli) che
hanno sopportato le mie ire e il mio nervosismo quando il lavoro sembrava non volgere verso la
soluzione auspicabile.
Contenuto                                                                                                                                Prefazione
9
Non posso poi certo dimenticare tutti quelli che mi hanno aiutato nella realizzazione fisica di tutto
questo scritto: mia sorella, per le centinaia di fotocopie, Paola Sipione per le digitalizzazioni delle
immagini, Claudio Antonelli per il «prestito» di alcune parti del PC nei momenti di difficolt 
«Hardware», Jacopo Baldioli per alcuni consigli sulla veste grafica, Giuseppe Reale per le ricerche
sui suoi Data Book quando io ne ero ancora sprovvisto e tutti quanti gli altri avessi dimenticato.
GRAZIE di cuore a tutti.
Capitolo1                                                                                                                      Concetti generali
10
&DSLWROR
&RQFHWWLJHQHUDOL
,QWURGX]LRQHDLPHWRGLGLFRPSUHVVLRQH
Fin dagli anni sessanta l interesse per i metodi di compressione dei dati Ł stato notevole.
La necessit  di avere dei sistemi di comunicazione sempre piø efficienti, ha spinto e spinge tuttora i
ricercatori a notevoli sforzi, affinchØ sia possibile l’utilizzo di mezzi trasmissivi sempre migliori e
tecnologie di archiviazione dei dati sempre piø capaci.
E  a questo punto che entrano in gioco i sistemi di compressione dei dati.
Nelle realizzazioni pratiche, molte volte, pu  essere piø economico utilizzare un algoritmo che
riduce le dimensioni del messaggio da trasmettere, o archiviare, che non realizzare un sistema di
elaborazione e trasmissione piø veloce od un supporto di registrazione piø capiente.
Queste tecniche, poi, sono indispensabili, se i mezzi di comunicazione sono le linee telefoniche.
Nessun altro sistema di comunicazione Ł cos  ramificato e raggiungibile da ogni angolo del mondo,
ma, come inconveniente si hanno le limitazioni della banda di canale, che ne precludono la
possibilit  di inviare dei dati ad elevata qualit 
1
.
In questo capitolo faremo una breve introduzione sulle tecniche di compressione dati con perdita e
senza perdita; dei loro impieghi e dei risultati che si possono ottenere.
Faremo un analisi introduttiva sulle tecniche di modellamento e di codifica. Esamineremo almeno
superficialmente gli algoritmi di Ziv e Lempel per la compressione senza perdita.
Ci occuperemo, infine, delle tecniche di compressione con perdita.
Questo primo lavoro sar , in ogni modo, solo propedeutico per lo sviluppo di un sistema di
compressione per campioni musicali realizzato con reti neurali, argomento su cui verte questa tesi.
,GXHWLSLGLFRPSUHVVLRQH
Le tecniche di compressione sono suddivise in due grosse famiglie:
- TXHOOHFRQSHUGLWD
- TXHOOHVHQ]DSHUGLWD
La  compressione con perdita permette di avere grossi fattori di riduzione rispetto alle dimensioni
iniziali dell informazione, in cambio, per  di un peggioramento della qualit ; questa tecnica
fornisce prova della sua funzionalit  soprattutto se applicata alle immagini grafiche e alla
digitalizzazione del suono.
In queste tecniche il livello di qualit  varia da metodo a metodo; grosse compressioni corrispondono
come ovvio ad accuratezze basse.
All inizio, la compressione con perdita veniva implementata usando delle architetture hardware
dedicate. In seguito sono stati sviluppati dei programmi in grado di «girare» su dei computer gestiti
da microprocessori non specifici.
Questi metodi sono comunque impiegabili solo se le velocit  di elaborazione richieste non sono
eccessivamente elevate.
                                                          
1
 Per un’introduzione sul sistema telefonico vedi Carassa [1] Cap. 7.
Capitolo1                                                                                                                      Concetti generali
11
Le tecniche senza perdita, consistono, invece, nel generare un duplicato esatto della sequenza
d’ingresso dopo un ciclo di compressione ed espansione.
Questi tipi di tecniche, sono usate soprattutto nei PC, per l archiviazione di dati sull HD. Infatti, in
questi casi la perdita anche di un solo bit pu  provocare l’irrecuperabilit  dell’intero documento.
0RGHOODPHQWRHFRGLILFD
Con l espressione FRPSUHVVLRQH GHL GDWL, s’intende il prelevamento della sequenza di simboli
d’ingresso e la sua trasformazione in un altra, mediante un opportuno codice. Se il risultato della
codifica Ł una sequenza piø corta di quella originale, si Ł ottenuta una compressione.
La compressione si basa su un PRGHOODPHQWR e su unaF GLILFD. l modellamento e la codifica sono
due cose differenti.
Di solito, ci si riferisce con il termine di FRGLILFD all intero processo di compressione, invece di
considerare la codifica come solo una parte di questa.
Infatti la decisione di fornire in uscita una certa codifica ad un certo simbolo o ad una sequenza di
simboli dipende dal modello considerato.
Possiamo quindi definire il modellamento nel seguente modo:
,OPRGHOODPHQWRqXQDVHPSOLFHFROOH]LRQHGLGDWLHUHJROHXVDWLSHU
SURFHVVDUHLVLPEROLG
LQJUHVVRHGHWHUPLQDUHLFRGLFLG
XVFLWD
La codifica pu  essere, invece, definita nel seguente modo:
/DFRGLILFDqODWUDVIRUPD]LRQHGLXQDVHTXHQ]DLQXQ¶DOWUDOHJDWHIUD
ORURGDOPRGHOODPHQWR
/HEDVLGHOODFRPSUHVVLRQH
La compressione dei dati Ł una branca della Teoria dell Informazione
2
 perchØ essa Ł in relazione
con la «ridondanza».
In un messaggio possono essere presenti delle informazioni ridondanti. Ad esempio il calcolo di
3+4=7 Ł un’informazione ridondante in quanto Ł gi  noto che 3+4 vale 7. Al numero 7 verranno
associati dei bit in modo analogo a quanto viene fatto per le informazioni non superflue.
L’eliminazione di questa parte di dati extra, permette d’ottenere una riduzione del messaggio.
Nella teoria dell informazione si usa il termine HQWURSLD come una misura di quanta informazione Ł
codificata nel messaggio; piø Ł alta l entropia maggiore Ł l informazione contenuta.
L entropia di un simbolo Ł il logaritmo della sua probabilit  con il segno cambiato; se poi il segnale
contiene informazioni in bit, il logaritmo Ł in base due:
()1XPHUR GL ELW /RJ 3UREDELOLWj

=− (1.1)
L entropia di un messaggio completo Ł la somma di tutte le singole entropie.
Vediamo qual Ł il significato fisico dell entropia. Consideriamo una lettera che compare in questo
testo, per esempio la «a». Ipotizziamo che essa sia presente su 82736 caratteri 10342 volte, in altre
parole ha una probabilit  di:
                                                          
2
 Per uno studio approfondito della teoria dell informazione vedi Bellini [2] e Haykin [3].
Capitolo1                                                                                                                      Concetti generali
12
3UREDELOLWj==




(1.2)
L informazione contenuta nel carattere sar  allora di 3 bit (-Log
2
 (1/8) =3).
Considerando, quindi la sequenza «aaaaa», si avr  un contenuto entropico pari a 15 bit.
Usando uno standard ASCII
3
 a 8 bit per carattere, per i 5 simboli si devono usare 40 bit, mentre
l informazione effettiva Ł di soli 15 bit; i 25 bit di differenza possono potenzialmente essere usati
per la codifica della compressione.
Un fatto importante da mettere in evidenza Ł che l entropia, a differenza di quello che avviene in
termodinamica, non pu  essere considerata come un numero assoluto per l informazione contenuta
nel messaggio.
Cambiando il modello, infatti, cambia la probabilit  di uno stesso simbolo.
Alla luce di questi fatti, senza approfondire il problema ulteriormente, possiamo affermare che per
avere la compressione migliore abbiamo bisogno del modello che predice il simbolo con la piø alta
probabilit .
Infatti un simbolo che ha alta probabilit  ha un basso contenuto informativo e necessita di pochi bit
per la codifica.
/DFRGLILFD
La compressione dei dati codifica i simboli con il numero «esatto» di bit di «informazione»
contenuti nel simbolo.
Un carattere «a» avente solo tre bit d’informazione, sar  codificato proprio con tre bit. Un carattere
«r» con 12 bit d’informazione, sar  codificato con 12 bit.
La codifica dei caratteri con il metodo ASCII, invece, non Ł chiaramente la migliore, in quanto
s’introducono degli errori in entrambe le direzioni con molte delle codifiche troppo lunghe o troppo
corte.
Le soluzioni a questo problema sono i codici di Shannon - Fano e Huffman.
Il codice di Huffman ottiene la minor ridondanza possibile per un fissato set di codici. Questo non
vuol dire per  che il codice Huffman sia il miglior metodo di codifica.
Il problema dei codici di Huffman e Shannon - Fano, Ł che essi usano un numero intero di bit in
ogni codifica. Per esempio, se l entropia Ł 2,5 bit la codifica avverr  con 2 o 3 bit e non 2,5.
Il codice Huffman resta in ogni caso il miglior metodo che usa una codifica con un numero di bit
intero.
La Tabella 1 mostra un esempio del codice Huffman.
                                                          
3
 Per approfondimenti sulla codifica ASCII vedere il testo di Bellafemina al Par. 8.4 [4].
Capitolo1                                                                                                                      Concetti generali
13
6LPEROR&RGLILFDGL+XIIPDQ
E 100
T 101
A 1100
I 11010
................. ......................
X 01101111
Q 01101110001
Z 01101110000
7DEHOOD(VHPSLRGLFRGLILFDGL+XIIPDQ
I simboli con una maggiore probabilit  hanno una codifica con un numero di bit minore in quanto il
contenuto d’informazione Ł piø basso
4
.
Altri codici, derivanti da quello di Huffman, si sono sviluppati creando numerose variet  di
algoritmi. Questi ultimi hanno dominato i metodi di codifica fino agli anni ottanta, vale a dire fino a
quando il costo di CPU, sempre piø veloci, non Ł diventato concorrenziale rispetto ai miglioramenti
degli algoritmi stessi.
Un particolare algoritmo che merita di essere ricordato Ł la codifica Aritmetica.
Questa codifica non produce un singolo codice per ogni simbolo, ma un codice per l intero
messaggio ed Ł molto piø complicata del codice Huffman. Ogni simbolo sommato al messaggio in
modo incrementale modifica il codice d’uscita.
Questo Ł un vantaggio perchØ l effetto di ogni simbolo sull uscita pu  essere un numero frazionario
di bit invece di un numero intero. Cos  se l entropia del carattere «a» Ł 2,5 bit Ł possibile sommare
esattamente 2,5 bit al codice d’uscita.
,OPRGHOODPHQWR
La compressione senza perdita Ł realizzata con due differenti tipi di modelli:
6WDWLVWLFL
%DVDWLVXXQGL]LRQDULR
Il modellamento statistico legge l ingresso e codifica un simbolo alla volta usando la probabilit  con
cui quel carattere Ł apparso.
Il modellamento basato su un dizionario usa un singolo codice che rimpiazza stringhe di simboli; in
pratica si preoccupa di ridurre il senso.
0RGHOODPHQWRVWDWLVWLFR
La piø semplice forma di modellamento statistico
5
 usa una tavola statica di probabilit .
Questo metodo non ha avuto un grosso successo, a causa del fatto che nei primi tempi della teoria
dell informazione, il costo di una CPU per l analisi dei dati e la costruzione dell albero di Huffman
(cioŁ la tabella) era elevato.
                                                          
4
 Maggiori dettagli sulla codifica di Huffman sono forniti nel paragrafo 1.8
5
 Per approfonditi studi vedere [5] Pag. 167-188.
Capitolo1                                                                                                                      Concetti generali
14
I blocchi rappresentativi dei dati sono analizzati uno per volta, dando in una tabella il conteggio
della frequenza del carattere. I dati d’ingresso, costruito l albero della codifica / decodifica, sono
immagazzinati in base ai codici dell albero stesso.
Il programma di compressione ha accesso a questo modello statistico e comprimer  i dati mediante
l impiego delle percentuali statistiche.
Usando un modello statistico universale si hanno per  delle limitazioni.
Infatti, se si ha in ingresso una sequenza non accumulata statisticamente in precedenza, il rapporto
di compressione Ł degradato a tal punto che l uscita pu  anche essere piø grande dell ingresso.
La costruzione della tabella di Huffman per ogni file Ł, quindi, un vantaggio, se la tabella Ł adattata
unicamente a quel file in modo da avere la migliore compressione possibile.
E  quindi opportuno avere un modello adattativo.
Uno schema generale di compressione adattativa Ł presentato in Figura 1.
)LJXUD6FKHPDGLFRPSUHVVLRQHDGDWWDWLYD
Il seguente schema rappresenta, invece, la decompressione:
)LJXUD6FKHPDGLGHFRPSUHVVLRQHDGDWWDWLYD
Maggiori dettagli sul modello adattativo sono reperibili nel lavoro di Mark Nelson [5]
0RGHOODPHQWRFRQVFKHPDDGL]LRQDULR
6
I modelli statistici, in genere, codificano un singolo simbolo alla volta, leggendolo, analizzandolo e
fornendo in uscita una sola codifica.
Il modellamento con schema a dizionario funziona in modo diverso da quello statistico, infatti,
legge dei dati d’ingresso e «guarda» se essi compaiono in un elenco.
Data una determinata sequenza, rintracciata in questo elenco, anzichØ fornire il codice della
sequenza stessa in uscita, l algoritmo produce un indice che il dizionario ha associato alla stringa di
caratteri.
,OFRGLFH+XIIPDQ
7
HGDOWUR
                                                          
6
 Vedi [5] Pag. 219-231
7
 Per un’analisi dettagliata del codice Huffman ci si pu  riferire al testo [5] da Pag. 29 a Pag. 148.
Capitolo1                                                                                                                      Concetti generali
15
La codifica di Huffman Ł una tecnica di compressione dei dati statistica, la quale esegue una
riduzione della dimensione del messaggio usando i simboli di un alfabeto.
La codifica di Huffman Ł un esempio di codice ottimo, nel caso in cui le probabilit  di tutti i simboli
sono una potenza di 1/2.
Un codice di Huffman Ł costruito in questo modo:
• 6LSRQJRQRWXWWLLVLPEROLLQRUGLQHGLSUREDELOLWj
• 6L FRPELQDQR L GXH VLPEROL GL SL EDVVD SUREDELOLWj SHU IRUPDUH XQ QXRYR
VLPEROR HYHQWXDOPHQWH FRVWUXLUHPR XQ DOEHUR ELQDULR GRYH RJQL QRGR q OD
SUREDELOLWjGLWXWWLQRGLVRWWRDGHVVR
• 6LWUDFFLDXQVHQWLHURGLRJQLIRJOLDDQQRWDQGRODGLUH]LRQHGLRJQLQRGR
Per una data frequenza di distribuzione, ci sono molti possibili codici di Huffman, ma la lunghezza
della compressione totale sar  la stessa.
E  possibile definire un albero canonico di Huffman che equivale a prendere una di queste
possibilit .
Ogni albero canonico pu  poi essere rappresentato in modo molto sintetico, trasmettendo solo la
lunghezza.
Vediamo un po  piø in dettaglio.
Consideriamo una sorgente che emetta sequenze binarie con 3 e 3 .
Sia per esempio:
000001010000010100000100000010100000011100011000
Si vuole codificare questa sequenza in modo da avere un messaggio complessivamente piø corto.
E  evidente, poi, che il messaggio codificato deve poter essere decifrato.
Una possibile soluzione potrebbe essere quella di prendere coppie di messaggi elementari.
Ad esempio:
 0HVVDJJLR &RGLILFD
00 0
xx 1xx
7DEHOOD(VHPSLRGLFRGLILFDHOHPHQWDUH
La coppia di 0, che compare mediamente 81 volte su 100
8
, si traduce in uno 0, mentre ogni coppia
diversa da 00 si riporta fedelmente con un 1 davanti.
Per esempio la sequenza 00 00 00 10 00 10 00 00 01 00  prende la forma
0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 .
Su messaggi molto brevi pu  succedere di avere il codice d’uscita piø lungo di quello sorgente, ma
su messaggi lunghi si hanno dei reali benefici.
Vediamo quanto possiamo risparmiare in media.
La lunghezza media del singolo messaggio elementare in uscita dal codificatore Ł:
()Q %LW=⋅ +⋅ ⋅ + ⋅ + ⋅ =⋅ +⋅ = + =               (1.3)
L efficienza
9
 Ł quindi di 1,38/2=0,69 Bit / messaggio.
                                                          
8
 Questa affermazione deriva da considerazioni puramente statistiche.
9
 Per maggiori dettagli sul numero medio di bit per messaggio e l efficienza si pu  esaminare il testo indicato in [6].
Capitolo1                                                                                                                      Concetti generali
16
 0HVVDJJLR &RGLILFD
00 0
01
10
10 110
11 111
7DEHOOD0LJOLRUDPHQWRGHOOHSUHVWD]LRQLLQXQDFRGLILFDHOHPHQWDUH
L uno, posto in evidenza, (seconda colonna / seconda riga) Ł ridondante, quindi, si pu  evitare di
rappresentarlo usando la codifica di Tabella 4.
 0HVVDJJLR&RGLILFD
00 0
01 10
10 110
11 111
7DEHOOD(OLPLQD]LRQHGHOOHLQIRUPD]LRQLULGRQGDQWL
In questo modo il numero medio di bit per messaggio Ł di:
( ) ( ) ( )
n=1 0,9 0,9
= 0,81+ 2 0,09 + 3 0,1 = 0,81+ 0,18 + 0,3 = 1,29
Bit
messaggio
⋅⋅+⋅⋅+⋅⋅+⋅=
⋅⋅
      
(1.4)
L efficienza Ł quindi di 1,29/2 = 0,645 Bit / messaggio.
Con questo tipo di codifica la sequenza 00 00 01 00 11 10 00 00 00 10  diventa
0 0 10 0 111 110 0 0 0 110 .
Con questo tipo di codifica a coppie si pu  dimostrare che non si pu  far meglio di 0,645 Bit /
messaggio.
Per la dimostrazione ricorriamo al codice Huffman, che Ł il codice binario ottimo in tema di
messaggi non equiprobabili.
I messaggi da codificare sono:
 0HVVDJJLR3UREDELOLWj
00 0,9 0,9 =0,81
01 0,9 0,1 = 0,09
10 0,9 0,1 = 0,09
11 0,1 0,1 = 0,01
7DEHOOD3UREDELOLWjGHOFRGLFH+XIIPDQDFRSSLH
Il codice Huffman si costruisce nel seguente modo.
Si ordinano, come primo passo, i messaggi 00, 01, 10 e 11 in modo decrescente secondo la loro
probabilit . Si otterr , quindi:
 0HVVDJJLR 3UREDELOLWj
00 0,81
Capitolo1                                                                                                                      Concetti generali
17
01 0,09
10 0,09
11 0,01
7DEHOOD2UGLQDPHQWRVHFRQGRSUREDELOLWjGHFUHVFHQWHGHOOHFRSSLHGLELW
Si attribuisce 0 e 1 rispettivamente al penultimo e ultimo della lista.
Si avr  ora:
3UREDELOLWj0HVVDJJLR&RGLILFD
0,81 00
0,09 01
0,09 10 0
0,01 11 1
7DEHOOD3ULPRSDVVRGHOODFRGLILFDGL+XIIPDQDFRSSLH
Costruisco un nuovo ente unione di 10 e 11 ed avente come probabilit  la somma delle probabilit :
10 ∪ 11 P = 0,09 + 0,01 = 0,1
Il nuovo ente 10 ∪ 11 cade fra 00 e 01 poichØ P(10 ∪ 11) = 0,1 > P(01) = 0,09.
Attribuendo ancora 0 e 1 al penultimo e ultimo ottengo:
3UREDELOLWj0HVVDJJLR&RGLILFD
0,81 00
0,1
10 ∪ 11
0
0,09 01 1
7DEHOOD6HFRQGRSDVVRGHOODFRGLILFDGL+XIIPDQDFRSSLH
La situazione attuale Ł la seguente:
 0HVVDJJLR &RGLILFD
00
01 1
10 00
11 01
7DEHOOD6LWXD]LRQHGHOODFRGLILFDGL+XIIPDQGRSRSDVVL
Si costruisce il gruppo 10 ∪ 11 ∪ 01 con probabilit  P(10 ∪ 11 ∪ 01) = 0,1 + 0,09 = 0,19 e si
ottiene:
3UREDELOLWj0HVVDJJLR&RGLILFD
0,81 00 0
0,19
10 ∪ 11 ∪ 01
1
7DEHOOD7HU]RSDVVRGHOODFRGLILFDGL+XIIPDQDFRSSLH
La situazione finale Ł:
Capitolo1                                                                                                                      Concetti generali
18
 0HVVDJJLR &RGLILFD
00
01 11
10 100
11 101
7DEHOOD6LWXD]LRQHFRQFOXVLYDGHOODFRGLILFDGL+XIIPDQDFRSSLH
L efficienza di questa codifica Ł:
( ) ( ) ( ) ( )
[]
Q 3 3 3 3
     %LW
  
     
⋅+⋅+⋅ + =
⋅⋅
(1.5)
Ci  equivale ad una efficienza di 1,29/2 = 0,645 Bit/messaggio.
Questo Ł un codice a lunghezza variabile, per  su 1000 bit di ingresso ne ho mediamente 650 di
uscita.
E  evidente che la «memoria tampone« e il canale devono essere in grado di trattare il flusso di dati.
Un altro modo di codificare Ł quello di suddividere il messaggio non in coppie, ma genericamente
in un gruppo di N bit.
Consideriamo per esempio un gruppo di N bit; se sono 0000000....0 allora lo codifico con 0; se Ł un
qualunque altro gruppo xxxxxxx xK  lo codifico con 1xxxxxxx xK .
Con questa codifica ho che la lunghezza media Ł:
( ) ( ) ( )
( )
Q  1    1 1   
 1   1 1 1 1
1
11 1
     
     
+⋅ =++⋅+ =
⋅=+ − =+−⋅
(1.6)
Dividendo per N si ottiene l efficienza:
ε ==+−
Q
1 1
1


 (1.7)
calcolando la derivata si trova il massimo:
G
GQ 1
1
1
1
1
1
1
1
ε
=−⋅ =
=
=
=
−
−
−

 











(1.8)
da cui si pu  ricavare l efficienza massima:  ε= 0,5939 Bit/messaggio.
Se si usa N=3 si ha ε = 0,604 Bit/messaggio, mentre con Huffman a terzine si ha ε = 0,532
Bit/messaggio.
 0HVVDJJLR &RGLILFD
Capitolo1                                                                                                                      Concetti generali
19
000 0
001 100
010 101
011 11100
100 110
101 11101
110 11110
111 11111
7DEHOOD&RGLILFDGL+XIIPDQDWHU]LQH
Un altro metodo di codifica Ł quello di scomporre il messaggio complessivo in messaggi a
lunghezza variabile, per esempio: 1, 01, 001 e 000.
Si codifica in uscita in modo da avere un numero fisso di bit, come si pu  vedere dalla Tabella 13.
 0HVVDJJLR &RGLILFD
11
01 01
001 10
000 00
7DEHOOD&RGLILFDFRQFRGLFLGLOXQJKH]]DILVVD
Cos  la sequenza 000 01 01 000 1 01 1 000 000  diventa 00 01 01 00 11 01 11 00 00 .
L efficienza di questa codifica vale:
( )
ε =
⋅+⋅ +⋅ +
=

      

 

%LW
PHVVDJJLR
(1.9)
Se questi messaggi si codificano alla Huffman si ottiene:
 0HVVDJJLR &RGLILFD
11
01 100
001 101
000 0
7DEHOOD&RGLILFDFRQ+XIIPDQGLVHTXHQ]HGLOXQJKH]]DYDULDELOH
con una efficienza di:
ε =
⋅+⋅+⋅
⋅+⋅ +⋅
=
     
  


 

%LW
PHVVDJJLR
Il risultato ottenuto Ł molto buono.
Si Ł quindi partiti da 0,7 Bit/messaggio e si Ł arrivati a 0,51 Bit/messaggio.
Shannon ha dimostrato che esiste un minimo dell efficienza che nel caso di P(0)=0,9 P(1)=0,1 e
vale 0,469.
Capitolo1                                                                                                                      Concetti generali
20
,O&RGLFHDULWPHWLFR
Potrebbe sembrare che i codici di Huffman e Shannon - Fano siano perfetti per la compressione dei
dati.
Questo non Ł in genere vero. Abbiamo gi  visto in precedenza che questi codici, funzionano al
meglio delle loro prestazioni se la probabilit  dei simboli Ł una potenza intera di 1/2.
La tecnica di codifica aritmetica
10
 non ha invece questa restrizione. Essa raggiunge gli stessi effetti
trattando il messaggio come una singola unit , ottenendo il valore di entropia teorico.
La codifica aritmetica lavora rappresentando un numero per mezzo di un intervallo di numeri interi
fra 0 e 1.
Appena il messaggio cresce, l intervallo che lo rappresenta diventa sempre piø piccolo ed il numero
di bit che lo rappresenta si incrementa.
In seguito i simboli nel messaggio riducono questo intervallo in accordo con la probabilit  del
simbolo.
Per fare un esempio di codifica aritmetica, consideriamo due simboli X e Y di probabilit  0.66 e
0.33.
Per codificare un messaggio con le caratteristiche dette esaminiamo il primo simbolo: se esso Ł una
X scegliamo la partizione piø bassa della prima colonna della tabella, se Ł una Y scegliamo la
partizione piø alta.
Continuando in questo modo per 3 simboli otteniamo il codice di lavoro mostrato sulla destra del
diagramma.
&RGLFH
YYY <- 31/32 11111
8/9         YY YYX <- 15/16 1111
Y YXY <- 14/16 1110
2/3 YX YXX <- 6/8 110
16/27   XYY <- 10/16 1010
XY
4/9 XYX <- 4/8 100
8/27     XXY <- 3/8 011
X
XX
XXX <- 1/4 01
1
7DEHOOD(VHPSLRGLFRGLILFDFRQFRGLFHDULWPHWLFR
Questo codice pu  essere ricavato semplicemente prendendo un’appropriata localizzazione
dell intervallo per quel particolare set di simboli e trasformarlo in una frazione binaria. E’
necessario, inoltre, nei casi pratici, sommare uno speciale simbolo di fine che in questo esempio non
Ł rappresentato.
In questo caso, il codice aritmetico non Ł completamente efficiente, a causa della brevit  del
messaggio. Con messaggi piø lunghi si possono avere efficienze anche del 100%.
Questa tecnica di codifica Ł particolarmente efficiente.
Con questa possiamo costruire un modello che pu  essere usato come encoder. Il piø semplice Ł
costituito da una tabella di associazione fissa. Per esempio le lettere che compaiono di frequente
nella lingua inglese (o italiana) possono essere usate per ottenere la probabilit . Un miglioramento
                                                          
10
 Il codice aritmetico Ł descritto in modo approfondito nel testo [5] da Pag. 123 a Pag. 148.
Capitolo1                                                                                                                      Concetti generali
21
di questa tecnica usa un «modello adattativo», cioŁ una tecnica che aggiorna la frequenza di
simbolo dopo ogni nuovo simbolo codificato.
Si possono ottenere dei risultati ancora migliori considerando la probabilit  di intersimbolo . Il
miglior compressore che usa questo metodo oggi Ł il DMC (Dinamic Markov Coding).
Il DMC
11
 parte con un modello di Markov di ordine zero e gradualmente estende questo modello
iniziale alle compressioni successive.
Come mai allora se queste tecniche di compressione lavorano cos  bene non sono ancora
universalmente utilizzate? A parte il fatto che sono recenti e non sono ancora entrate nell uso
comune, ci sono anche altri motivi; il fatto Ł che richiedono grosse risorse computazionali sia in
termini di potenza della CPU che di memoria.
*OLDOJRULWPLGL=LYH/HPSHO
La maggior parte degli algoritmi di compressione usano il modellamento statistico.
Nel 1977 e nel 1978, Jacob Ziv e Abraham Lempel descrissero due algoritmi di compressione
usando un dizionario adattativo
12
.
Questi due algoritmi chiamati LZ77 e LZ78 furono la scintilla per lo sviluppo di una enorme
quantit  di metodi basati sul «dizionario» e vengono comunemente chiamati «compressori
sostituzionali».
L idea base di un compressore sostituzionale Ł quella di rimpiazzare un pezzo di una particolare
frase o un gruppo di byte in una sequenza di dati, con un riferimento a quel pezzo di frase.
Nei due paragrafi seguenti Ł esposto il loro principio di funzionamento.
/=
Questo algoritmo Ł relativamente semplice.
LZ77 basa il suo funzionamento sugli ultimi N byte di dati visti. Una frase, gi  incontrata, si
sostituisce, in uscita, con una coppia di valori, corrispondente alla posizione della stessa nel buffer
dei dati e dalla sua lunghezza.
Il compressore muove una «finestra» di dimensioni fisse «sopra» i dati (generalmente chiamata
«sliding window» finestra scorrevole). Il dizionario per la compressione consiste, quindi, in stringhe
poste all interno di questa finestra, alle quali sono associate una posizione e una lunghezza. Un
programma di compressione di files potrebbe usare, per esempio, un dizionario di 4 Kb. Ogni volta
che il confronto fra la sequenza d’ingresso coincide con una di quelle contenuta nel dizionario, Ł
codificato il puntatore.
Il piø comune algoritmo deriva dallo schema LZSS descritto da James Storer e Thomas Szymansky
nel 1982.
In questo, il compressore usa una finestra di N byte e un «Lookahead buffer»,  il cui contenuto Ł
confrontato con gli elementi della finestra per vedere se c Ł una coincidenza.
Un esempio di algoritmo di confronto Ł cos  rappresentato:
WHILE (LookAheadBuffer non vuoto)
                                                          
11
 Approfondimenti sulle DMC e sul codice aritmetico sono disponibili anche via Internet contattando Peter Gutman
all indirizzo <[email protected]>
12
 La discussione di un algoritmo per un metodo adattativo, basato su uno schema a dizionario, si trova in [5] da Pag.
221 a Pag. 223.