 |
Questa pagina è stata trascritta e formattata, ma deve essere riletta. | |
| 88 | Codifica numerica del segnale audio |
ghezza di quelli meno frequenti. Non disponendo della distribuzione della probabilità dei simboli, si può mantenere fissa la lunghezza delle parole di codice, ma associando ed esse blocchi di simboli di dimensione crescente in funzione della loro frequenza di emissione. In il numero medio di bit per simbolo, quindi, si riduce tanto più quanto maggiore è la possibilità di avere ripetizioni di lunghe sequenze di simboli.
Un algoritmo di compressione adattativa particolarmente diffuso è l’algoritmo di Ziv-Lemplel (LZ). Essendosi diffuso per applicazioni essenzialmente legate alla compressione di informazioni su memoria di massa, in tale algoritmo le sequenze a lunghezza variabile di simboli vengono dette “stringhe” e la dimensione dei codici, legata alla lunghezza delle parole nei sistemi di elaborazione, sono tipicamente a 12 o 16 bit.
Tale algoritmo si basa sulla realizzazione di una tabella di conversione, inizializzata per contenere, come stringhe iniziali, tutti i simboli generabili dalla sorgente (es.: tutti i possibili caratteri ASCII per un file di testo), presi singolarmente. Tale algoritmo di compressione si basa sulla proprietà per la quale ciascuna stringa presente nella tabella ha un prefisso “w” ottenuto eliminando il simbolo terminale “K” (estensione), anch'esso nella tabella.
Durante la compressione, vengono costruite stringhe di dimensioni crescenti ordinando sequenzialmente i simboli in ingresso (fig. 3.3). Contemporaneamente si controlla che la stringa w che si viene via via formando sia compresa in tabella, nel qual caso tale procedura continua. Nel momento in cui, ricevendo il simbolo K, la stringa wK non risulta presente nella tabella, si eseguono i seguenti passi:
- viene emesso il codice relativo alla stringa w, che rappresenta la più lunga delle stringhe già tabellate contenuta nella stringa da codificare;
- la stringa wK viene inserita nella tabella, assegnando ad essa un nuovo codice;
- K diventa il simbolo iniziale di una nuova stringa.
Analizzando le prestazioni di tale algoritmo, si nota come nella fase iniziale viene eseguita, in realtà, un’espansione del flusso (dato che singoli simboli vengono codificati in codici di dimensioni maggiori). Successivamente, però, ciascun codice emesso sarà via via relativo a stringhe di dimensioni crescenti, con un’efficienza che aumenta man mano che il processo di compressione procede.
