Informatika | Információelmélet » Éltető Tamás - Univerzális forráskódolás

Univerz alis forr ask odol as E ltet}o Tamas November 2, 1998 Legyen  egy vges . Ekkor az elemeib}ol kepzett hosszu szavakat jeloljuk gy: 1 2 1 , itt 1 az hosszu szavak halmaza. C el: Kodoljuk a stacionarius, ergodikus forrasbol szarmazo 1 sorozatot n egy valoszn}useggel barmely eloszlasra, ahol ugy, hogy ( 1 ) ! abc x n abc n n n n n P L x x HP n P 1 ( = lim !1 HP Itt ( 1 ) jeoli az n L x De nco 1 n n H X n 0 1 ) = nlim !1 H (X1 jX,n ): kodjanak hosszat. n 1 x HP X = 2 ( ) log ( ) P x P x x Ha  = f0; 1g, es ( )=  P x Ekkor specialisan ( )= h p p; 1,  ha x p; =0 =1 ha x :  = , log + (1 , ) log (1 , ) HP p p p p : 1 Statikus szotar tpusu kodolas 1.1 Adaptv kodolas A forras eloszlasat nem ismerjuk, es csak azt feltetelezzuk, hogy stacionarius, ergodikus. Tekintsuk az 1 sorozatot, es vagjuk fel egymassal szomszedos as blokkokra! Jelolje ^ (
j 1 ) ezen -as

blokkok 1 -ben meg gyelhet}o relatv gyakorisagait, azaz tapasztalati eloszlasukat, melyet tpus nak nevezunk. n x Pk Tetel 1 Az n 1 x k n x n k x sorozatban el}ofordulo tpusok szama  1 jjk,1 (jj,1) . n Az uzenet alljon harom reszb}ol:  azonostjuk a tpust : jj ,1 (jj , 1) log bit  Kodoljuk most a -as blokkokat a ^ (
j 1 ) eloszlashoz tartozo ShannonFano (vagy peldaul Hu mann) koddal. Ekkor a kod hossza: k n k Pk  x n ( ^ (
j 1 ))  n H Pk k x n nHP ; ha eleg nagy  tudatni kell, hogy a blokkmeret , azaz kodolni kell a szamot: log bit lasd kovetkez}o tetel k k k n Tetel 2 (Elias) Letezik olyan : N ! f0 1g pre x kod, hogy ( ) = (log ) = C log + (log log ) n O O Tehat az (log ) + n ; L n O n n sorozat kodjanak hossza: ( 1 )  jj ,1 (jj , 1) log + . Ha mret}u blokkokra bontottuk fel az uzenetet n 1 x nHP Lk x k n n k 1.2 Adaptv Hu man kod Itt feltesszuk, hogy a forrasunk

emlekezetnelkuli. Az el}oz}o kodolassal szemben ez bet}unkenti kodolas. Az 1 -b}ol megbecsuljuk a forras eloszlasat, megpedig a tapasztalati eloszlassal: ^ n1 . Ezek utan az +1 kodolasahoz a ^ n1 eloszlashoz rendelt Hu man-kodot hasznaljuk. n x Px xn Px 1.3 Tpusosztalyon beluli kodolas Ennel a kodolasnal is feltesszuk, hogy a forrasunk emlekezetnelkuli, azaz a sorozatunk elemei fuggetlen, azonos eloszlasu veletlen bet}uk. Az egyszer}useg kedveert most  = f0 1g. Tekintsuk a kovetkez}o pre x kodot: Az 1 2 1 sorozatnak azonostjuk a tapasztalati eloszlasat, azaz a tpusat, ez dlog ( , 1)e bittel megtehet}o (ui. ,, 1 darab
tpus van). Ezutan a megfelel}o tpuson beluli sorszamat kodoljuk dlog 0 e bittel. A kovetkez}okben mind a tpusok szamara vonatkozo alltast, mind az azonos tpusu sorozatok szamara vonatkozo alltast altalanosabban, jj  2 esetben latjuk be. ; k x k k k k N De nco 2

Jelolje P a hosszu sorozatok lehetseges tpusai halmazat! Jelolje tovabba 2 P eseten = f 1 2 1 : ^ n1 = g k P k k k k TP k x Lemma 1 jP j = k  k Px P  + ,1 ,1 r r ha jj = r. 2 ; : Na o . Nb o o o o o Nz o o o o  egesz, ahol P 2 = . , 1 + darab helyre kell , 1 darab vonast betenni. Ebb}ol + 1 jelkepezi a karakter kozott a bet}ucsoportok hatarait, es tovabbi , 2 segtsegevel kodoljuk Bizonytas: 0  k Na k r Na a k r k k r az esetleg nem szerepl}o karakterek miatt keletkezett tobbszoros hatarokat. Lemma 2 1 2 jP j j j2 P kH k Bizonytas: Legyen k Q ( 1) = k x Y veletlen minta egy k 1 x k Y ( )= Q xi =1 2 i Itt ^ k1 ( ) = Px a a. N k () Q a Ekkor ( ) = j j2 k Q k P 1  ( ) = j j2 k k P TP k TP amib}ol kovetkezik, hogy =2 k P a2 P^xk1 (a) log Q(a) : P a2 P (a) log Q(a) : P a2Xi P (a) log P (a) j j2 k = j j2, k P; kH TP P: kH TP X k P k TP

= ! 1 = (1 ) = a N eloszlasbol: Q a Q TP Legyen most P: kH TP k ( )  jP j max ( ) = jP j ( ) 2Pk k P TQ 2Pk Q ha tudjuk, hogy a maximum = Q k k P TQ Q k P k TP : eseten eretik el. Ekkor: P 1  jP jj j2, k k p; kH TP azaz belattuk a Lemmat. Lemma 3 ( ) ( ) k k P TQ P TP : Bizonytas: P =f Na k ( ) = j j2 k P TQ k TQ : 2 g a Q P a2 Na0 log P (a) =f k : 2 g a : Y = Q ! 0! () 2 2 k a 3 0 Na Na P a a a0 : N Itt szamossaga egyszer}u kombinatorikus megfontolassal kaphato: elem ismetleses permutacioja, ahol minden egyes 2  bet}ub}ol 0 darab fordul el}o. Az alltas belatasahoz az kell, hogy: Y Y 0 Q ! 0! ( ) aQ ! ! () a 2 2  2 2 k TQ k a k a Y 0 N 2 a  Na a Xi Y Tehat az kell, hogy: a ,Na0 () = N Y 2 a Xi ! , ! Ezt harom esetre bontva nezzuk meg: 1. = , ekkor igaz az egyenl}otlenseg, k k l k k l ; a a ,Na0 0 N ,Na k a Na N P a Na a a P a 2 a k

N P a Na Na N = Y 2 Na a ,Na0 : N a : l 2. k > l , ekkor 3. k < l , ekkor ! l! k! l! k z k , }| darab { ( + 1)  , , tehat szinten kesz, l = ( , 1) k k ::: l k = ( , 1) 1 ( + 1)  | {z } l l k ::: k k l 1 l,k . l,k darab Ezzel teljesen bebizonytottuk a Lemmat. Tetel 3 A lert kodra 1 lim !1 k k Bizonytas: E , k A bet}unkenti atlagos kodhosz: 0 1 ( )  1 @d ( + 1)e + 1 k k L x log k k
( 1) = L x HP = () h p : X  log k k x1 21 X  dlog( + 1)e + 1 log 2 k k 0 (xk1 )  N (xk )  ! 0 1 k ( P x N kh k  k k X  0( 1 )  d log( + 1) e + 1 + ( 1) = = x k k = dlog( + 1)e + 1 + k k Eh  k xk 1 21 0 (X1k ) N k h k x k  dlog(  k = log( + 1) + 1 + ( ) ! k k N h p 4 HP ; k P x + 1)e + ha h k ( 1) + 1 = P x k1 2k1 1 1 )A  k k  h 0 (X1k ) EN !1 k :  = Itt nehezseget jelent, hogy meg kell mondani az 1 jelsorozatrol, hogy hanyadik a tpusosztalyaban

peldaul lexikogra kusan. Ez az enumeratv kodolas Az 1 sorszama a kovetkez}okeppen rhato fel: k x x X k j =1 ( 1 xj N x ; : : : ; xj k ,1 ; 0); ahol ( 1 ,1 ) azon sorozatok szama a tpusosztalyon belul, amelyeknek ( 1 ,1 ) a pre xe. Ha peldaul az 1 -edik bitje 1-es, akkor az osszes olyan sorozat kissebb nala, amelynek els}o , 1 bitje ugyanaz, es a -edik bitje 0. Legyen 0 az ( 1 ,1 )-beli nullak szama. Ekkor N x ; : : : ; xj k x ; : : : ; xj x j j N ;j x ; : : : ; xj ( 1 N x ; : : : ; xj ,1 ) = j  , 0, k 0 : ,
bittel valo binaris felrasa. N A sorozat kodja pedig a kapott sorszam log  j N ;j k 0 N 2 Lempel-Ziv tpusu kodok A sorozatot szegmentaljuk es a kijelolt darabokat, a szavakat, kodoljuk. 2.1 Egyszer}u Lempel-Ziv (LZ78) Kovetkez}o szo = a legrovidebb uj szo 0 1 10 100 01 1001 10 Az uj szo egy regebbi szo folytatasa egy karakterrel. A kodolas ugy tortenik, hogy megadjuk a regebbi szo

helyet, es az uj karaktert. Az eredeti leras megtalalhato: [1] Tegyuk fel, hogy = ( 1 ) blokk keletkezett! Ekkor az osszes kodhossz: + dlog jje + dlog e+ utolso szo. A bet}unkenti atlagos hossz lenyegeben log ; c c X c ; ; ; ; n c c n c n n Tetel 4 (Ziv) n : ( 1 ) log = lim !1 ergordikus forrasbol szarmazik. c X 1 valoszn}useggel, ha X1 ; n n n n HP 2.2 Szabad Lempel-Ziv Ket fajta van, a masodik lerasat lasd [2]. Kovetkez}o szo = a legrovidebb blokk, amelyik nem kezd}odott el valahol a multban. 0 1 10 10100 01001 0 Kovetkez}o szo = a leghosszabb blokk, ami vagy egy bet}u, vagy megegyezik egy, valahol a multban elkezd}odott, jelsorozattal. 0 1 1 01 010 00 100 10 ; ; ; ; ; ; ; ; ; 5 ; ; ; 2.3 Lempel-Ziv-Welch Kovetkez}o szo = a leghosszabb szo, ami vagy egy bet}u, vagy egy korabbi szo, amelyet egy bet}u kovet. Az egyszer}u Lempel-Ziv kodolassal szemben itt nem a szo utolso bet}ujet kovet}oen

kezdjuk el keresni a kovetkez}o szot, hanem a szotarban mar szerepl}o resz utolso bet}ujet - azaz az utolso el}otti bet}ut kovet}oen. Leirasa pl lasd [3] 0 1 1 0 01 00 10 010 11 10 ; ; ; ; ; ; ; ; ; A modszereknek az a hatranya, hogy vegtelen nagy memoriat felteteleznek. Veges memoriat igenyel az egyszer}u Lempel-Ziv es a Lempel-Ziv-Welch, ha a szotar b}ovteset mondjuk bet}u utan el}orol kezdjuk. Ez azt jelentheti peldaul, hogy igazabol hosszu jelsorozatokat kodolunk. Egy masik veges memoriat feltetelez}o modszer a csuszoablakos szabad LempelZiv kodolas, ahol az a szabaly, hogy a kovetkez}o szo egyetlen bet}u, vagy a leghosszab blokk, amely megegyezik egy olyan multban elkezd}odott jelsorozattal, amely nem kezd}odott el tobb, mint karakterrel korabban. N N N 2.4 O sszefoglalas Az univerzalis forraskodolasnal olyan modszereket hasznalunk, amelyek nem feltetelezik a forras valoszn}usegeloszlasanak az

ismeretet, megis aszimptotikusan az elerhet}o legjobb tomortest adjak. A statikus szotar tpusu kodolas adaptv fajtaja eseten ismernunk kell a teljes kodolando szoveget, de csak annyit feltetelezunk a forrarsrol, hogy stacionarius es ergordikus. Ez a kodolas nem alkalmazhato valos id}oben. A tpusosztalyon beluli kodolasnal szinten szuksegunk van a teljes uzentre, raadasul itt azt is feltetelezzuk, hogy a forrasunk emlekezetnelkuli. Az adaptv Hu man kod mar valos id}oben m}ukodik, de ez a kodolas varhatoan szinten csak emlekezetnelkuli forrasokra optimalis (aszimptotikusan). A Lempel-Ziv tpusu kodok tetsz}oleges stacionarius es ergodikus forras uzenetet aszimptotikusan optimalisan kodoljak valos id}oben. Hatranyuk az, hogy vegtelen nagy memoriat felteteleznek mind az adonal, mind a vev}onel. Azonban tetsz}olegesen kozel tudunk kerulni az optimumhoz, ha elegend}oen nagy memoriaval

rendelkezunk. Referencia [1] J. Ziv and A Lempel, Compression of individual sequences via variable rate coding" IEEE Trans. Inform Th, IT-24 (1978), 530-536 [2] J. Ziv and A Lempel, A universal algorithm for sequential data compression" IEEE Trans Inform Th, IT-23 (1978), 337-343 [3] T. A Welch, A technique for high-performance data compression" IEEE Computer, 17 (1984), 8-19. [4] Paul C. Shields Performance of LZ algorithms on individual sequences" 6