Komprese dat. Jan Outrata KATEDRA INFORMATIKY UNIVERZITA PALACKÉHO V OLOMOUCI. přednášky

Komprese dat Jan Outrata

KATEDRA INFORMATIKY UNIVERZITA PALACKÉHO V OLOMOUCI

přednášky

Statistické metody

Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat

Olomouc, únor–březen 2016

1 / 23

Tunstallův kód = zdrojová slova proměnné délky kódována na kódová slova pevné délky k ≥ dlogm ne kódových symbolů = blokový kód, ∼ variable-to-fixed code (n je velikost zdrojové abecedy, m je velikost kódové abecedy) chyby v kódových slovech se při dekódování nešíří – robustnost požadavky: každou (neprázdnou) posloupnost zdrojových symbolů musí být možné vyjádřit jako (případně prefix) zřetězení právě jedné posloupnosti zdrojových slov kódovaných na kódové slovo – jednoznačná kódovatelnost 2 průměrná délka zdrojových slov kódovaných na kódové slovo je maximální = optimální kód → delší zdrojová slova mají větší pravděpodobnost výskytu 3 je použito maximum kódových slov, ideálně všech mk – optimalita 1

prefixový – pro zdrojová slova kódovaná na kódové slovo, jednoznačná kódovatelnost průměrná délka kódu: Pt i=1

k , P (wi )l(wi )

t počet zdrojových slov wi délky l(wi ) s

pravděpodobností výskytu P (wi ) pouze statický a semi-adaptivní model Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat


2 / 23

Tunstallův kód B. P. Tunstall Input : číslo k Uses : zdrojová abeceda A, n = |A|, pravděpodobnosti P (A+ ) výskytu slova z A, velikost m kódové abecedy Output: C(U ) T ← A; i ← 0; while n + (i + 1)(n − 1) ≤ mk do x ← w ∈ T, P (w) ≥ P (w0 ), w0 ∈ T ; T ← (T \ {x}) ∪ {xy | y ∈ A}; i ← i + 1; C(T ) ← {kódová slova délky k} libovolně; 5 7 PRIKLAD: k = 4, A = {a, b, r, u, o}, p(a) = 20 , p(b) = 20 , p(r) = 1 p(o) = 20 , m = 2, vstup barbaraabarboraubaru, redundance


Komprese dat

5 20 ,

p(u) =

2 20 ,


3 / 23

Shannon-Fanovo kódování C. E. Shannon, R. M. Fano první pokus o optimální binární prefixový kód – využití distribuční funkce/kumulované pravděpodobnosti (cumulative distribution function) zdroje Input : čísla a, b Uses : zdrojová abeceda A = {a1 , . . . , an }, n ≥ 2, pravděpodobnosti {p1 , . . . , pn }, pi ≥ pj pro i < j, výskytu ai Output : kód C(A) if a + 1 = b then C(aa ) ← 0; C(ab ) ← I; najdi j takové, že |

Pj

pi −

i=a

Pb i=j+1

pi | je minimální;

C(A) ← zavolej se rekurzivně s a, j a s j + 1, b; C(ai ) ← 0C(ai ) pro i = a, . . . , j; C(ai ) ← IC(ai ) pro i = j + 1, . . . , b; Run with: 1, n 5 20 ,

7 PRIKLAD: A = {a, b, r, u, o}, p(a) = 20 , p(b) = vstup barbaraabarboraubaru, redundance

optimální při | minimální

P

k

pk =


Pj

i=a pi

−

Pb

i=j+1 pi

=

Komprese dat

p(r) = l pl |,

P

5 20 ,

p(u) =

2 20 ,

p(o) =

1 20 ,

k, l ∈ {a, . . . , b}, {k} ∩ {l} = ∅, Olomouc, únor–březen 2016

4 / 23

Huffmanovo kódování David A. Huffman: A method for the construction of minimum-redundancy codes. Proceedings of the I.R.E., pp. 1098–1102, 1952. optimální prefixové, vyplývá z vlastností optimálního prefixového kódu (viz Věta dříve) a následujícího Lemma


Komprese dat


5 / 23

Huffmanovo kódování David A. Huffman: A method for the construction of minimum-redundancy codes. Proceedings of the I.R.E., pp. 1098–1102, 1952. optimální prefixové, vyplývá z vlastností optimálního prefixového kódu (viz Věta dříve) a následujícího Lemma

Lemma Nechť C 0 : A0 7→ B + , kde A0 = {a01 , . . . , a0n0 }, n0 ≥ m ≥ 2, a0i = ai ∈ A, i < n0 , P pravděpodobnosti výskytu symbolů a0i jsou p0i = pi , i < n0 , p0n0 = nj=n−m0 +1 pj , A = {a1 , . . . , an }, n = n0 + m0 − 1, s pravděpodobnostmi výskytu pi symbolů ai , kde pn−m0 +1 , . . . , pn jsou nejmenší, m0 ∈ {2, 3, . . . , m}, m0 ≡ n (mod (m − 1)), B = {b1 , . . . , bm }, je optimální prefixový kód ze zdrojové abecedy A0 do kódové abecedy B. Pak kód C : A 7→ B + , C(ai ) = C 0 (a0i ), i < n0 , C(an−m0 +j ) = C 0 (a0n0 )bj , j ≤ m0 , ze zdrojové abecedy A do kódové abecedy B je také optimální.


Komprese dat


5 / 23

Huffmanovo kódování Statický a semi-adaptivní model : abeceda A0 = {a01 , . . . , a0n0 }, pravděpodobnosti {p01 , . . . , p0n0 } výskytu a0i : zdrojová abeceda A = {a1 , . . . , an }, pravděpodobnosti {p1 , . . . , pn } výskytu ai , kódová abeceda B = {b1 , . . . , bm } Output : kód C(A0 ) setřiď a0i a p0i tak, že p0i ≥ p0j pro i < j; if n0 ≤ m then C(a0i ) ← bi pro i = 1, . . . , n0 ; else if n0 = n then m0 ← (n − 2) mod (m − 1) + 2; else m0 = m Pn0 C(A0 ) ← zavolej se rekurzivně s A0 \ {a0n0 −m0 +2 , . . . , an0 }, {p01 , . . . , p0n0 −m0 , i=n0 −m0 +1 p0i }; C(a0n0 −m0 +i ) ← C(a0n0 −m0 +1 )bi pro i = 1, . . . , m0 ; Run with: A = {a1 , . . . , an }, {p1 , . . . , pn } Input Uses

5 5 7 , p(b) = 20 , p(r) = 20 , p(u) = PRIKLAD: A = {a, b, r, u, o}, p(a) = 20 m = 2, vstup barbaraabarboraubaru, m = 3, vstup ??, redundance Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat

2 20 ,

p(o) =

1 20 ,


6 / 23

Huffmanovo kódování Proč m0 a ne m? Protože při tomto počtu nejdelších kódových slov bude u všech kratších kódových slov a prefixů využito všech m symbolů kódové abecedy a kód má být optimální prefixový. Huffmanův strom TH (A) = hVH (A), EH (VH (A))i = reprezentace Huffmanova kódu C(A) formou m-árního stromu: listové uzly vl (ai ) ∈ VH (A) pro symboly ai ∈ A, i = 1, . . . , n vnitřní uzly v(a0n0 ) ∈ VH (A) pro všechny a0n0 (ve všech rekurzivních voláních) + kořenový uzel vr ∈ VH (A) hrany hv(a0n0 ), v(a0n0 −m0 +i )ibi ∈ EH (VH (A)) a hvr , v(a0i )ibi ∈ EH (VH (A)) označené bi ∈ B z uzlu pro a0n0 následujícího rekurzivního volání do uzlů pro a0n0 −m0 +i , i = 1, . . . , m0 při n0 > m a z kořenového uzlu do uzlů pro a0i , i = 1, . . . , n0 při n0 ≤ m C(a) = zřetězení b ∈ B označujících hrany na cestě stromem z vr do vl (a) PRIKLAD Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat


7 / 23

Huffmanovo kódování minimální rozdíly v délkách kódových slov (pro jejich minimální bufferování při pevné rychlosti přenosu/ukládání): třídění a0i a p0i tak, že původní a0n0 bude po zatřídění a0i , i < j pro všechna j, pro která p0j = p0i m = 2 a pi > nj=i+2 pj , pi ≥ pj pro i < j (speciálně pi = 2−i , i = 1, . . . , n − 1 a pn = 2−(n−1) ) → unární číselný kód i − 1 pro ai , i = 1, . . . , n − 1 a n I pro an P

m = 2 a p1 < pn−1 + pn , pi ≥ pj pro i < j (speciálně pi = n1 ) → blokový kód délky k = blog2 nc pro a1 , . . . , a2k a délky k + 1 pro a2k +1 , . . . , an PRIKLADY


Komprese dat


8 / 23

Huffmanovo kódování Adaptivní model – binární kód triviálně: znovuvytváření kódu pro každý další symbol na vstupu – výpočetně náročné Faller, Gallager, Knuth, Vitter vlastnost Huffmanova stromu (tzv. sibling property): p0n0 ≤ . . . ≤ p0n0 −m0 +1 ≤ p0n0 ≤ . . . ≤ p0n0 −m0 +1 následujícího rekurzivního volání – musí stále platit → v následujících algoritmech zajištěno pomocí (aktuálního) počtu n(x) výskytů symbolu x a čísla i(v(x)), v(x) ∈ VH (A) speciální (escape) symbol e značící neexistující/první výskyt symbolu TH (A) ← h{vl (e)}, ∅i, C(e) ← prázdný řetězec; n(e) ← 0; i(vl (e)) ← 1; while načti ze vstupu symbol a ∈ A do if vl (a) 6∈ VH (A) then zapiš na výstup C(e) a kód a; else zapiš na výstup C(a); zavolej následující algoritmus; Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat


9 / 23

Huffmanovo kódování Adaptivní model – binární kód if vl (a) 6∈ VH (A) then VH (A) ← VH (A) ∪ {vl (a), v(x)}; n(a) ← n(x) ← 1; i(v(x)) ← i(vl (e)); i(vl (a)) ← i(v(x)) + 1; i(vl (e)) ← i(vl (a)) + 1; EH (VH (A)) ← (EH (VH (A)) \ {hu, vl (e)ib }) ∪ {hv(x), vl (e)iI , hv(x), vl (a)i0 , hu, v(x)ib }; else v(x) ← vl (a); while v(x) 6= vr do if hv(x), vl (e)i 6∈ EH (VH (A)) then najdi v(y) takové, že i(v(y)) < i(v(z)), ∀v(z) ∈ VH (A), n(y) = n(z); if v(y) 6= v(x) ∧ hv(y), v(x)i 6∈ EH (VH (A)) then v ← v(x); v(x) ← v(y); v(y) ← v; i ← i(v(x)); i(v(x)) ← i(v(y)); i(v(y)) ← i; n(x) ← n(x) + 1; v(x) ← u, hu, v(x)i ∈ EH (VH (A)); n(x) ← n(x) + 1;

PRIKLAD Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat


10 / 23

Huffmanovo kódování Adaptivní model – binární kód TH (A) ← h{vl (e)}, ∅i; n(e) ← 0; i(vl (e)) ← 1; while není konec vstupu do v ← vr ; while v 6= vl (a) do načti ze vstupu symbol b ∈ B; v ← u, hv, uib ∈ EH (VH (A)); if a = e then načti ze vstupu kód symbolu a ∈ A; dekóduj kód a a zapiš na výstup a; else zapiš na výstup symbol a ∈ A; zavolej předchozí algoritmus; PRIKLAD Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat


11 / 23

Huffmanovo kódování Aplikace často v návaznosti na jiné metody, např. na diferenční kódování (obraz, zvuk)


Komprese dat


12 / 23

Aritmetické kódování průměrná délka optimálního prefixového kódu, např. Huffmanova, je minimálně rovna entropii zdroje a nejvýše o 1 větší než entropie (Shannon noisless coding theorem, viz Věta dříve) – platí těsnější, nejvýše o nejvyšší pravděpodobnost pmax ≥ 0.5 zdrojových symbolů nebo o pmax + 0.086, pmax < 0.5 změna zdrojové abecedy na k-tice (nezávislých) symbolů z původní abecedy A pro přiblížení se entropii ale zvyšuje velikost abecedy, a tím i Huffmanova stromu, na |A|k , např. pro p1 = 0.95, p2 = 0.03, p3 = 0.02 je entropie přibližně 0.335 b/symbol, průměrná délka Huffmanova kódu 1.05 b/symbol, kódu pro 9 dvojic symbolů přibližně 0.611 b/symbol a kódu pro ? ?tic symbolů přibližně ? b/symbol! ⇒ výhodnější kódovat zdrojová slova než samostatné symboly – ale nevytvářet kód pro všechna slova dané délky, např. Huffmanův! → kód pouze pro zdrojová slova na vstupu vhodné pro malé zdrojové abecedy, např. binární, s velkými rozdíly v pravděpodobnostech symbolů = kódování zdrojových slov do čísel z podintervalů [0, 1) kódovaných do binárního kódu Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat


13 / 23

Aritmetické kódování Pasco, Rissanen, 1976, Rissanen, Langdon, 1979 využití distribuční funkce/kumulované pravděpodobnosti (cumulative distribution P function) FX (i) = ik=1 P (X = k), P (X = k) = P (ak ) = pk zdroje (nezávisle se stejným pravděpodobnostním rozložením se vyskytujících) symbolů z abecedy A = {a1 , a2 , . . . , an } jako náhodných proměnných X(ai ) = i, FX (0) = 0 lp ← 0; up ← 1; while načti ze vstupu symbol ai ∈ A do l ← lp + (up − lp )FX (i − 1); u ← lp + (up − lp )FX (i); lp ← l; up ← u; // přeškálování [l, u) zapiš na výstup C = binární reprezentace jakéhokoliv čísla z [l, u) s minimem bitů; PRIKLAD


Komprese dat


14 / 23

Aritmetické kódování C(A+ ) je prefixový binární kód ze zdrojových slov nad abecedou A, průměrná délka pro slova délky k je H(Ak ) ≤ ¯l(C(Ak )) < H(Ak ) + 1 ⇒ průměrná délka na symbol z A je H(A) ≤ ¯l < H(A) + k1 pro dekódování je nutné znát délku L kódovaného zdrojového slova → uložit spolu s komprimovanými daty nebo speciální zdrojový symbol značící konec vstupu lp ← 0; up ← 1; j ← 0; načti ze vstupu binární reprezentaci čísla x ∈ [0, 1); while j < L do x−l najdi i ∈ {1, . . . , n} takové, že FX (i − 1) ≤ up −lpp < FX (i); zapiš na výstup symbol ai ∈ A; j ← j + 1; if j < L then l ← lp + (up − lp )FX (i − 1); u ← lp + (up − lp )FX (i); lp ← l; up ← u; // přeškálování [l, u)


Komprese dat


15 / 23

Aritmetické kódování u kódování i dekódování žádoucí průběžný výstup během čtení vstupu, ne až po načtení celého vstupu → kód čísla z [l, u) průběžně [l, u) se s délkou zdrojového slova zmenšuje, ale uložení necelých čísel je v praxi s omezenou přesností → omezení délky slova nebo přeškálování [l, u): u < 0.5: x ← 2x, x ∈ {l, u} l ≥ 0.5: x ← 2(x − 0.5), x ∈ {l, u} 3 l ≥ 0.25 ∧ u < 0.75: x ← 2(x − 0.25), x ∈ {l, u} 1 2

c-krát

c-krát

c-krát

c-krát

z }| { z }| { z }| { z }| { případy 3. . . 31 = 12. . . 2 a 3. . . 32 = 21. . . 1


Komprese dat


16 / 23

Aritmetické kódování c ← 0; // while ... while u < 0.5 ∨ l ≥ 0.5 ∨ (l ≥ 0.25 ∧ u < 0.75) do if l ≥ 0.25 ∧ u < 0.75 then // případ 3 c ← c + 1; d ← 0.25; else if u < 0.5 then // případ 1 b ← 0; d ← 0; else // případ 2 b ← I; d ← 0.5; zapiš na výstup b; while c > 0 do zapiš na výstup inverzi b; c ← c − 1; l ← 2(l − d); u ← 2(u − d); zapiš na výstup C = I;

PRIKLAD


Komprese dat


17 / 23

Aritmetické kódování načti ze vstupu d− log2 pmin e bitů binární reprezentace čísla x ∈ [0, 1), pmin nejnižší pravděpodobnost zdrojových symbolů; // while ... while u < 0.5 ∨ l ≥ 0.5 ∨ (l ≥ 0.25 ∧ u < 0.75) do if l ≥ 0.25 ∧ u < 0.75 then d ← 0.25; else if u < 0.5 then d ← 0; else d ← 0.5; l ← 2(l − d); u ← 2(u − d); načti ze vstupu další bit b anebo b ← 0; x ← 2(x − d) + b 2d− log12 pmin e ; PRIKLAD Jan Outrata (Univerzita Palackého v Olomouci)

Komprese dat


18 / 23

Aritmetické kódování Celočíselná implementace M 3M 1 zobrazení [0, 1) na [0, M − 1) (0.25 7→ M 4 , 0.5 7→ 2 , 0.75 7→ 4 ), M ≥ 4 pmin , M typicky 28 , 216 , 232 nebo 264 podle datového typu pro čísla z [0, M − 1) n(ak ) odhad FX (i) s frekvencemi/četnostmi f (ak ) = P|A| j=1

n(aj )

výskytu symbolu ak ∈ A

místo pravděpodobností P (ak ) l ← lp + b(up − lp + 1)FX (i − 1)c, u ← lp + b(up − lp + 1)FX (i)c − 1, u ← 2(u − d) + 1, x ← 2(x − d) + b – kvůli celočíselné aritmetice načti ze vstupu dlog2 M e bitů binární reprezentace čísla x ∈ [0, M − 1) při M = 2k pro nějaké k ≥ 2:

x−lp +1 up −lp +1 ,

u< M 2 → nejvýznamnější bit l i u je 0 l≥ M 2 → nejvýznamnější bit l i u je I 3M l≥ M 4 ∧ u < 4 → druhý nejvýznamnější bit l je I a u je 0 M 2x a 2(x − M 2 ) → bitový posun x doleva o 1 bit, 2(x − 4 ) → navíc inverze (nového) nejvýznamnějšího bitu


Komprese dat


19 / 23

Aritmetické kódování Adaptivní model n(ak ) průběžný odhad FX (i) s frekvencemi/četnostmi f (ak ) = P|A| j=1

n(aj )

výskytu symbolu

ak ∈ A místo pravděpodobností P (ak ) inicializace na známý odhad nebo počet n(a) = 1 výskytu každého symbolu a ∈ A inkrementace n(a) po (de)kódování symbolu a

uložení pmin spolu s komprimovanými daty, u celočíselné implementace nesmí pmin P|A| n(a ) 1 klesnout pod 4 M → v praxi n(aj ) ← 2 j pro n(aj ) > 1 při j=1 n(aj ) = M 4 Aplikace ve standardech komprese multimediálních dat (obraz, video, zvuk)


Komprese dat


20 / 23

Aritmetické kódování – QM kódování = modifikované adaptivní binární aritmetické kódování (Q kódování, skew kódování), tj. pro binární zdrojovou abecedu s adaptivním modelem A = u − l místo u: l ← lp + Ap FX (i − 1) a A ← Ap pi místo 2 symbolů A, a1 = 0 a a2 = I, a1 = více (MPS) a a2 = méně (LPS) pravděpodobný symbol s průběžně odhadovanými frekvencemi/četnostmi 1 − q a q výskytu l ← lp a A ← Ap (1 − q) pro MPS l ← lp + Ap (1 − q) a A ← Ap q pro LPS x−lp Ap < 1 − q pro MPS a ≥ 1 − q pro LPS

potlačení násobení (i pro nebinární zdrojové abecedy) – udržování hodnoty A v [0.75, 1.5) a zanedbání násobení Ap l ← lp a A ← Ap − q pro MPS l ← lp + Ap − q a A ← q pro LPS x − lp < 1 − q pro MPS a ≥ 1 − q pro LPS přeškálování l, A: A < 0.75: A ← 2A, l ← 2l pro l < 0.5 a l ← 2(l − 0.5) pro l ≥ 0.5


Komprese dat


21 / 23

Aritmetické kódování – QM kódování while A < 0.75 do if l < 0.5 then b ← 0; d ← 0; else b ← I; d ← 0.5; zapiš na výstup b; l ← 2(l − d); A ← 2A; zapiš na výstup C = I; načti ze vstupu d− log2 qe bitů binární reprezentace čísla x ∈ [0, 1); // while ... while A < 0.75 do if l < 0.5 then d ← 0; else d ← 0.5; l ← 2(l − d); A ← 2A; načti ze vstupu další bit b anebo b ← 0; 1 x ← 2(x − d) + b d− log ; 2 qe 2

PRIKLAD


Komprese dat


22 / 23

Aritmetické kódování – QM kódování inicializace q = 0.5 a aktualizace q podle tabulky hodnot při přeškálování, ne po (de)kódování každého symbolu při častějším výskytu LPS než MPS, q > A − q, prohození symbolů včetně aktuálních hodnot l a A, při přeškálování celočíselná implementace: zobrazení [0, 1.5) na [0, M − 1) (0.25 7→ 2M 41 0.75 7→ M 2 , 1 7→ 3 ), M ≥ 3 q , i pro hodnoty q

M 6 ,

0.5 7→

M 3 ,

použití ve standardu JPEG (JBIG) komprese obrazu


Komprese dat


23 / 23

Komprese dat. Jan Outrata KATEDRA INFORMATIKY UNIVERZITA PALACKÉHO V OLOMOUCI. přednášky

Recommend Documents