© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 1
FONDAMENTI DI INFORMATICA
Prof. PIER LUCA MONTESSORO
Facoltà di Ingegneria Università degli Studi di Udine
Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2 Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degli Studi di Udine.
Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.
Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte dell’autore.
L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).
In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.
In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.
Nota di Copyright
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 3
Run Length Encoding
• Comprime sequenze di byte uguali
• Due versioni:
– con uso di carattere riservato – senza uso di carattere riservato
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 4
Run Length Encoding
• Facendo uso di un carattere riservato si può sostituire una sequenza di byte uguali con il carattere riservato seguito da uno solo dei byte ripetuti più un contatore del numero di ripetizioni
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 5
Run Length Encoding ecco ******** 8 asterischi
65 63 63 6F 20 2A 2A 2A 2A 2A 2A 2A 2A 20 38 20 61 73 74 65 72 69 73 63 68 69
65 63 63 6F 20 1A 2A 8 20 38 20 61 73 74 65 72 69 73 63 68 69 codici ASCII
carattere riservato (SUB)
codice ASCII del carattere da ripetere numero di ripetizioni
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 6
Run Length Encoding
• Senza usare un carattere riservato si
può accorciare una sequenza di byte
uguali interrompendola dopo un numero
predefinito di ripetizioni (es. 3) e
sostituendo ai caratteri rimanenti il
numero che rappresenta la lunghezza
totale della sequenza
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 7
Run Length Encoding ecco ******** 8 asterischi
65 63 63 6F 20 2A 2A 2A 2A 2A 2A 2A 2A 20 38 20 61 73 74 65 72 69 73 63 68 69
65 63 63 6F 20 2A 2A 2A 8 20 38 20 61 73 74 65 72 69 73 63 68 69 codici ASCII
prima parte della sequenza
lunghezza totale della sequenza
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 8
Run Length Encoding
ecco *** 3 asterischi
65 63 63 6F 20 2A 2A 2A 20 33 20 61 73 74 65 72 69 73 63 68 69
65 63 63 6F 20 2A 2A 2A 3 20 33 20 61 73 74 65 72 69 73 63 68 69 codici ASCII
prima parte della sequenza lunghezza totale della sequenza A VOLTE LA LUNGHEZZA AUMENTA...
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 9
Codifica entropica
• Si associano codici binari più corti ai simboli (elementi di informazione) più probabili
NOTA: la codifica dell’informazione vista finora (numeri, testi) è finalizzata alla semplicità dell’elaborazione, non alla minimizzazione della lunghezza del codice
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 10
Definizioni
• Alfabeto
• Probabilità dove
} ,...,
{ 1 M
A = α α
∑ =
=
= M
j j
M p
p p P
1 1 ,..., }, 1 {
0 ] [ α ≥
≡ j
j P
p
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 11
Definizioni
• Informazione del simbolo isolato α j
• Si definisce entropia della sorgente di simboli X = {A, P} la sua informazione media
Proprietà:
⎟ ⎟
⎠
⎞
⎜ ⎜
⎝
≡ ⎛ α
j
j p
i 1
log )
( 2
∑ =
= α
= M
j
j
j p
p i
E X H
1
2 ( 1 / ) log
)]
( [ ) (
M X
H ( ) log 2
0 ≤ ≤
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 12
Codifica entropica
• L’entropia misura l’uniformità (o la non uniformità) della distribuzione dei simboli generati dalla sorgente
• È possibile assegnare ai simboli codici di lunghezza differente
• Esempio: codici a prefisso (nessuna parola di codice è prefisso ad un’altra parola di codice)
A → 0, B → 10, C → 110, D → 111
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 13
Codifica entropica
• I codici a prefisso vengono decodificati mediante alberi binari
• Esempio:
A → 0, B → 10, C → 110, D → 111
A 0 1
B C D
0 0 1
1
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 14
Codifica entropica
• La probabilità di un simbolo può anche essere funzione del “contesto”, cioè dei simboli che lo hanno preceduto
• Esempio: nell’alfabeto comune la probabilità della lettera ‘u’ è quasi 1 dopo una ‘q’
• È possibile introdurre codifiche con memoria, basate sulla probabilità condizionata dal contesto
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 15
Codifica di Huffman
• Viene costruito un albero binario in cui ogni diramazione rappresenta l’aggiunta un bit a 1 o a 0 della parola di codice
• Il grado di sbilanciamento dell’albero è funzione della frequenza relativa di ricorrenza dei dati
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 16
Esempio
α
1α
4α
5α
2α
3P=1.0
P=0.55
P=0.45 P=0.3
0 1
1 0 0
0 1
Probabilità dell’alfabeto P={0.25, 0.25, 0.2, 0.15, 0.15}
α
1→ 00 α
2→ 10 α
3→ 11
α
4→ 010 α
5→ 011
Nota: sono necessari arrotondamenti per ottenere un numero intero di bit Entropia
H(X) = 2.2855 bit/simbolo
1
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 17
MNP 5:
codifica adattativa statistica basata sulla frequenza dei caratteri
• Cambia la codifica binaria di ogni byte utilizzando un numero di bit minore, uguale o maggiore a 8 a seconda della frequenza con cui il carattere compare
• È adattativa perché calcola
dinamicamente la frequenza statistica dei caratteri durante la compressione
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 18
MNP 5
byte in ingresso header body
00000000 000 0
00000001 000 1
00000010 001 0
00000011 001 1
00000100 010 00
00000101 010 01
00000110 010 10
00000111 010 11
00001000 011 000
00001001 011 001
… … …
00100000 101 00000
… … …
11111100 111 1111100
11111101 111 1111101
11111110 111 1111110
11111111 111 11111110
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 19
MNP5: compressione
compressione 00000101
header body contatori
aggiorna il contatore
restituisce la nuova codifica
01001
se il contatore di un byte indica una frequenza maggiore di uno a codifica più corta, verranno scambiati con effetto dalla prossima occorrenza
A
B
C
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 20
MNP5: versione più sofisticata
• Si utilizzano 256 tabelle
• La tabella da usare viene selezionata in base al carattere precedente
• In questo modo il calcolo della frequenza statistica è più accurato
• Esempio:
– la lettera ‘u’ dopo una ‘q’ ha probabilità estremamente elevata, mentre in altri casi è molto bassa
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 21
Codifica a dizionario
• Idea di base: Ziv-Lemper
• Successivamente modificata da Welch
→ Algoritmo LZW
• Utilizzato in numerosi software comuni (es. WinZip)
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 22
Codifica a dizionario
• L’idea di base è suddividere i dati di ingresso in sottosequenze che, se già incontrate nella sequenza di dati di ingresso, vengono codificate mediante il puntatore alla posizione corrispondente
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 23
Algoritmo di Lempel-Ziv-Welch (LZW)
• Sostituisce stringhe (sequenze) di caratteri con un singolo codice binario
• I codici hanno lunghezza predefinita maggiore di 8 bit (es. 12 bit):
– i primi 256 valori sono assegnati ai caratteri ASCII
– i restanti valori vengono assegnati dall’algoritmo alle stringhe
Fondamenti di Informatica - Tecniche di compressione senza perdita
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 24
Algoritmo di Lempel-Ziv-Welch (LZW)
STRING = get input character
WHILE there are still input characters DO CHARACTER = get input character IF STRING+CHARACTER is in the string
table then STRING = STRING+character ELSE
output the code for STRING
add STRING+CHARACTER to the string table
STRING = CHARACTER END of IF
END of WHILE
output the code for STRING
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 25