Software di compressionevenus.unive.it/borg/5Compressione.pdf · Reti e Sistemi Informativi –Anno...

Reti e Sistemi Informativi – Anno Accademico 2009/2010 1

Software di

compressione

di Giulia Giacon

2Reti e Sistemi Informativi – Anno Accademico 2009/2010

Di cosa stiamo parlando?

Si tratta di software applicativi in grado di comprimere

e di decomprimere un file.

1. La quantità di bit necessari alla rappresentazione in forma

digitale dell’informazione viene ridotta allo scopo di occupare

meno spazio nei supporti di memorizzazione quali l’Hard-disk

del computer, le unità floppy, i CD-Rom e le chiavette USB;

2. Tramite la decompressione il file ridotto viene riportato alle

condizioni iniziali, nuovamente pronto per essere aperto.

http://it.wikipedia.org/wiki/Digitale_(informatica)


Qual è il motore?

le operazioni di compressione/decompressione vengono

attivate da specifici strumenti detti algoritmi.

un algoritmo consiste nella soluzione di un problema più o

meno complesso, analizzato in precedenza, seguendo

successioni finite di istruzioni sequenziali preordinate,

rappresentate sotto forma di diagramma o di pseudocodifica

e applicabili ad ogni linguaggio di programmazione.

Gli algoritmi di compressione si basano sul presupposto che

in qualsiasi tipo di file ci siano dei dati ridondanti, superflui

o mal disposti.


Si possono individuare due grandi categorie di algoritmi:

1. Compressione di tipo Lossy

I dati vengono compressi attraverso un processo con perdita

d’informazione che sfrutta gli elementi superflui nell’utilizzo dei

dati.

2. Compressione di tipo Lossless

I dati vengono compressi attraverso un processo senza perdita

d'informazione che sfrutta le ridondanze nella codifica del dato.


Tecniche Lossy Ottengono delle compressioni molto forzate dei files a

scapito dell'integrità del file stesso.

L’idea di fondo è che l'occhio e l'orecchio umano hanno

delle limitazioni, operano quindi cercando di togliere dei

dettagli del video/audio senza che questo venga percepito

dall’utente.

Non possono essere usati per testi o database in cui l'integrità

dell'informazione è fondamentale, l'uso caratteristico è nel

campo multimediale.


Tecniche Lossless Durante la compressione si preoccupano di preservare il

messaggio originale.

Non possono garantire sempre la diminuzione delle

dimensioni dell’insieme di dati in input. Alcuni vengono

ridotti, ma altri restano necessariamente invariati.

Utilizzano questo tipo di metodi tutti quei files per i quali

non è accettabile una perdita di informazione, come i testi o i

programmi.


Tecniche Lossy:

file immagini: JPEG

file video: MPEG, DivX, WMV

file audio: Vorbis, MP3, AAC, WMA

Tecniche Lossless:

file testuali: Huffman, LZMA(7Zip), DEFLATE(WinZip)

file audio: FLAC, ALAC

file immagine: GIF, TIFF

file video: Sheervideo, Animation codec


In che lingua parli?

Nei computer i caratteri vengono codificati usando il codice

ASCII, un codice che associa 8 bits ad ogni simbolo.

Mediamente in tutti i files testo vi sono dei caratteri che

appaiono con una frequenza maggiore di altri.

Per risparmiare spazio nella codifica non avrebbe senso

assegnare a questi caratteri un codice composto da un

numero inferiore di bits?


Nel codice Morse le lettere con frequenza maggiorevengono rappresentate da sequenze più piccole, mentrequelle meno usate sono associate a codici più lunghi (adesempio: “e= ∙”; “a= ∙-”; “q= --∙-”; “j= ∙---”).

L'idea di usare codici più corti fu introdotta nell'ambitoinformatico da Claude Shannon e R. Fano negli anni 50.Qualche anno dopo D.A. Huffman ne migliora l’algoritmodando origine all’algoritmo di “Huffman”.

Si consideri un file di 40 caratteri in cui le lettere abbiano laseguente frequenza: “A”: 20 volte, “B”: 5 volte, “E”: 3volte, “C”: 7 volte, “O”: 5 volte.


Algoritmo di Huffman

Si consideri un file di 40 caratteri in cui le lettere abbiano laseguente frequenza: “A”: 20 volte, “B”: 5 volte, “E”: 3 volte,“C”: 7 volte, “O”: 5 volte.

Usando la codifica standard ASCII, il file occupebbe 40*8bits ovvero 320 bits.

Usando una codifica a lunghezza variabile, a le lettere confrequenza maggiore viene associato un numero inferiore dibits rispetto a quelle con bassa frequenza, ottenendo un filecon lunghezza inferiore ai 320 bits.



Questo è il principio base dell’algoritmo di Huffman usato per

la gestione dei testi. Partendo da uno studio statistico basato

sulla frequenza dei caratteri nelle parole cerca di codificare le

lettere a maggior frequenza con dei codici binari più brevi

rispetto a quelli utilizzati per quelle meno frequenti.

Esempio:

Si intende comprimere un file testo contenente la stringa:

“CIAO_MAMMA”



Codice ASCII:

“A”= 01000001 “C”= 01000011 “I”= 01001001

“O”= 01001111 “M”=01001101 “_”= 01000000

Il file salvato sarà pertanto composto da 80 bits (= 10 lettere *8 bits):

01000011 01001001 01000001 01001111 01000000 01001101

01000001 01001101 01001101 01000001

Applicando l'algoritmo di “Huffman” per prima cosa ènecessario contare la frequenza di ogni lettera presente nella

stringa:“C”(1), “I”(1), “A”(3), “O”(1), “M”(3), “_”(1)



Vanno individuate le due lettere con minor frequenza (la “C” e

la “I”). Nello schema delle frequenze saranno rappresentate

come un’unica lettera e con una frequenza che sarà la somma

delle loro frequenze

“C+I”(2), “A”(3), “O”(1), “M”(3), “_”(1)

Si cercano ancora le due lettere conminor frequenza e osserva che sitratta dell'accoppiata “C+I” e “O+_”.

“C+I+O+_”(4),“A”(3), “M”(3)



Una volta creato l'albero,

bisogna associare ad ogni

nodo un bit. E' possibile

associare lo “0” a tutti i nodi

di sinistra e l’“1” a tutti quelli

di destra. Con i nuovi codici

otterremo la seguente

sequenza di bits:

000001100100111110111110



Solamente 24 bits invece degli 80 che verrebbero impiegati

con il codice ASCII. Per capirne la vera potenza, si deve

immaginare lo stesso algoritmo applicato ad un file testo di

migliaia di parole.

È importante sottolineare che il codice così ottenuto non è

univoco; nel senso che può essere creato un codice

altrettanto valido, ma differente da quello qui presentato.


Applicazioni

L’estesa diffusione dei programmi di compressione inizia

negli anni 90 quando il principale supporto di scambio dati è

l’unità floppy da 1.44 Mbyte, se non più piccolo da 360

Kbyte.

In seguito si afferma anche su Internet, per diminuire le

dimensioni dei files da trasferire riducendo notevolmente il

tempo di connessione necessario per l’upload e per il

download dei files secondo gli standard V24bis o MNP5

relativi ai modem.


PKZip: primo software introdotto nel mercato degli home

computer.

Attualmente esistono molteplici software di compressione,

scaricabili on-line, che si suddividono principalmente in:

Software shareware: tutti quei software concessi sotto licenza d’uso

quindi a pagamento, alcuni dei quali prevedono un periodo di prova

gratuito mediamente da 30 a 40 giorni (WinZip 11.0; WinRar 3.71).

Software freeware: insieme di software disponibili all’uso

gratuitamente (ZipGenius 6; 7-Zip).


Quale scegliere?

Da un punto di vista tecnico la scelta va fatta prendendo in

considerazione una serie di parametri.

I programmi vengono valutati in base a due preferenze

immediate nelle esigenze quotidiane del target di utenza:

ottenere una maggiore compressione e occupare così meno spazio

nella memoria;

impiegare il minor tempo possibile nel comprimere i files a scapito

della potenza di compressione.


Una volta stabilito l’interesse principale dell’utente, affinché

un test sia attendibile e aggiornato il più possibile, si

dovrebbero considerare:

l’ultima versione disponibile sul mercato, il relativo costo e l’opzione

di lingua dell’interfaccia;

le caratteristiche del file da comprimere per il confronto delle

performances;

il livello di memoria Ram e di potenza della CPU del computer di cui

il software necessita per essere operativo.


Dato che ogni algoritmo a seconda della propria struttura di

funzionamento occupa una certa quantità di memoria Ram.

È importante conoscere anche le caratteristiche effettive del

PC su cui si intende caricare i programmi da testare.

In questo modo, il test può essere considerato valido ed

attendibile, rendendo la scelta autonoma e consapevole.


Le Fonti

Articoli di giornale:

Salari P., “Un mondo compresso” in PC Pratico n.10 – anno VII – ottobre 2001,

pg. 126-129

Siti internet:

http://www.pc-facile.com/download/?cat=15

http://www.pc-facile.com/glossario/v24bis/

http://www.pc-facile.com/glossario/mnp5/

http://www.pc-facile.com/glossario/algoritmo/

http://www.pcperfetto.com/compressionefiles.html

http://www.ictv.it/file/vedi/340/software-di-compressione/

http://www.ecowebnews.it/software%20di%20compressione

http://it.wikipedia.org/wiki/Algoritmo_Lempel-Ziv-Markov

http://it.wikipedia.org/wiki/LZ77_e_LZ78

http://it.wikipedia.org/wiki/Compressione_dei_dati

http://it.wikipedia.org/wiki/Compressione_dati_lossy

http://it.wikipedia.org/wiki/Compressione_dati_lossless

http://www.dspvlsi.uniroma2.it/corsi/bio/La%20compressione.doc

http://it.wikipedia.org/wiki/Codifica_di_Huffman

























http://www.ecowebnews.it/software di compressione

http://www.ecowebnews.it/software di compressione















http://www.dspvlsi.uniroma2.it/corsi/bio/La compressione.doc

http://www.dspvlsi.uniroma2.it/corsi/bio/La compressione.doc



Software di compressionevenus.unive.it/borg/5Compressione.pdf · Reti e Sistemi Informativi –Anno...

Documents

Transcript of Software di compressionevenus.unive.it/borg/5Compressione.pdf · Reti e Sistemi Informativi –Anno...