Significato, vantaggi e svantaggi
Marchesin Sara
Soligo Alessandra
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Tecnica utilizzata in ambito informatico, per
ridurre le dimensioni di un file e quindi lo
spazio necessario per la sua memorizzazione.
Primo esempio di compressione dei dati con tecniche
probabilistiche risale alla prima metà dell’800 con Samuel
Morse,in Inghilterra.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Riduce la quantità di bit necessari alla
rappresentazione digitale di
un’informazione, eliminando la parte
ridondante senza precludere la
comprensibilità del messaggio.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
PERSOSTE*ERELESAM*DISISTEMIDIE*A
BORAZIONEDELLE*NFORMAZIONIB*SO
GNAST*DIAREEFR*QUENTAR*ILCORSO
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
La frase precedente mostra una rudimentale
forma di compressione dati che sfrutta il
fatto che la lingua italiana, come tutti i
linguaggi naturali, è ridondante.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Si dividono in due categorie:
Compressione
dati lossy;
Compressione dati lossless.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Comprime i dati attraverso un processo con
perdita d’informazione che sfrutta le
ridondanze nell’utilizzo dei dati:


Grandi risparmi di risorse;
svantaggio qualità audio-video.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Comprime i dati attraverso un processo senza
perdita d’informazioni che sfrutta le
ridondanze nella codifica del dato:
preservano
le informazioni;
“Zip” è il formato più conosciuto;
solitamente utilizzato per immagini non
fotografiche.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Risparmio
della spazio quando si
memorizzano i file;
Risparmio di tempo all’invio del file.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Tempo
impiegato per comprimere e
decomprimere un file;
il file compresso non è usabile
direttamente, per usarlo si deve
decomprimere;
il file compresso è più “fragile”. Alcuni
errori di trasmissione possono alterarne il
contenuto.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Zip
Gzip
Bzip2
Rar
7z
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
WinZip è il più diffuso programma per la
compressione e decompressione dei file e
"ZIP" è il nome di un particolare formato di
compressione associato a questo.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
quanta memoria può richiedere un’enciclopedia
multimediale?
500.000 pagine di testo (2 KB per pagina): 1GB
3.000 immagini a colori (in media 640x480x24 bit = 1MB): 3
GB
500 mappe (in media 640x480x16 bit = 0.6 MB): 0.3 GB
60 minuti di suono stereo (176KB/sec.): 0.6 GB
30 animazioni di durata media di 2 minuti (640x320x16 bit x
16 frame /sec = 6.5 MB/sec): 23.4 GB
50 video, di durata media di 1 minuto (640x480x24 bit x 30
frame/sec = 27.6 MB/sec): 82.8 GB
Per un totale di: 111.1 GB
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Si applicano allora algoritmi di compressione ai diversi tipi di
media usati e si assume di ottenere mediamente i seguenti
rapporti di compressione:
Testo 2:1  0.5 GB
Immagini a colori 15:1  0.2 GB
Mappe 10:1  0.03 GB
Suono stereo 6:1  0.1 GB
Animazioni 50:1  0.47 GB
Video 50:1  1.66 GB
Si passa quindi da 111.11 GB a 2,96 GB
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Nei computer i caratteri vengono codificati usando il
codice ASCII "American Standard Code for Information
Interchange", cioè "Standard americano per lo scambio di
informazioni":
codice di 8 bit per ogni simbolo
ad esempio:
01100001 in binario rappresenta la lettera a.
Un file di 100 caratteri quindi occuperà sempre 800 bit
(8 bit * 100 caratteri = 800) sia esso composto da 100
caratteri differenti piuttosto che da 100 identici.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Visto che in tutti i file testo alcuni caratteri
appaiono con una frequenza maggiore di altri non
avrebbe senso assegnare a questi un codice
composto da un numero inferiore di bit in modo da
risparmiare spazio nella codifica ??
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Vogliamo comprimere un file testo contenente la stringa:
CIAO_MAMMA
In un normale file testo, ogni lettera è rappresentata da 8 bit
codificati rispettando il codice ASCII.
Il nostro file salvato sarà composto così da 80 bits, ovvero 10
lettere * 8 bit:
c01000011 i01001001 a01000001 o01001111 _00100000
m01001101 a01000001 m01001101 m01001101 a01000001
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Codifica di Huffman
È un algoritmo di usato per la compressione dei
dati, basato sul principio di trovare il sistema
ottimale per codificare stringhe a seconda della
frequenza relativa di ciascun carattere.
Essa è stata sviluppata nel 1952 da David A. Huffman, mentre
stava svolgendo il dottorato e pubblicata su “Method for the
Construction of Minimum-Redundancy Codes” (Un Metodo
per la Costruzione di Codici a Ridondanza Minima).
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
È stato dimostrato che la codifica di Huffman è il
più efficiente sistema di compressione di questo
tipo: nessun'altra mappatura di simboli in stringhe
binarie può produrre un risultato più breve nel
caso in cui le frequenze di simboli effettive
corrispondono a quelle usate per creare il codice.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Applicando l'algoritmo di Huffman per calcolare
dei nuovi codici da assegnare alle lettere
dell'esempio si deve costruire un albero in cui le
lettere più frequenti siano posizionate più vicino
alla radice rispetto a quelle con minore
frequenza.
Per prima cosa è necessario contare la frequenza
di ogni lettera nella nostra stringa:
C(1) I(1) A(3) M(3) O(1) _(1)
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Una volta creato l'albero, bisogna associare ad ogni
nodo un bit.
E' possibile associare lo 0 a tutti i nodi di sinistra e
1 a tutti quelli di destra. E' possibile anche fare il
contrario senza compromettere il risultato finale.
Nel nostro caso scegliamo lo 0 a sinistra e l'1 a
destra ed ecco il risultato finale:
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Volendo scrivere a questo punto il nostro
CIAO_MAMMA con i nuovi codici otterremo la
seguente
sequenza di bit:
000001100100111110111110
Solamente 24 bit invece degli 80 usati in
precedenza con il codice ASCII !
E solamente su una stringa di 10 caratteri.
Immaginiamo lo stesso algoritmo applicato ad un file testo di
migliaia di parole per capirne la vera potenza.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
E' importante sottolineare che il codice ottenuto
non è univoco, nel senso che può essere creato un
codice altrettanto valido ma differente dal nostro
che può dipendere ad esempio dalle lettere con
minor frequenza scelte all'inizio oppure dal modo
in cui decidiamo di impostare gli 0 e gli 1 sui rami
dell'albero.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
Una caratteristica particolare di questo algoritmo
è che il codice ottenuto per ogni singola lettera
NON è un prefisso di un’altra lettera.
Nel nostro esempio, la A ha il codice 10 e nessuna altra
lettera ha una codifica che comincia con 10.
In questo modo leggendo la stringa di 24 bit che abbiamo
ottenuto in precedenza, possiamo riconoscere le singole
lettere senza bisogno di un separatore tra loro.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
JPEG è l'acronimo di Joint Photographic
Experts Group, un comitato ISO/CCIT che ha
definito il primo standard internazionale di
compressione per immagini a tono continuo,
sia a livelli di grigio che a colori.
1.
2.
3.
4.
è un formato aperto e ad implementazione gratuita.
attualmente JPEG è lo standard di compressione delle
immagini fotografiche più utilizzato
l'estensione più comune per questo formato è .jpg, ma
sono anche usate .jpeg, .jfif, .JPG, .JPE.
è una compressione di tipo lossy
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
JPEG qualità 10% - 3,2 Kb
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
JPEG qualità 50% - 6,7 Kb
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
JPEG qualità 90% - 30,2 Kb
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
JPEG qualità 100% - 87,7 Kb
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni
www.wikipedia.it
 www.tutorialpc.it/winzip.asp
 www.winzip.com


Varie riviste e dispense trovate in internet.
università ca'foscari di Venezia - corso di sistemi di elaborazione delle informazioni