Paolo Guccini

Impossibile non é per sempre

LA COMPRESSIONE DATI

Ai suoi albori il personal computer disponeva come supporto di memorizzazione dati il solo floppy disk di tipo single side single density con una capacità di circa 180 KByte.
Il suo successo commerciale ha consentito alle industrie di convogliare ingenti investimenti con evidenti risultati: oggi un nuovo PC dispone di una potenza di calcolo incredibilmente maggiore e di dischi fissi di almeno 850 megabyte con prezzi in costante diminuzione. A seguito di queste ed altre considerazioni si potrebbe considerare il discorso della compressione dati come un qualcosa di quasi anacronistico o comunque sorpassato, invece è sempre più attuale: esistono alcuni campi in cui essa riveste un ruolo fondamentale.
Per esempio, l’avvento della multimedialità ha portato ad un vertiginoso aumento della richiesta di capacità di memorizzazione: i filmati rappresentano il tipico caso di un immenso flusso di dati che deve essere immagazzinato e trasferito.


Cos’è la compressione

La compressione è un’operazione mediante la quale lo spazio necessario a contenere una determinata informazione viene ad essere ridotto mediante il ricorso a tecniche software oppure hardware.
Essa si basa generalmente sul concetto di sostituire una informazione con un’altra che la possa rappresentare necessitando di uno spazio minore. Su questo concetto si sono sviluppati numerosi sistemi alcuni dei quali, talvolta, sono utilizzati inconsapevolmente con molta frequenza nella vita lavorativa quotidiana: si può citare per esempio il caso del telefax che utilizza l’algoritmo di Huffman per la compressione dei dati.
Esistono molti algoritmi di compressione, ma nessuno è il migliore in assoluto: spesso i programmi ne implementano più di uno al fine di poter utilizzare quello che fornisce il miglior rapporto di compressione in relazione al tipo di dato su cui si deve operare.
Infatti, se si prende un file composto di un solo carattere ripetuto per centomila volte e si lancia Pkzip (versione 1.02) il file ottenuto avrà una dimensione di oltre un Kbyte, mentre l’Arj (versione 2.3) produce un file di seicento bytes.
Se essi avessero tentato con l’algoritmo RLE (Run Lenght Encoding) avrebbero prodotto un file lungo appena una decina di byte. Logicamente ogni programma che include nel file compresso varie informazioni quali il nome del file e la dimensione originaria non compressa, un CRC (Ciclic Redundany Check) nonché altre informazioni, produce degli archivi lievemente più grandi, ma il vantaggio rappresentato dalla disponibilità di questi dati è oltremodo pagato da quella decina di byte in più. In sintesi, ogni algoritmo di compressione non è idoneo a lavora re con ogni tipo di dato e perciò un buon compressore dovrebbe essere in grado di scegliere fra più algoritmi per poter stabilire di volta in volta quale sia il più efficiente in relazione alla situazione.
Lo stabilire quale sia il migliore comporta un’analisi e quindi un’elaborazione che talvolta consiste nel comprimere i file con tutti gli algoritmi disponibili per poter discriminare fra essi quale sia il più idoneo; ma questo è ovviamente causa di una crescita dei tempi di elaborazione.
Ne consegue che, in linea generale, all’ aumentare delle prestazioni di compressione vi è un aumento dei tempi dical colo, sia durante la compressione che durante la decompressione. Questo è un aspetto molto importante soprattutto per le animazioni, le quali necessitano di una velocità di decompressione che garantisca un tempo massimo al fine di evitare l’effetto di "movimento a scatti", i quali risultano essere estremamente sgradevoli. Senza avventurarci nei meandri della statistica, è comunque necessario segnalare che ogni compressione ha un rapporto detto rapporto di compressione, il quale viene calcolato dividendo la dimensione del file compresso per la sua dimensione iniziale e rappresenta l’efficienza della compressione.


Archivi e file

Per evitare confusione sui termini, quando si parla di compressione esistono due entità: il file che è esattamente ciò che si in tende con questo termine, e archivio, con il quale si identifica il file che contiene i file compressi.
Ogni archivio può contenere al suo interno uno o più file, perciò il programma di compressione deve necessariamente introdurre alcune informazioni dette file header prima di ogni file; in esse vengono memorizzati svariati dati relativi ad ogni file, quali:

  • il nome e sua estensione
  • nome della directory all’interno della quale risiedeva
  • data ed ora di creazione o di ultima modifica
  • i suoi attributi Dos
  • la dimensione originaria
  • il CRC

La loro presenza permette al programma di fornire all’utente alcuni servizi quali la possibilità di richiedere la scompattazione di un file senza la necessità di fornire il nome e la directory di destinazione, particolare utile quando in un archivio si trovano numerosi file; altra possibilità è l’aggiornare i singoli file all’in terno dell’archivio e la possibilità di poter analizzare in quale archivio sia memorizzato il file più recente nel caso che quest’ultimo sia duplicato in più archivi.
L’informazione dimensione originaria, ovvero la dimensione in byte del file non compresso, potrebbe risultare utile quando si cancella accidentalmente una parte di dati e poi si salvai! file: se non ci si rende conto subito del danno, potrebbe capitare che in tempi successivi si eseguano altre archiviazioni del file rovinato; da qui la necessità di poter vedere, nei vari archivi, qua le di essi contenga il file prima della cancellazione parziale.
La reale utilità di questa informazione è un’altra. Essa consente al programma di decompressione di verificare se durante la fase di decompressione i vari file riacquistano la loro dimensione originaria; in caso contrario è avvenuto un errore per cui il file prodotto non è uguale a quello che era stato compresso.
Ancor più importante al fine di garantire l’integrità dei dati è il CRC; esso vie ne generalmente inserito ogni n caratteri e consente al programma di controllare se il valore dei byte precedenti produce un CRC identico a quello atteso.
Questo semplice sistema è riconosciuto come uno dei migliori metodi di controllo sui dati in termini di sicurezza ed efficienza se confrontato al costo di elaborazione che è veramente minimo.


Perdita di informazioni

Il processo di compressione può prevedere una perdita di quantità di informazioni al fine di migliorare ulteriormente il rapporto di compressione.
Se a prima vi sta sembrerebbe insensato, questa scelta è abitualmente applicata in determinate aree; ovviamente nessuno penserà mai di applicare un algoritmo di compressione con perdita di informazioni a file di contabilità, ma esso è abitualmente utilizzato sui filmati in quanto essi sono estrema mente voluminosi e il guadagno ottenuto da questi algoritmi in termini di spazio occupato è ben ripagato dal degrado della qualità dell’immagine.
Per mediare fra la qualità e la compressione s ono stati implementati degli standard relativamente recenti concepiti esplicitamente per la gestione delle immagini. Essi sono il JPEG (Joint Photographic Engineering Group) e l’MPEG (Motion Picture Engineering Group).
Fra i vari concetti su cui si basa no gli algoritmi con perdita di informazioni, troviamo la compressione spazia le e la compressione temporale. La prima si basa sulla semplice idea di ridurre la dimensione di ogni singolo fotogramma o frame, mentre la seconda si fonda sull’osservazione che, spesso, le sequenze animate presentano solo lievi modifiche di fotogramma in fotogramma. E' tipico l’esempio della ripresa di una persona che parla su uno sfondo fisso quale un muro.
L’unica parte variabile durante tutta la durata del filmato sarà la persona e, più in particolare, il suo viso.
Da qui si parte elaborando un fotogramma di riferimento detto key frame che rappresenta praticamente il primo fotogramma; i successivi fotogrammi conterranno solo quell’area in cui è presente una modifica rispetto il key frame. In altre parole conterranno solo il corpo della per sona che parla nel caso si muova o gesticoli oppure il solo viso o addirittura le sole labbra. Questo secondo frame prende il nome di fotogramma differenziale in quanto esso contiene solo le informazioni che lo differenziano dal fotogramma di base; quest’ultimo rimane valido sino a quando il nuovo fotogramma presenta una differenza inferiore ad una determinata soglia, superata la quale il programma di compressione considera il nuovo fotogramma come key frame.
Per meglio comprendere l’ordine di grandezza con cui si ha a che fare quando si parla di animazioni, basta considerare che un fotogramma è composto da 525 linee per il formato NTSC e 625 per il PAL; ogni riga è composta da 720 pixel ed il colore viene rappresentato in RGB (Red, Green, Blue) occupando quindi 24 bit. La cadenza al secondo deve essere superiore ai 18 fotogrammi per secondo, altrimenti l’occhio umano potrà percepire la generazione dell’immagine sul video.
I valori generalmente utilizzati vanno da un minimo di 15 ad un massimo di 30.
La dimensione finale di un file non compresso contenente un’animazione sarà calcolabile con la formula seguente:

(1/8) x (durata in secondi) x (dim.orizzontale frame) x (dim. verticale frame) x (profondità del colore) x (frame al secondo)

Poiché i frame e la profondità dei colori, ovvero il numero di bit necessari per rappresentare un pixel, sono espressi in bit, è necessario trasformare il prodotto in byte dividendolo per 8 (numero di bit che compone un byte). A tal fine è stato introdotto il valore 1/8 all’inizio della formula, perciò il risultato corrisponderà al numero di byte necessari per memorizzare il fumato. Ad esempio, una modesta animazione digitale della durata di un minuto in una finestra di 160 per 120 pixel con 16 bit per la rappresentazione del colore visualizzata alla velocità di 15 frame/secondo occuperà oltre 34 Mbyte (Esistono anche algoritmi di compressione che volutamente perdono informazioni le quali non sono più ricuperabili in alcun modo).
Ad esempio è possibile comprimere un’immagine avente una profondità di colore a 32 bit semplicemente memorizzando ne solo 24 bit con un conseguente risparmio del 25%: questa operazione comporta una reale perdita di dati i quali risultano non più ricuperabili.
Questi algoritmi sono utilizzati in quei casi in cui è più importante il rapporto di compressione che la corrispondenza fedele al dato originario.


La trasmissione dati

La necessità di trasmettere una sempre crescente quantità di informazioni in tempi il più contenuti possibile ha portato allo sviluppo di varie tecniche fra le quali la compressione rappresenta un elemento sostanziale.
L’obiettivo in questo settore è fornire uno strumento che garantisca il successo della trasmissione in tempi ritenuti soddisfacenti nel contesto in cui viene utilizzato: ad esempio un sistema che garantisce la trasmissione senza errori ma che richieda per concludere la comunicazione tempi nell’ordine di mesi non avrebbe nessuna utilità.
Per raggiungere questo obbiettivo sono state percorse due strade parallele: la costruzione di apparati hardware sempre più complessi che consentissero di ridurre la durata del segnale e di sistemi software o firmware che permettessero di ridurre la quantità dei segnali.
Sono oggigiorno disponibili sul mercato sia i modem che qualche scheda di rete che implementano entrambe queste tecniche: la prima consente di trasmettere nell’unità di tempo un numero maggiore di segnali mentre la seconda effettua una compressione dei segnali in uscita; questo connubio consente di ottenere prestazioni in continuo miglioramento.
Ma il futuro in questo settore sembra meno interessato alla compressione di altri in quanto è indubbiamente più facile progettare nuovi dispositivi elettronici e supporti fisici quali le fibre ottiche che progettare algoritmi di compressione migliori di quelli esistenti.


Conclusione

La compressione dei dati è un argomento sentito come un’esigenza già da tantissimi anni. Oggi l’utente informatico dispone di eccezionali programmi in grado di eseguire compressioni con un rapporto di massima efficienza. Si potrebbe essere quindi propensi a considerare l’argomento compressione come un qualcosa di oramai giunto all’ apice dello sviluppo e che null’ altro vi sia da aggiungere. In realtà l’intero mondo dell’informatica è in attesa di un nuovo e migliore algoritmo.
Anche se magari non è vostra intenzione cimentarvi con questa non facile impresa, è altresì vero che essa rappresenta uno strumento oramai indispensabile e sul quale è meglio disporre di quel minimo di conoscenza e confidenza necessarie che sono richieste a tutti gli operatori del settore EDP.


Bibliografia

[1] R. Hone, M. Kuntz, "La gestione dei fumati con il PC", Ed. Tecniche Nuove, 1994, SBN 88 481 0163 1. [2] D.T. Roger, "Principi di programmazione grafica", Ed. Tecniche nuove, 1988, ISBN 88 7081 307 X. [3] S. Rimmer, "Windows bit mapped graphic", Mc Graw Hill, 1994, ISBN 88 386 0274 3.

Il testo e' stato acquisito tramite OCR dalla rivista su cui e' stato pubblicato e velocemente ricontrollato.
Le segnalazioni di errori saranno molto gradite e si possono fare alla pagina Contatti.

Tratto da:
Paolo Guccini
Rivista DEV Computer Programming
Edizioni Infomedia
1995