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 ( j 0 ) = lim 1 , 1 !1 !1 HP n n H X n n H X X n : Itt ( 1 ) jeoli az 1 kodjanak hosszat. n n L x x De nco 1 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 k n x n k x Tetel 1 Az 1 sorozatban el}ofordulo tpusok szama  n x 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 ( 1 )  jj ,1 (jj , 1) log + . Ha mret}u blokkokra bontottuk fel az uzenetet 1 sorozat kodjanak hossza: n 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 Px  + , 1 P k r r ha jj = r. 2 ,1 ; : 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 P  jT k j  2kHP : kH jP j P k Bizonytas: Legyen 1 veletlen minta egy eloszlasbol: k x k Q ( 1) = k x Y k Q Y ( )= Q xi =1 2 i Itt ^ k1 ( ) = Px a ( ) a =2 P a2 P^xk1 (a) log Q(a) : a a . Ekkor N k ( ) = j j2 k k Q TP Legyen most k N Q a Q = ! P 1  ( ) = j j2 k k P TP k TP amib}ol kovetkezik, hogy k P P a2 P (a) log Q(a) : P a2Xi P (a) log P

(a) = jTPk j2,kHP ; j j2 P k kH TP X 1 = (1 ) = k TP ( )  jP j max ( ) = jP j ( ) 2P k 2Pk Q ha tudjuk, hogy a maximum : P TQ = Q k k P TQ k 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 : 2 g a Q =f 0 Na k : 2 g a : Y P 0 0 ( ) = j j2 a2 a log ( ) = Q ! 0 ! () a 2 2 k P TQ k TQ N k P a a 3 Na P a a 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 Na 2 a a Xi Tehat az kell, hogy: Y a ,Na0 = P (a) 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 N 2 a k N P a

Na Na N Y 2 Na a ,Na0 : N a : l k,l darab ! 2. k > l, ekkor l! = k(k , 1) : : : (l + 1)  kk,l , tehat szinten kesz, 1 . 3. k < l, ekkor kl!! = l(l , 1) : 1: : (k + 1)  kl,k k z }| { | l,k darab {z } Ezzel teljesen bebizonytottuk a Lemmat. Tetel 3 A lert kodra 1 lim !1 k k Bizonytas: E , ( )
= L x k 1 A bet}unkenti atlagos kodhosz: 0 HP = () h p :   1 ( )  1 @d ( + 1)e + X log 1 k k L x log k k k k x1 21 X  dlog( + 1)e + 1 log 2 k k 0 (xk1 ) P x N  N (xk )  ! kh k 0 1 k 1 ( 1 )A   k ( 1) + 1 = k P x k1 2k1 X  0( 1 )  d log( + 1) e + 1 + ( )= = x k k = dlog( + 1)e + 1 + k k Eh k xk 1 21  0( N 1) X k k h k x k P x k 1 h k h p 4 HP ; ha h k k  dlog( + 1)e   + = log( + 1) + 1 + ( ) ! k k N k !1 0 (X1k ) EN : 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, 0 k j A sorozat kodja pedig a kapott sorszam log : ,
bittel valo binaris felrasa. N 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 (LZ'78) 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 c ; ; ; ; ; n c n c n n Tetel 4 (Ziv) : ( 1 ) log = lim !1 1 valoszn}useggel, ha 1 ergordikus forrasbol szarmazik. c X n X n n n HP n 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