Posted By: JayDee (expect the unexpected) on 'CZprogram'
Title:     Re: Co prosim?
Date:      Thu Jan 25 00:37:49 2007

> > The resulting byte stream from that is then compressed using Arithmetic 
> > compression, which, unlike Huffman compression, can use fractional bits
> per 
> > symbol.
> > 
> > Pokud tomu spravne rozumim, tak tvrdi, ze dokazou zakodovat symbol na 
> > informaci mensi nez bit... to ve mne nejak nebudi duveru. Nebo mi to nekdo
> > dokaze vysvetlit nejak rozumne?
> > 
> > Mam to z http://lags.leetcode.net/codec.html
> 
> To ale imho neznamena, ze muzes mit 1 symbol na 0.3 bitu, ale treba 2.3. 
> Nechce se mi to cmarat na papir, abych si to overil, ale z popisu fungovani
> tady:
> http://en.wikipedia.org/wiki/Data_compression/Arithmetic_coding
> vyplyva, ze by to mohla byt pravda (ten algoritmus totiz ve vysledku neudela
> nejaky slovnik symbolu, pomoci nehoz zakoduje vstup, ale napise jedno cislo
> reprezentujici cely vstup. 

Ano, zatimco huffmannovo kodovani koduje vstupni symboly do vystupnich 
sekvenci s celociselnym poctem bitu, aritmeticke je obecnejsi a muze kodovat 
do "sekvenci s necelociselnou delkou" jako dvaapul bitu, triactvrt.. Ovsem 
pouze zprumerovane pres vic symbolu, ne ze by to takovou necelou sekvenci 
skutecne pouzilo. 
(ano, da se zkonstruovat i priklad, kdy to 10 vstupnich symbolu 
narve do jednoho bitu, ale spis asi mysleli ty zlomky vetsi nez jedna) 

Vyklad metody:

Na pocatku se vezme cely interval 0 az 1.
Aktualni interval se rozdeli na podintervaly podle ocekavanych 
pravdepodobnosti dalsiho symbolu (ty doda na zaklade predchozich dat 
'pravdepodobnostni model', ktery je dodan zvnejsku a musi byt stejny v koderu 
i dekoderu) - cim vetsi pravdepodobnost, tim sirsi intervalek.
Podle vstupniho symbolu se zvoli prislusny podinterval, udela se z nej novy 
aktualni interval, prejde se na dalsi vstupni symbol a cela vec se opakuje. 

Ted mame cela data zakodovana do jednoho maleho intervalu nekde mezi 0 a 1.
K jeho reprezentaci nam bude stacit jedno konkretni cislo, ktere v nem lezi. 
Zvolime si to, ktere ma ve dvojkove soustave nejkratsi zapis.
(tohle by jeste nestacilo, je jeste potreba bud mit ukoncovaci 
symbol nebo poznamenat delku vstupu, abychom pri dekodovani vedeli, kdy 
prestat)
Cim lepe pravdepodobnostni model odhadl data, tim sirsi bude vysledny 
interval a tim uspornejsi bude kodovani. 

Dekodovani si domyslete, mame jedno cislo a v kazdem kroku se to rozdeli na 
intervaly stejnym zpusobem jako u kodovani a kam to cislo padne, ten symbol to 
je. Dekoder musi uvazovat identickou sekvenci vnorenych podintervalu jako 
koder pri kodovani.

Huffmannovo kodovani se da povazovat za specialni pripad aritmetickeho:
pravdepodobnostni model ma v tomto pripade pravdepodobnosti symbolu konstantni 
a rovne ruznym mocninam 1/2. 

Sila aritmetickeho kodovani je v tom, ze pokud pravdepodobnostni model 
obsahuje skutecne maximum informaci, co se o tech datech predem da rict, pak 
dostaneme jejich nejuspornejsi mozne vyjadreni.
(vymakany model na cesky jazyk by mohl treba hledat rozepsane slovo ve 
slovniku a nabizet podle toho pravdepodobnosti hlasek, drobna nevyhoda je v 
tom, ze by ten samy slovnik pak musel mit k dispozici i dekoder..) 

> 
> > -
> > Clovek je nejpomalejsi zname zarizeni typu I/O.
> >                                                                  Quasimodo
> 
>     .      .   . # # recnamorueN | Neuromancer # # .   .      .