Entropia di sequenze simboliche

Entropia di sequenze simboliche
Chiara Basile, Chiara Farinelli
Dipartimento di Matematica, Università di Bologna
8 Luglio 2008
“La mia più grande preoccupazione era come chiamarla. Pensavo di chiamarla
informazione, ma la parola era fin troppo usata, così decisi di chiamarla incertezza.
Quando discussi della cosa con John Von Neumann, lui ebbe un’idea migliore. Mi
disse che avrei dovuto chiamarla entropia, per due motivi: ‘Innanzitutto, la tua
funzione d’incertezza è già nota nella meccanica statistica con quel nome. In secondo
luogo, e più significativamente, nessuno sa cosa sia con certezza l’ entropia, così in una
discussione sarai sempre in vantaggio.’ ”
- C.E. Shannon -
L’idea generale [2]: misurare la quantità di informazione di un “messaggio” emesso da
una “sorgente”. Gli aspetti semantici (il significato del messaggio) non sono presi in considerazione, la quantità di informazione si pensa invece come una misura del fatto che si sta
scegliendo un messaggio tra i tanti possibili.
Da qui subito una prima idea: usare come misura del contenuto informativo il “numero di
messaggi ” tra cui si è scelto, o una qualsiasi funzione monotona di tale numero. Per ragioni
“pratiche” (di semplicità di calcolo e anche ingegneristiche - Shannon si poneva il problema
reale della comunicazione!) si può pensare di utilizzare il logaritmo del numero di messaggi.
Fin qui solo chiacchiere...
1
Sorgenti d’informazione ed ergodicità
Definizione 1.1. Dato uno spazio di probabilità (Ω, S, P ) e un alfabeto finito A, un processo stocastico è una successione infinita {Xn } = {X1 , X2 , . . . , Xn , . . .} di variabili aleatorie
definite da Ω in A. Il processo si dice stazionario se P (X1 = a1 , . . . , Xn = an ) = P (X1+k =
a1 , . . . , Xn+k = an ) ∀ a1 , . . . , an ∈ A, ∀ k, n ∈ N.
Per comodità denoteremo spesso con an1 la sequenza a1 , . . . , an e analogamente con X1n
la sequenza costituita dalle prime n componenti del processo. Nel caso di processi stazionari
indicheremo inoltre con P (an1 ) la probabilità P (X1 = a1 , . . . , Xn = an ), che sappiamo essere
invariante per traslazione della sequenza. Tali probabilità congiunte, al variare di n, sono
dette per brevità distribuzione del processo e determinano univocamente il processo stesso:
in altre parole, la particolare scelta di (Ω, S) non è importante, purché la distribuzione sia
la stessa.
1
Una sorgente di informazione (discreta) può essere rappresentata matematicamente come un processo stocastico: un’“entità” che genera un simbolo ad ogni istante di tempo n
(discretizzato), costruendo in modo sequenziale una stringa di caratteri presi da un alfabeto
fissato e finito A. La probabilità con cui essa genera un simbolo può dipendere, in generale,
dai simboli precedenti, dal simbolo in questione e dall’istante in cui lo genera. Diremo che la
sorgente è stazionaria quando lo è il processo che la rappresenta: in questo caso la distribuzione di probabilità con cui la sorgente genera i simboli si mantiene costante al passare del
tempo.
Intuitivamente, una sorgente si dice ergodica se quasi ogni sequenza da essa prodotta ha
le stesse proprietà statistiche. Più formalmente:
Definizione 1.2. Sia A∗ = ∪n∈N An l’insieme delle sequenze finite di simboli di A e per
an1 , bk1 ∈ A∗ , con n ≥ k, sia fan1 (bk1 ) la frequenza (relativa) di bk1 in an1 . Definiamo l’insieme
delle sequenze tipiche della sorgente (stazionaria):
T ({Xn }) = {a ∈ AN | ∀ k ∈ N, ∀ bk1 ∈ Ak , fan1 (bk1 ) −−−→ P (X1k = bk1 )}.
n→∞
Una sorgente (i.e. la sua distribuzione P ) si dice ergodica se e solo se P (T ({Xn })) = 1, cioè
se e solo se quasi ogni sequenza generata dalla sorgente è tipica.
Nota: questa è solo una delle (tante!) possibili definizioni equivalenti di ergodicità... [3]
A cosa serve l’ergodicità? Permette di identificare medie su sequenze tipiche infinite
(medie “temporali”, se si pensa a {Xn } come all’orbita di un sistema dinamico...) con medie
sull’insieme di tutte le sequenze (medie “spaziali”)... questo è molto importante dal punto
di vista sia teorico (vedi seguito) sia pratico: permette di considerare sequenze “abbastanza
lunghe” come buoni indicatori della distribuzione della sorgente che le ha generate...
2
L’entropia di una variabile aleatoria
Volevamo misurare la quantità di informazione veicolata da un messaggio di una data sorgente; ancora meglio, vorremmo misurare il tasso (rate) con cui tale informazione è prodotta
dalla sorgente. Limitiamoci per ora ad una singola variabile aleatoria X che prende valori
nell’alfabeto A = {a1 , . . . , am }, e sia pi = P (X = ai ), i = 1, . . . , m; ci poniamo il problema
di misurare “quanto è incerto” il valore di X. È naturale richiedere tre proprietà ad una
funzione H che misuri tale incertezza:
1. H(X) = H(p1, . . . , pm ) continua nelle pi ;
2. se denotiamo A(m) = H( m1 , . . . , m1 ) (X può assumere gli m valori con uguale probabilità), A(m) deve essere una funzione crescente di m: l’aggiunta di un evento
equiprobabile può solo aumentare l’incertezza;
P
P
p
p
3. H(p1 , . . . , pm ) = H( kj=1 pij , p1 , . . . , p̂i1 , . . . , p̂ik , . . . , pm )+ kj=1 pij H( Pk i1 p , . . . , Pk ik p ),
j=1
ij
j=1
∀ k = 1, . . . , n, ∀ i1 < . . . < ik ∈ {1, . . . , m}
Diamo qualche spiegazione della terza proprietà richiesta. Innanzitutto si è fatto un abuso di
notazione utilizzando lo stesso simbolo H per indicare diverse funzioni, con un numero diverso
di argomenti: tale notazione sarà comunque mantenuta anche nel seguito, per semplicità. La
proprietà 3 può essere espressa nel seguente modo: ogni volta che è possibile spezzare una
scelta in due scelte successive la H della scelta originaria deve essere la somma della H delle
due scelte, ognuna pesata con la probabilità che tale scelta sia effettuata.
2
ij
Esempio 2.1. Sia A = {a,b,c}, un alfabeto ternario, e P (a) = 1/2, P (b) = P (c) =
1/4. Si può suddividere la scelta in due scelte successive: prima si sceglie tra i due eventi
equiprobabili {a} e {b,c} e poi, se si è scelto {b,c}, si sceglie ancora una volta in modo
equiprobabile tra b e c. Allora, secondo la 3, dovrà essere H( 21 , 14 , 41 ) = H( 12 , 21 ) + 12 H( 21 , 12 )
(colori come in figura 1).
Figura 1: Decomposizione di una scelta ternaria in due scelte binarie.
Teorema 2.1 (Shannon,[2]). La sola funzione che soddisfa le tre proprietà elencate sopra è
H(p1, . . . , pm ) = −K
m
X
pi log pi ,
i=1
con K costante positiva che deriva semplicemente dalla scelta della base del logaritmo (i.e.
di una unità di misura per H). H è detta entropia della variabile aleatoria X o della
distribuzione di probabilità (p1 , . . . , pm ).
Dimostrazione. È sempre possibile decomporre una scelta tra sm possibilità equiprobabili in
m scelte tra s possibilità equiprobabili, ottenendo per la proprietà 3:
A(sm ) = mA(s)
e, analogamente,
A(tn ) = nA(t).
Per qualsiasi valore di s, t ed n esiste un m tale che
sm ≤ tn ≤ sm+1 .
Da qui, prendendo il logaritmo in base s e dividendo per n log s = n:
m
m 1
≤ log t ≤
+ .
n
n
n
Fissato ε > 0, si può quindi prendere n abbastanza grande perché | m
− log t| < ε. Per la
n
monotonia di A(n) (proprietà 2):
A(sm ) ≤ A(tn ) ≤ A(sm+1 )
e cioè
mA(s) ≤ nA(t) ≤ (m + 1)A(s)
3
da cui, ponendo K := A(s) e dividendo per nA(s) = nK:
m
A(t)
m 1
≤
≤
+ ,
n
K
n
n
− A(t)
| < ε per n ≫ 1. Quindi | log t − A(t)
| < 2ε per n ≫ 1, ma dal momento che
ovvero | m
n
K
K
il termine da maggiorare è indipendente da n ciò significa che
A(t) = K log t,
(1)
con K positiva per soddisfare la 2.
Osserviamo che scegliere un’altra base per il logaritmo corrisponde esattamente a modificare la K, moltiplicandola per una costante che dipende solo dalle due basi in considerazione.
Supponiamo ora di poter scegliere tra m possibilità con probabilità razionali pi = Pmni ni ,
i=1
P
ni ∈ N ∀ i = 1, . . . , m. Osserviamo che possiamo decomporre una scelta tra m
i=1 ni possibilità equiprobabili in una scelta tra m possibilità con probabilità p1 , . . . , pm e poi, se si è
scelta i, un’ulteriore scelta tra ni eventi equiprobabili. Usando
Pmancora la condizione 3 e la (1)
eguagliamo le due espressioni per l’entropia della scelta tra i=1 ni possibilità equiprobabili:
X X X
X
A
ni = K log
ni = H(p1, . . . , pm )+
pi A(ni ) = H(p1, . . . , pm )+K
pi log ni .
Dunque:
H
n
n
P 1 , . . . , Pm
ni
ni
X
X
X
pi log
ni −
pi log ni
X
ni
= −K
pi log P
ni
X
= −K
pi log pi .
= K
(2)
Se le pi non sono razionali possono essere approssimate da razionali e H deve mantenere
la stessa espressione per continuità (proprietà 1): perciò la (2) vale in generale.
La scelta più naturale per l’unità di misura dell’informazione (e quindi dell’incertezza) è il
bit, che rappresenta la scelta tra due possibilità equiprobabili: 0/1, on/off... di conseguenza, i
logaritmi nella (2) saranno in generale in base 2. Comunque, come già osservato, un cambio di
base del logaritmo corrisponde semplicemente alla moltiplicazione per una costante positiva
K.
Il nome “entropia” non è un’invenzione di Shannon: già in meccanica statistica si usava per
definire (l’opposto de) la quantità di informazione derivante dalla scelta fra tutti i microstati
corrispondenti ad un dato macrostato... si veda anche la citazione inziale.
Definizione 2.1. Date due variabili aleatorie X, Y la loro entropia congiunta (joint entropy)
è l’entropia della loro distribuzione congiunta, ovvero:
X
H(X, Y ) := −
P (X = α, Y = β) log P (X = α, Y = β).
α,β∈A
4
3
L’entropia di una sorgente di informazione
Ricordiamo: sorgente d’informazione = processo stocastico. Per noi d’ora in avanti la
sorgente sarà sempre stazionaria (ipotesi pesantina nel mondo reale...).
Definizione 3.1. Fissato n ≥ 1, la block entropy (entropia a blocchi ) di ordine n della
sorgente {Xn } è l’entropia congiunta delle prime n variabili aleatorie del processo, ovvero:
X
P (X1n = an1 ) log P (X1n = an1 ).
(3)
H(X1n ) = H(X1 , . . . , Xn ) = −
n
an
1 ∈A
Nel caso stazionario si può sostituire (X1 , . . . , Xn ) con qualsiasi sequenza di n componenti
consecutive del processo; in tal caso useremo, come sopra, la notazione P (an1 ) = P (Xii+n−1 =
an1 ).
Definizione 3.2. L’entropia della sorgente {Xn } è definita come:
H({Xn }) := lim sup
n→∞
H(X1n )
.
n
Si può provare [3, p. 59] che nel caso stazionario il lim sup è in realtà un lim.
Per sorgenti ergodiche vale il seguente importantissimo
Teorema 3.1. Sia {Xn } sorgente ergodica e A finito. Allora per quasi ogni sequenza a ∈ AN
vale:
1
(4)
lim − log P (an1 ) = H({Xn }).
n→∞
n
Il teorema 3.1 è detto Asymptotic Equipartition Property in teoria dell’informazione e
Teorema di Shannon-McMillan-Breiman (dai nomi di coloro che lo dimostrarono per casi
sempre più generali) in teoria ergodica. Una dimostrazione del risultato generale, tratta da
[1], si trova in [3, pp. 51-55]. Qui ne diamo solo la dimostrazione per sorgenti markoviane,
una caso più ristretto ma non troppo lontano da quel che ci si può aspettare nel caso reale.
Definizione 3.3. Un processo {Xn } si dice markoviano se ∀ n ≥ 1, ∀ an+1
∈ An+1 vale:
1
P (Xn+1 = an+1 |X1n = an1 ) = P (Xn+1 = an+1 |Xn = an ).
Equivalentemente, {Xn } si dice markoviano se ∀ n ≥ 1, ∀ an+1
∈ An+1 vale:
1
P (X1n+1
=
an+1
)
1
= P (X1 = a1 )
n
Y
P (Xi+1 = ai+1 |Xi = ai ),
i=1
con P (Xi+1 = ai+1 |Xi = ai ) indipendente dall’indice i della componente di {Xn }.
Si può pensare un processo markoviano come una sorgente con “memoria finita”: ogni
nuovo simbolo generato dipende solo dal simbolo che è stato generato precedentemente, e non
da tutto quello che è stato generato prima. Si può generalizzare questo concetto a memoria
di lunghezza k (processi markoviani di ordine k), ma poiché è sempre possibile ricondursi al
caso di memoria 1 considereremo solo questo nel seguito.
5
Definizione 3.4. Siano X, Y due variabili aleatorie su (Ω, S, P ). L’entropia di Y condizionata ad X è definita come:
X
P (X = α, Y = β) log P (Y = β|X = α).
H(Y |X) := −
α,β∈A
Proposizione 3.2. L’entropia condizionata ha le seguenti proprietà (dimostrazione ad esempio in [3, pp. 59-61]):
A) H(Y |X) ≥ 0 e H(Y |X) = 0 ⇔ Y = X (se X = Y e conosco X, non c’è nessuna
incertezza residua su Y )
B) H(Y |X) ≤ H(Y ) (la conoscenza di X non può aumentare l’incertezza di Y )
e H(Y |X) = H(Y ) ⇔ X, Y sono statisticamente indipendenti (in questo caso conoscere
X non mi dà nessuna informazione su Y ).
C) H(X, Y ) = H(Y |X) + H(X) (legge di addizione)
La dimostrazione del teorema 3.1 nel caso markoviano richiede una proposizione preliminare.
Proposizione 3.3. Se {Xn } è una sorgente markoviana stazionaria ed ergodica si ha:
X
Pα P (β|α) log P (β|α),
H({Xn }) = −
α,β∈A
dove {Pα }α∈A = {P (Xn = α)}α∈A è la distribuzione stazionaria del processo (la cui esistenza
e unicità è assicurata dall’ergodicità del processo) e P (β|α) indica la probabilità di transizione
P (Xn+1 = β|Xn = α), indipendente da n per la stazionarietà.
Dimostrazione. Dimostriamo innanzitutto che per sorgenti markoviane
H({Xn }) = lim H(Xn+1|X1n ).
n→∞
Infatti per la (C) di 3.2 con X = X1n , Y = Xn+1 , è H(Xn+1 |X1n ) = H(X1n+1 ) − H(X1n ) e,
poiché la successione H(Xn+1|X1n ) è (debolmente) decrescente in n per (B) e non negativa
per (A), essa ha un limite, che chiamiamo ℓ. Poniamo poi en := H(X1n ), l’entropia a blocchi
di ordine n; poiché en+1 − en = H(Xn+1|X1n ) −−−→ ℓ, si ha per il Teorema di Cesàro che
en
−−−→
n n→∞
n→∞
ℓ. Ma per definizione di entropia di una sorgente
l’unicità del limite,
limn→∞ H(Xn+1 |X1n )
en
−−−→
n n→∞
H({Xn }) e dunque, per
= H({Xn }).
Ora:
H(Xn+1|X1n ) = −
X
P (an+1
) log P (an+1 |an1 )
1
an+1
∈An+1
1
= −
X
an ,an+1
= −
X


log P (an+1|an ) 
X
an−1
1
P (a1 , . . . , an−1 , an , an+1 )
log P (an+1 |an )P (an , an+1 )
an ,an+1
= H(Xn+1 |Xn ) = (ancora per stazionarietà) H(X2 |X1 ).
6

E quindi:
H({Xn }) = lim H(Xn+1 |X1n ) =
lim H(X2 |X1 ) = H(X2|X1 )
X
= −
P (X1 = α, X2 = β) log P (X2 = β|X1 = α)
n→∞
n→∞
α,β∈A
= −
X
Pα P (β|α) log P (β|α).
α,β
Dimostrazione del Teorema di Shannon-McMillan-Breiman per sorgenti markoviane. La proposizione 3.3 ci dà una forma esplicita per l’entropia di un processo markoviano. Vediamo ora
log P (an )
la convergenza di − n 1 all’entropia nel caso ergodico. Poiché la sorgente è markoviana
si può scrivere:
P (an1 ) = Pa1 P (a2 |a1 )P (a3 |a2 ) . . . P (an |an−1 )
e dunque
log P (an1 )
= log Pa1 +
n−1
X
log P (ai+1 |ai ).
(5)
i=1
Per l’ergodicità (legge dei grandi numeri) per ogni sottosequenza di due caratteri αβ, con
α, β ∈ A, e per quasi ogni a ∈ AN , fan1 (αβ) −−−→ P (αβ). Poiché P (αβ) = Pα P (β|α), il
n→∞
numero di occorrenze della coppia αβ nella sequenza an1 , per n abbastanza grande, è dunque
nfan1 (αβ) = n [Pα P (β|α) + o(n)] ,
con o(n) → 0 per n → ∞. Dunque la (5) diventa:
X
log P (an1 ) = log Pa1 +
n [Pα P (β|α) + o(n)] log P (β|α),
α,β∈A
da cui, dividendo per n e cambiando segno:
X
X
1
1
− log P (an1 ) = − log Pa1 −
Pα P (β|α) log P (β|α) −
o(n) log P (β|α).
n
n
α,β
α,β
(6)
Ma il primo e il terzo termine della (6) si annullano per n → ∞, mentre il secondo è l’entropia
H({Xn }) della sorgente.
4
Entropia e Codici
Vediamo ora come questa entropia introdotta sia legata ai compressori. Quando parliamo
di compressori dovete pensare ai comuni compressori che utilizzate quotidianamente per
comprimere file sui vostri computer (bzip, gzip, etc...).
Comprimere una sequenza an1 (i cui caratteri appartengono ad un certo alfabeto A)
significa mappare tale sequenza in un’altra sequenza bl1 dalla quale sia poi possibile ricostruire
an1 . Per poter avere una compressione, bisogna fare in modo che le parole di codice siano
piu’ corte possibili (in senso medio).
Ovviamente, piu’ riesco a ridurre questa lunghezza piu’ sono contento...allora, quanto e’
possibile comprimere?! Esistono dei particolari tipi di codici, chiamati codici a prefisso, per i
quali esiste una connessione fra la lunghezza della parole di codice e l’entropia della sorgente.
7
4.1
Codici binari
Definizione 4.1. Un codice su un alfabeto A è una funzione
C : A → B∗
dove con B∗ indichiamo l’insieme di tutte le sequenze costrutite sull’alfabeto B (generalmente
parleremo di codici binari, in cui cioè B = {0, 1}).
Fra tutti i codici possibili un sottoinsieme significativo è rappresentato dai codici non
singolari in cui si richiede semplicemente che la funzione C sia iniettiva per garantire che
una sequenza s ∈ A∗ possa essere codificata, applicando C ad ogni carattere di s, in maniera
reversibile.
Se richiediamo che ogni parola di codice appartenente a B∗ corrisponda ad un unico
carattere dell’alfabeto A (codice non singolare) e che un eventuale destinatario sia in grado di poter univocamente ricostruire la sequenza di partenza, allora il codice è chiamato
univocamente decifrabile (o decodificabile) (UD).
Notiamo che non tutti i codici sono UD:
Esempio 4.1. Sia A = {a, b, c} e C tale che:
C
C
C
a 7→ 0 ; b 7→ 1 ; c 7→ 01
In questo caso, se ci trovassimo di fronte la sequenza 01 non sapremmo in maniera univoca
ricostruire la sequenza di caratteri originaria, infatti 01 potrebbe corrispondere a c ma anche
ad ab.
Fra tutti i codici UD ne esiste una sottoclasse, chiamati codici a prefisso, che hanno la particolarità di essere codici UD, e quindi univocamente decifrabili, ma in piu’ non permettono
ritardi di codifica...
Definizione 4.2. Un codice C si dice a prefisso se nessuna parola di codice (cioè una parola
w ∈ C(A)) è prefisso di un’altra parola di codice; in altre parole, per nessuna parola di codice
w1n ∈ C(A) esiste un’altra parola di codice v1k ∈ C(A), k < n tale che w1k = v1k .
Facciamo un esempio:
Esempio 4.2. Consideriamo due differenti codici che codificano tre lettere di un alfabeto
A = {a, b, c}: un codice C1 (A) = {1, 10, 100} che è un codice UD (non ci sono ambiguità
per un eventuale decodifica) ma non è un codice a prefisso perché la parola di codice 1 è
prefisso di un’altra parola di codice 10 (come pure 10 è prefisso di 100). Il secondo codice
che consideriamo, invece, è un codice a prefisso: C2 (A) = {0, 10, 11} (è UD e in piu’ nessuna
parola di codice è prefisso di un’altra).
Supponiamo di avere una sequenza codificata come 1010100.
Per ottenere la sequenza di partenza con caratteri in A (ovvero, per poter decodificare
la sequenza) devo poter individuare lungo la sequenza di B∗ le parole di codice alle quali poi
associare le lettere della sequenza di partenza.
L’individuazione di queste parole di codice nel caso sia stato utilizzato il codice C1 non è
immediata: fin dal primo carattere, quando leggo 1, posso dire con certezza che la parola di
codice è effettivamente 1 solo se il carattere successivo non è zero; e questo lo posso sapere
solo continuando a leggere la sequenza! In questo caso, dopo l’ 1 abbiamo uno 0 ... anche
questa volta dobbiamo ancora procedere nella lettura della sequenza per verificare il carattere
8
successivo a 10: abbiamo un 1 (e non 0). Quindi, tornando indietro di un passo lungo la
sequenza (per questo si parla di ritardi nella codifica..), possiamo dire con certezza che la
prima parola di codice lungo la sequenza è 10, che corrisponde alla lettera b. Procedendo,
si ottengono le seguenti parole di codice:
10 | 10 | 100
che corrispondono alla sequenza bbc.
Se invece la stessa sequenza fosse stata codificata dal codice C2 , l’individuazione delle parole di codice lungo la sequenza non avrebbe richiesto un proseguimento nella lettura, ovvero
sarebbe stata istantanea (infatti i codici a prefisso sono anche chiamati codici istantanei):
10 | 10 | 10 | 0
alla quale corrisponde, nell’alfabeto A, la sequenza bbba.
E’ chiaro che se si vuole comprimere dati senza perdere informazione su essi (che significa
che dobbiamo poi essere in grado, una volta ottenuta la sequenza compressa, di tornare
indietro alla sequenza originale), un buon codice deve essere almeno un codice UD; se poi è
anche un codice a prefisso tanto meglio, perché ci permetterà di essere piu’ veloce in fase di
decodifica.
Ancora, sempre in vista di una buona compressione, è chiaro che saremo interessati a
codici dai quali riottenere la sequenza originaria senza ambiguita’ e in maniera “veloce”, ma
ci interessa anche che le lunghezze delle parole di codice non siano troppo grandi... quanto
brevi possono essere le parole di un codice UD? La diseguaglianza di Kraft risponde a questa
domanda:
Teorema 4.1. Se C : A → {0, 1}∗ è un codice Univocamente Decodificabile, con parole
di codice lunghe li = |C(ai )|, i = 1, . . . |A| = m, allora vale la seguente diseguaglianza
(Diseguaglianza di Kraft):
m
X
2−li ≤ 1
(7)
i=1
Notiamo che il teorema, scritto per codici UD, vale anche per il caso particolare di codici
a prefisso: questo ci dice che non vi è nulla da guadagnare, in termini di possibili scelte per
le lunghezze delle parole di codice, passando dall’insieme dei codici istantanei a quello piu’
ampio dei codici univocamente decodificabili. Conviene dunque, per il discorso fatto sopra
della velocità di decodifica, restringersi ai codici a prefisso. Vale anche il teorema “inverso”:
Teorema 4.2. Se gli interi l1 , . . . , lm verificano la diseguaglianza di Kraft (7), allora esiste
un codice a prefisso con parole di codice di lunghezza l1 , . . . , lm .
(Per la dimostrazione dei teoremi rimandiamo a [4] o [3]).
Quello che interessa a noi ora, come dicevamo all’inizio, è rendere minima la lunghezza
media di queste parole di codice, sotto il vincolo che questi codici siano istantanei (e quindi
che valga la diseguaglianza di Kraft (7)).
La soluzione di questo problema di minimizzazione è legata all’entropia.
Piu’ precisamente:
Denotiamo con LC (a) la funzione che associa a ciascun a ∈ A la lunghezza della parola
di codice C(a):
9
LC : A → N
a 7→ |C(a)|
La lunghezza media delle parole del codice C, relativa alla distribuzione di probabilità pi
di una variabile aleatoria X (pi = P (X = ai )), è per definizione:
X
EX (LC ) =
pi LC (ai ).
(8)
i
Ricordiamo la definizione di entropia di una variabile aleatoria X data precedentemente:
X
pi log pi .
(9)
H(X) = −
i
Confrontandola con la lunghezza media di un codice, l’entropia puo’ essere vista come la
lunghezza media di un codice che utilizza − log pi bits per codificare ai .
Sarà una buona scelta questo codice che utilizza − log pi ?!, ovvero, è una scelta che mi
minimizza (in media) la lunghezza delle parole di codice?
Attraverso i due teoremi seguenti, faremo vedere che non solo è una buona scelta, ma
meglio di così non possiamo fare! Infatti, per codici a prefisso si dimostra che l’entropia è
un limite inferiore alla lunghezza media delle parole di codice:
Teorema 4.3. i) Per ogni codice C Univocamente Decodificabile
EX (LC ) ≥ H(X)
(con uguaglianza se e solo se LC (ai ) = − log pi )
ii) Esiste un codice prefisso tale che
EX (LC ) ≤ H(X) + 1
Per dimostare questo teorema abbiamo bisogno di introdurre un piccolo lemma:
Lemma 4.4. Se p = (p1 , . . . , pm ) e q = (q1 , . . . , qm ) sono due distribuzioni di probabilità,
allora
X
X
pi log pi ≥
pi log qi
(10)
i
i
con uguaglianza se e solo se p = q
Dimostrazione. Basta osservare che il logaritmo è una funzione concava e quindi vale log x ≤
x − 1 (con uguaglianza se e solo se x = 1). Così:
X
X qi
X
X
qi
pi log ≤
pi ( − 1) ≤
qi −
pi = 0
(11)
pi
pi
i
i
i
i
con uguaglianza se e solo se qi = pi . Quindi:
prova il teorema.
P
i
10
pi log pqii =
P
i
pi log qi −
P
i
pi log pi ≤ 0 che
In verità, per dimostrare il lemma è sufficiente che q sia tale che
La quantità
X
X
pi
qi
pi log = −
pi log
qi
pi
i
i
P
i qi
≤ 1.
(12)
è chiamata divergenza di Kullback-Leibler o entropia relativa, o più semplicemente divergenza, fra due distribuzioni di probabilità p e q, ed è una quantità sempre positiva.
Torniamo ora alla dimostrazione del teorema:
Dimostrazione. i) Sia C un codice UD.
X
X
E(LC ) =
pi LC (ai ) =
pi log 2LC (ai )
i
=
X
pi log
pi
i
−
X
pi log pi
−LC (ai )
2
i
i
X
pi
=
pi log −L (a ) + H(X).
2 C i
i
−LC (ai )
Il primo
,
P termine è la divergenza fra la distribuzione di probabilità pi e qi = 2
dove i qi ≤ 1 per P
la diseguaglianza di Kraft. La divergenza è una quantità sempre
pi
positiva e quindi :
i pi log 2−LC (ai ) + H(X) ≥ H(X), con uguaglianza se e solo se
pi = 2−LC (ai ) .
ii) Dalla dimostrazione precedente, se − log pi = L(ai ) allora E(L) = H(X). Ma in generale
− log pi potrebbe non essere un numero intero... Impongo L(ai ) = ⌈− log pi ⌉, cioè il
più piccolo intero maggiore o uguale a − log pi . Gli L(a1 ), . . . , L(am ) sono interi che
soddisfano la disuguaglianza di Kraft; infatti:
X
X
X
2−L(ai ) ≤
2log pi =
pi = 1.
i
i
i
Per il teorema 4.2 esiste allora un codice a prefisso C t.c. LC (ai ) = L(ai )
Ora, poiché LC (ai ) ≤ 1 − log pi ne verrà:
X
EX (LC ) =
pi LC (ai )
i
≤
X
(1 − log pi )pi = 1 −
X
pi log pi
i
i
= 1 + H(X)
Concludendo: abbiamo dimostrato che in effetti − log pi è la scelta ottimale per la lunghezza media delle parole di codice, ovvero che l’entropia è la lunghezza media ottimale.
Le stime ora ottenute (H(Xn ) ≤ E(LC ) ≤ H(Xn ) + 1)), però, non ci assicurano un raggiungimento del valore dell’entropia, anzi, potremmo essere abbastanza al di sopra di tale
valore.
Facciamo un esempio che ci evidenzi questo fatto:
11
Esempio 4.3 (Codice di Huffman). Supponiamo di avere un alfabeto A = {a, b, c, d} e di
conoscere le probabilità di apparizione delle lettere dell’alfabeto A in una sequenza simbolica
X: per esempio P(a)=0.4, P(b)=0.3, P(c)=0.25 e P(d)=0.05.
Dopo aver ordinato i caratteri in modo decrescente in base ai valori delle loro probabilità,
si divide l’insieme iniziale {a, b, c, d} in 2 sottoinsiemi, uno composto dalla lettera piu’ probabile {a} e l’altro dai restanti caratteri {b, c, d}. Assegnamo la parola di codice 0 alla scelta
di a, 1 alla scelta di {b, c, d}. Ora si ripete la procedura sull’insieme {b, c, d} e si associa la
parola di codice 0 se si sceglie la lettera piu’ frequente (all’interno di questo insieme) b, 1 se
si sceglie l’insieme delle lettere restanti {c, d}.
La lettera b avra’ parola di codice associata uguale a 10. In maniera iterativa, si ottengono
le parole di codice per tutte le lettere dell’alfabeto.
In sintesi, il codice ottenuto è: (nota che è un codice a prefisso)
a
b
c
d
0
10
110
111
In figura 2 e’ rappresentato l’albero che si ottiene con questa procedura.
Come si può notare anche visivamente dall’albero, il codice opera in modo da assegnare parole di codice piu’ corte alle lettere piu’ frequenti (e piu’ lunghe per caratteri meno
frequenti).
Osserviamo che nell’esempio la lunghezza media del codice è uguale a:
E(L) = P (a)L(a) + P (b)L(b) + P (c)L(c) + P (d)L(d) = 1.9
ed, ovviamente,
E(L) > H(X) = −[P (a) log P (a) + P (b) log P (b) + P (c) log P (c) + P (d) log P (d)] = 1.766
Figura 2: esempio codice Huffman
Passiamo ora da una singola variabile aleatoria ai processi.
4.2
n-Codici
Consideriamo ora la funzione (n-Codice) definita:
Cn : An → B∗
12
che mappa sequenze di lunghezza n in parole binarie. Analogamente a prima, denotiamo la
L (an )
lunghezza di codice per simbolo con Cnn 1 e la lunghezza media con E{Xn } (LCn )
Sia H(X1n ) l’entropia a blocchi definita come in (3).
Considerando Cn come un codice sull’alfabeto An , il teorema 4.3 i) diventa:
1
H(X1n )
≤ E{Xn } (LCn )
n
n
(13)
per ogni n-codice a prefisso, mentre il teorema 4.3 ii) prova l’esistenza di un n-codice a
prefisso Cn tale che
H(X1n ) 1
1
E{Xn } (LCn ) ≤
+
(14)
n
n
n
Una sequenza {Cn } tale che, per ogni n, Cn è un n-codice a prefisso con lunghezza associata
L(an1 ) = LCn (an1 ), sarà chiamata una sequenza di codici a prefisso. Il rate di una tale sequenza
di parole di codice, relative a un processo {Xn }, è definito:
R({Cn }) := lim sup
n→∞
E(LCn )
n
(15)
I due risultati (14) e (15) portano al seguente teorema (Teorema I.7.12 in [3]):
Teorema 4.5 (Entropia di un processo e codici a prefisso). Se {Xn } è un processo stazionario
con entropia H, allora:
i) Esiste una sequenza di codici a prefisso {Cn } tale che R({Cn }) ≤ H
ii) Non esiste una sequenza di codici a prefisso {Cn } tale che R({Cn }) < H
Quindi: esistono codici buoni, cioè è possibile comprimere al limite fino al valore dell’entropia, ma non esiston codici “troppo” buoni, cioè nessuna sequenza di codici può asintoticamente comprimere meno del valore dell’entropia del processo.
Questo teorema ci garantisce l’esistenza di un codice ottimale per una singola sorgente,
dove la sorgente è NOTA.
Nel mondo reale, però, si lavora su dati/sequenze per le quali la sorgente non è nota... quindi dobbiamo chiedere molto di piu’ ai nostri compressori! Chiediamo che siano
universalmente asintoticamente ottimali, o piu’ semplicemente, universali:
Definizione 4.3. Una sequenza di codice {Cn } è detta universale se
lim sup
n→∞
LCn (an1 )
≤ H({Xn }) quasi certamente
n
per ogni processo ergodico {Xn }.
Teorema 4.6 (Esistenza dei Codici Universali). Esiste una sequenza di codici a prefisso {Cn }
L (an )
tale che lim supn Cnn 1 ≤ H({Xn }) quasi certamente, per ogni processo ergodico {Xn }.
Teorema 4.7 (Codici troppo buoni non esistono). Se {Cn } è una sequenza di codici non
L (an )
singolari allora lim inf n Cnn 1 ≥ H({Xn }) quasi certamente.
Per concludere vediamo ora un esempio di compressore universale.
13
Esempio 4.4 (L’algoritmo LZ78). Quello che presenteremo ora è un algoritmo di codifica
proposto da Lempel e Ziv nel 1978 in [5] ed è attualmente alla base di molti comuni e popolari
compressori presenti nei nostri computer.
L’algoritmo è basato su una particolare procedura di segmentazione (parsing) di una
sequenza che permette di scrivere una sequenza infinita a ∈ AN come concatenazione di
blocchi di lunghezza variabile, chiamati parole:
a = w1 w2 . . .
.
L’insieme delle parole così formate è chiamato dizionario della sequenza (D(x) = {w1 , w2 , . . .}).
Nel caso dell’algoritmo LZ78 la regola di parsing può essere sintetizzata nella frase: “scegli la prossima parola in modo che sia la piu’ corta nuova parola non ancora apparsa nel
dizionario”.
Facciamo un esempio: consideriamo una sequenza
s = aababbbbaababb...
Seguendo la regola scritta sopra, dobbiamo ‘tagliare’ la sequenza in modo da ottenere le
parole che poi andranno codificate. Si incomincia a leggere la sequenza: ovviamente il primo
carattere sarà sicuramente una parola nuova, mai incontrata, quindi il primo taglio lungo la
sequenza sarà fatto proprio dopo la prima ‘a’ e la lettera a andrà a far parte del dizionario
della sequenza. Ora leggo il secondo carattere, che è ancora la lettera a: questo è già presente
nel dizionario, quindi non è una nuova parola, quindi continuo a leggere finchè non trovo
una parola non presente nel dizionario. In questo caso non devo andare molto lontano, basta
leggere il carattere sucessivo e trovare la parola ab che è una nuova parola, e aggiungerla al
dizionario. Si procede in questo modo fino alla fine della sequenza, ottenendo un dizionario
con tutte le parole.
Ogni parola cosi’ creata puo’ essere vista come composta da due parti: un prefisso corrispondente ad una parola già apparsa nel dizionario piu’ un suffisso costituito da un nuovo carattere; il prefisso di ogni parola può essere identificato con la posizione che ha nel
dizionario.
La sequenza in esempio, seguendo questa regola di parsing, diventa concatenazione delle
seguenti parole:
s = a|ab|abb|b|ba|aba|bb....
Ora queste parole vanno mappate in parole binarie (codificate); il codice LZ (Lempel
e Ziv) mappa dunque la stringa s nella concatenazione delle parole ottenute dal parsing
codificate.
Non esponiamo ora il tipo di codice a prefisso che si viene a costruire su queste parole
del parsing; in maniera molto approssimativa diremo solo che l’output dell’algoritmo di
compressione sarà dato dalla codifica binaria della posizione del prefisso nel dizionario e del
nuovo carattere.
Nella tabella che segue abbiamo scritto le coppie corrispondenti ad ogni parola del dizionario per la sequenza s d’esempio; la prima colonna è il numero che indica la posizione
nel dizionario della parola codice la cui coppia corrispondente è mostrata nella stessa linea,
in seconda colonna. Per facilitare la lettura, aggiungiamo una terza colonna che mostra
ciascuna parola codificata nella stringa originale s, ma notiamo che questa non è contenuta
nel file di output:
14
1
2
3
4
5
6
7
(0,a) [a]
(1,b) [ab]
(2,b) [abb]
(0,b) [b]
(4,a) [ba]
(2,a) [aba]
(4,b) [bb]
...
Se con C indichiamo il numero di parole ottenute con questo tipo di parsing (ovvero la
cardinalità del dizionario finale), il costo di codifica, cioè il numero di bit spesi per codificare
queste parole, sarà approssimativamente dato dal numero di bit necessari a codificare il
prefisso, cioè la posizione nel dizionario, + il numero di bit necessari a codificare il nuovo
carattere, ovvero (al più) C log n bit per codificare le posizioni nel dizionario e C log |A| bit
per codificare i nuovi caratteri.
Quando si va a considerare il rate (costo di codifica diviso per la lunghezza originaria
n della sequenza), al limite per n → ∞ il termine dominante in questa codifica è C log n,
e dunque per stabilire l’universalità dell’algoritmo di compressione LZ78 basta provare il
seguente teorema di Ziv [7], nel quale C(an1 ) denota il numero di parole ottenute con il
parsing ora descritto per la sequenza an1 :
Teorema 4.8. Se {Xn } è un processo ergodico con entropia H({Xn }), allora
1
C(an1 ) log n −−−→ H({Xn }) quasi certamente.
n→∞
n
Ovviamente basta dimostrare che l’entropia è un limite superiore, poiché per il teorema
4.7 nessun codice puo’ comprimere superando l’entropia.
Due considerazioni finali: il teorema 4.8 ci assicura l’esistenza di un codificatore ottimale.
Non ci dice nulla, però, sulla velocità di convergenza all’entropia; per avere tale informazione
sono necessarie stime accurate sul costo effettivo del codice LZ implementato, come riportato
in [6] e [5] da Ziv e Lempel per gli algoritmi LZ78 e LZ77 (ma questi conti li lascerei agli
informatici...).
La seconda considerazione: con i codificatori alla LZ abbiamo degli strumenti in grado di
comprimere sequenze simboliche senza conoscerne a priori la statistica: questo ovviamente li
rende molto piu’ veloci dei cosiddetti codificatori statistici, come il codice di Huffman prima
spiegato, che prima di operare la codifica devono leggere tutta la sequenza per registrare le
frequenze dei caratteri (o parole) presenti.
Il codificatore LZ, al contrario, codifica la stringa sequenzialmente, mentre la legge,
utilizzando per la compressione le ridondanze all’interno della sequenza stessa.
Riferimenti bibliografici
[1] D. Ornstein, B. Weiss, The Shannon-McMillan-Breiman theorem for amenable groups,
Israel Journal of Mathematics 44 (1983), 53-60.
[2] C.E. Shannon, A Mathematical Theory of Communication, The Bell System Technical
Journal 27 (1948), 379-423, 623-656.
15
[3] P.C. Shields, The Ergodic Theory of Discrete Sample Paths, American Mathematical
Society (1996).
[4] T.M. Cover, J.A.Thomas, Elements of Information Theory, New Jork: Wiley (1991)
[5] J. Ziv, A. Lempel Compression of individual sequences via variable-rate coding, IEEE
Transactions on Information Theory, IT-24, n 5 (1978), 530-536,
[6] J. Ziv, A. Lempel A Universal Algorithm for Sequential Data Compression”, IEEE
Transactions on Information Theory, 23, n 3, (1977) 337-343
[7] J. Ziv Coding theorems for individual sequences, IEEE Transactions on Information
Theory IT-24 (1978), 405-412
16