Algoritmy komprese dat Úvod do teorie informace
Claude Shannon (1916 – 2001)
5.11.2014
NSWI072 - 7
Teorie informace Informace • Co je to informace? • Můžeme informaci měřit? • Existují teoretické meze pro délku zprávy nesoucí danou informaci?
2
Hartleyho vzorec Motivační hra: Informace obsažená ve zprávě • •
minimální # otázek typu ANO/NE kterými lze odhalit obsah zprávy
Ralph Hartley (1928) Je-li neznámá x prvkem n prvkové množiny, pak informace, kterou x nese, má hodnotu log2 n bitů.
3
Hartleyho vzorec |H| = n, (x1 ,…, xk) ∈ Hk Buď Sk nejmenší # otázek, nutný k určení všech xi log2nk ≤ Sk < log2nk +1 log2n ≤ Sk / k ≤ log2n + 1/k ☞ Závěr Sk / k = průměrný # otázek potřebných k určení jednoho prvku
4
Shannonův vzorec Buď X diskrétní náhodná veličina s oborem hodnot H a pravděpodobnostní funkcí p(x) = P(X=x) pro x ∈ H ☀ Pozorování: |H| = n, p(x) = 1/n pro každé x ∈ H ⇒ log2n = log2 1/p(x) = Σx∈H p(x) log2 1/p(x) Claude Shannon (1948): Entropie H(X) diskrétní náhodné veličiny X s oborem hodnot H je definována vztahem
5
Entropie ☀ Příklady • •
motivační hra: H - množina hádaných osob kódování: H - abeceda zpráv, X - zdroj informace
☝Zdůvodnění • • •
analogie ze statistické mechaniky (Ludwig Boltzmann, 1872) axiomatický přístup souvislost s kódováním
6
Základní vlastnosti ☝Věta. H(X) ≥ 0. ☝Lemma. Nechť
. Pak
a rovnost nastane právě když pi=qi pro každé 1≤ i ≤ k. ☝Věta. Pro náhodnou veličinu X s konečným oborem hodnot H, |H|=n, platí H(X) ≤ log n, přičemž rovnost nastane právě tehdy, když p(x) = 1/n pro každé x ∈ H. 7
Entropie – axiomatický přístup ☝Věta. Nechť posloupnost funkcí Hn(p1, p2, ... , pn), n=2,3,..., splňuje následující axiomy • H2(1/2, 1/2) = 1 • H2(p,1-p) je spojitá v oboru 0 ≤ p ≤ 1 • Hn+1(p1,...,pn-1,q1,q2) = Hn(p1,...,pn) + pn H2(q1/pn, q2/pn), kde pn =q1+q2 >0, pi ≥ 0, p1+...+pn = 1.
Pak pro n=2,3,... platí Hn (p1 , p2 , . . . , pn ) =
n X i=1
8
pi log2 pi
✎ Problémy ➀ Definujte entropii pro diskrétní náhodný vektor X ➁ Rozhodněte, zda platí: Pro n-rozměrný náhodný vektor X=(X1,...,Xn), jehož složky jsou nezávislé náhodné veličiny se stejným rozdělením psti, platí H(X) = n ⋅ H(Xi).
9
Teorie informace × teorie kódování Kód C pro diskrétní náhodnou veličinu X s oborem hodnot H je zobrazení C: H → {0,1}*. Kód C generuje kódování C*: H* → {0,1}* definované C*(x1...xk) = C(x1)...C(xk). Kód C je jednoznačně dekódovatelný, pokud u,v ∈ H*, C*(u)=C*(v) ⇒ u = v . Průměrnou délku kódového slova L(C) kódu C • pro diskrétní náhodnou veličinu X • s pravděpodobnostní funkcí p(x)
definujeme jako L(C)=Σx∈H p(x)|C(x)|. 10
Horní a dolní odhady ☝Věta (Kraft-McMillan) Délky l1,l2, … kódových slov jednoznačně dekódovatelného kódu C splňují ∑i 2-li ≤ 1. Naopak, pokud přirozená čísla l1,l2, … splňují tuto nerovnost, pak existuje prefixový kód s kódovými slovy o těchto délkách. ☝Věta Buď C jednoznačně dekódovatelný kód pro náhodnou veličinu X. Pak H(X) ≤ L(C). 11
Horní a dolní odhady ☝Věta. Pro libovolný optimální prefixový kód C pro náhodnou veličinu X platí H(X) ≤ L(C) < H(X) + 1 . ☞ Důsledek. Pro průměrnou délku kódového slova L Huffmanova kódu platí H ≤ L < Η + 1.
12
☀ Příklad znak
četnost
entropie
E
20
1.26 bitu
Huffmanův kód 1 bit
A
20
1.26 bitu
2 bity
X
3
4 bity
3 bity
Y
3
4 bity
4 bity
Z
2
4.58 bitu
4 bity
13
Huffmanův kód nad rozšířenou abecedou A = {a1 , . . . , am } n-krát
n-krát
✎ Problém
{
{ {
A(n) = {a1 a1 . . . a1 , a1 a1 . . . a2 , . . . , am am . . . am } n-krát
• odvoďte dolní a horní odhad pro průměrnou délku kódového slova Huffmanova kódu nad abecedou rozšířenou na bloky n znaků • můžete předpokládat, že znaky zpráv jsou » nezávislé » se shodným rozdělením psti » a entropií H 14
Analýza aritmetického kódování Buď X diskrétní náhodná veličina s oborem hodnot H = {1,2,3,...} a pravděpodobnostní funkcí p ☝Poznámka: Obor hodnot n.v. X = množina zpráv, které budeme kódovat Položme F(x) = P(X ≤ x) = Σy≤x p(y) = ½(F(x-1) + F(x)) = 0.y1 y2 y3... • yi ∈ {0,1}
Pro x ∈ H položme C(x) = y1 y2 ...yl(x) • l(x) = ⎡log2 1/p(x) ⎤ + 1 ☝Závěr: Pak C je prefixový kód pro X splňující
H(X) ≤ L(C) < Η(X) + 2 . 15
Analýza pravděpodobnostního modelu Při popisu algoritmu aritmetického kódování jsme použili následující předpoklad: C je kódování pro náhodný vektor X = (X1,...,Xm) takový, že X1,...,Xm jsou • nezávislé náhodné veličiny • se stejným rozdělením pravděpodobností
Pro X = (X,...,X) pak platí H(X) ≤ L(C) ≤ Η(X) + 2 H(X) ≤ L(C) / m ≤ Η(X) + 2 / m 16
Návrh pravděpodobnostního modelu p(x1 x2... xm) = p(x1) p(x2)... p(xm)
✎ Problém: Jak odhadnout p(xi | x1 x2... xi-1)? ☞Řešení: Předpoklad p(xi | x1 x2 ... xi-1) = p(xi | xi-k xi-k+1... xi-1) Model s konečným kontextem řádu k 17
Experimentální určení entropie anglického textu Anglický text - slovo nad abecedou A = {26 písmen bez rozlišení velikosti} ∪ {mezera} C.Shannon (1951) # pokusů 1
2
3
4
5
>5
četnost
8%
3%
2%
2%
5%
79%
T.M.Cover, R.C.King (1978) Výsledek: 1.3b/symbol Pro srovnání • •
anglický text bible (bible.txt, cca 4MB) PPMZ (C. Bloom): 1.47b/znak 18
