Modelli specifici per compressori dati

26 Nov. 98 (nota 30)

N.B. Per motivi di occupazione le immagini di questa pagina sono in formato Png, leggibile dal Netscape4, ma non da Internet Explorer 3.

Un compressore opera su un file dati idealmente in due stadi: con un modellatore e un codificatore entropico. Il modellatore spesso è specifico per un tipo di dati, mentre il secondo è generale. Lo scopo del modellatore è quello appunto di fare un modello dei dati, ed usarlo per prevedere il futuro, cioè il byte successivo, dati tutti i precedenti nel file. I compressori entropici lavorano basandosi sul fatto che si risparmia bit se si spediscono al ricevente codici più corti per i simboli più frequenti. Il ricevente contiene gli stessi due blocchi di modellatore e codificatore entropico.
Il modellatore calcola la differenza, l'errore, fra la sua previsione e il file effettivo, e la spedisce al codificatore. In ricezione lo stesso modellatore è in grado di ricostruire i dati originali, basandosi sul dato iniziale e sulle differenze. Se la previsione era ben fatta la maggior parte dei simboli dell'input era stata prevista, e la sequenza differenza sarà composta quasi solo di piccoli errori. Dato che stiamo lavorando in digitale, piccoli errori sono necessariamente di pochi tipi, quindi il segnale passato al codificatore conterrà pochi simboli ad alta probabilità e alcuni, i grandi errori, poco probabili. Questo è proprio quello che ci vuole per una buona compressione entropica...

Facciamo un esempio molto semplice, con audio digitale mono 8bit/camp., frequenza campionamento di 16Khz, 1.63s della mia voce che pronuncia "I think, therefore I am", per un totale di 26089 campioni (byte). Di seguito eccone l'oscillogramma, lo spettrogramma e l'istogramma di frequenza (cliccandoli si può udire).

 Oscillogramma del segnale originale
Spettrogramma del segnale originale
Istogramma di frequenza del segnale originale
Prendendo i campioni a coppie e utilizzandili come coordinate di punti sul piano cartesiano, si può osservare la correlazione di primo ordine fra i dati:
Diagramma di correlazione del segnale originale
Abbiamo ottenuto un sigaro molto stretto, questo significa che se un valore è alto il successivo sarà in media alto, se è basso il successivo sarà basso, ecc.
Come ho detto prima i modellatori entropici, quale è quasi puro ZipMagic, lavorano sull'istogramma delle frequenze dei simboli (byte) in ingresso. Esse devono essere le più sbilanciate possibili per ottenere migliore compressione. ZipMagic riduce il segnale di partenza a 15898 byte (61% dell'originale).
Applicando al segnale di partenza una differenziazione, cioè togliendo da ogni campione il valore del suo precedente otteniamo una specie di derivata discreta del segnale:
 Oscillogramma del segnale differenziato
Spettrogramma del segnale differenziato
Istogramma di frequenze del segnale differenziato

Come si vede l'istogramma è più piccato, e il suono risulta meno "pieno", diefetta di basse frequenze, ma perfettamente intelleggibile. Sul piano la correlazione lineare è ancora presente, ma molto diminuita:

Diagramma di correlazione del segnale differenziato
Da questo segnale è facile ricostruire l'originale. Lo ZipMagic lo riduce a 11827 byte. (45% dell'originale, 74% del precedente). E' evidente il motivo per cui parecchi compressori lossless oggi possiedono modelli, specifici per segnali audio o multimediali in genere.
Un programma specifico per la compressione lossless audio, il WaveArc, utilizza metodi simili, ma più sofisticati, e porta il file a 7579 byte.

Nota ai grafici: per eseguire spettrogrammi e oscillogrammi ho utilizzato Cool Edit Pro 1, poi ho ridotto le loro dimensioni spaziali e numero di colori. Gli istogrammi sono una rielaborazione di quelli del Paint Shop Pro 5, mentre i diagrammi di correlazione sono ottenuti con Exel 7, usando le prime tremila coppie di campioni dei file, con l'ausilio di due elementari programmi T. Pascal, necessari per convertire i byte in forma di file testuale di coppie e per differenziare un file di byte (stando attenti agli overflow).

Torna alla Home Page