Utente:Hellis/Senza perdita d'informazione

La compressione dati senza perdita d'informazione come detto nel capitolo precedente è una classe di algoritmi di compressione dati che non porta alla perdita di alcuna parte dell'informazione originale durante la fase di compressione/decompressione dei dati stessi.

Le tecniche di compressione che ricadono in questa categoria sfruttano il fatto che la maggior parte dei file che vengono utilizzati contegno al loro interno una significativa ridondanza dei dati, sfruttando questa ridondanza e riorganizzando in modo più efficiente i dati si può ridurre la dimensione dei file nella maggior parte dei casi. E' da notate che non può esistere un algoritmo di compressione senza perdita d'informazione che comprime tutti i possibili file. Quest'affermazione può essere dimostrata tramite il seguente ragionamento logico.

1. Si supponga di aver un generico algoritmo chiamato A, questo algoritmo comprime sempre i file riducendo la dimensione almeo dell'1%.
2. Si prende un generico file chiamato X e lo si comprime tramite A ottenendo Y=A(X).
3. Il file Y dato che l'algoritmo A funziona sempre deve essere più piccolo di X di almeno 1%.
4. Si supponga di comprimere Y tramite A ottenendo Y²=A(Y).
5. Dato che A comprime sempre tutti i tipi di file Y² deve essere più piccolo di Y e quindi anche di X
6. Si supponga di reitarare la compressione n volte ottenendo Yⁿ
7. Yⁿ è piccolo di tutti gli altri file da Y^n-1 fino a X e continuano si potrebbe arrivare a un file di dimensione nulla che ovviamente è impossibile, dato che da un file nullo non si può pensare di ricostruire un file non nullo. Quindi non può esistere un algoritmo di compressione che comprime ogni tipo di file.

Nelle applicazioni reali comunque la maggior parte dei file hanno una loro intrinseca ridondanza dei dati e sfruttando questa ridondanza si può ridurre la dimensione dei file. Per esempio supponendo di avere un file contenente un testo in italiano il testo conterrà molto spesso le vocali a,e,i e raramente lettere come a x,y,z. Normalmente nel testo tutte le lettere dell'alfabeto sono rappresentate con 8 bit ma si potrebbe pensare di rappresentare con una notazione con pochi bit le vocali e di utilizzare una rappresentazione con più bit per le consonanti meno usate. Questo permetterebbe di ottenere in media un file più piccolo di quello di partenza. O per esempio si supponga di aver un'immagine con uno sfondo uniforme, in un immagine non compressa ogni punto dell'immagine è memorizzata con un simbolo che identifica il colore. Lo sfondo uniforme quindi sarà memorizzato come una sequenza continua di simboli tutti uguali, quindi supponendo di identificare 15 simboli uguali contigui si potrebbe pensare di memorizzare il primo simbolo e poi il numero di volte che va ripetuto. Quindi la sequenza

• Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero,Nero

diventerebbe la sequenza

• Nero * 15

Quindi si passerebbe da 15 simboli memorizzati a soli 3 simboli memorizzati riducendo la dimensione della stringa di cinque volte.

Questi sono degli esempi semplificati delle varie tecniche di compressione senza perdita d'informazione, le reali tecniche di compressione devono preoccuparsi di individuare la ridondanza all'interno dei file e nel contempo devono essere efficienti e risolvere dei problemi di implementazione; i vari problemi verranno analizzati nei capitoli successivi.