"generiche": tecniche di compressione applicabili a qualsiasi sequenza binaria

• tuttavia, con efficacia variabile

codifica run-length

• codifica il numero di occorrenze consecutive del simbolo

codifica differenziale, o relativa

• decompone la sequenza in blocchi e codifica le differenze del blocco relativamente al precedente

codifica dipendente dalla frequenza dei simboli

• esempi: codice Morse, codici di Huffman

codifica basata su dizionario, adattativa

• si codificano riferimenti (numerici) a un dizionario predefinito (ad es., quello per il controllo ortografico in un elaboratore di testi) o, in quella adattativa, dinamicamente costruito sulla stessa sequenza da codificare
• esempi: codifiche di Lempel-Ziv (ad es. LZW: Lempel, Ziv & Welsh)

sono largamente in uso tecniche di compressione specifiche

• cioè, specificamente progettate (e standardizzate) per dati multimediali

tecniche di compressione audio:

• MP3: (v. appresso)
• OGG/VORBIS: più efficace di MP3, a parità di qualità
• Speex: molto efficace per la compressione del parlato

standard di compressione di immagini:

• GIF: Graphical Interchange Format
• PNG: Portable Network Graphics
• JPEG: Joint Photographic Experts Group

compressione A/V:

• MPEG: Motion Picture Experts Group
• compressione video: ∼JPEG + codifica relativa
• compressione audio: MP3 = MPEG-1 Layer 3

problema:

• nella comunicazione attraverso un mezzo trasmissivo, una sequenza binaria è suscettibile di alterazioni accidentali che possono corrompere l'informazione rappresentata

soluzione:

• estendere la sequenza con informazione di controllo di errore
  • efficace per la rivelazione di errori (in certi limiti),
  • e magari anche per la loro correzione (in limiti più ristretti)

esempi (in ordine di crescente complessità algoritmica):

• bit di parità aggiunto alla codifica ASCII dei caratteri
• byte di controllo, per sequenze più lunghe di un byte
• somma di controllo (ingl.: checksum )
• codici a ridondanza ciclica (ingl.: Cyclic Redundancy Code (CRC))

per configurazioni binarie di uguale lunghezza, distanza di Hamming :

• di due configurazioni binarie: numero di bit in cui differiscono
• di un insieme finito di configurazioni binarie:
  minima distanza di Hamming fra due configurazioni nell'insieme
• di un codice c : A → 2ⁿ: distanza di Hamming della sua immagine c(A)

un codice con distanza di Hamming 2n+1 permette di rivelare fino a 2n errori nella trasmissione della codifica di un simbolo, e di correggere fino a n errori

• esempio: il codice appresso a sinistra ha distanza di Hamming 3

1. Tecniche generiche di compressione adattativa
   L'algoritmo LZW di compressione generica, pubblicato nel 1984, è un raffinamento di algoritmi proposti in precedenza: è adottato in alcuni programmi di utilità, ad es. compress in sistemi Unix di vecchia data, ma nel corso del tempo questi hanno ceduto il posto ad altre tecniche generiche, quali ad es. gzip, bzip2, rzip, che vantano rapporti di compressione mediamente migliori. Meritano approfondimento gli algoritmi di compressione impiegati in tali tecniche e un'analisi comparativa dei relativi pregi e limiti.
2. Tecniche di compressione lossy
   Si indicano con questo termine le tecniche caratterizzate dalla possibilità di perdita di informazione attraverso la codifica, ragion per cui la decodifica non è esattamente l'inversa della codifica, ma ne è solo un'approssimazione. Per la compressione di dati multimediali tale perdita, se contenuta entro certi limiti, è spesso accettabile, ad es. quando genera differenze impercettibili dai sensi umani interessati (visione, udito). Alcune tecniche lossy sono impiegate negli standard di cui si son dati cenni a lezione, altre sono tuttora oggetto di ricerca, ad es. le tecniche di compressione frattale o quelle basate su ondulette (ingl. wavelet). Si possono approfondire le idee alla base di tali tecniche, i relativi algoritmi e i campi d'impiego in cui risultano meglio applicabili.