Czestina Aritmetické kódování TNT's HomePage Algoritmy komprese dat

Aritmetické kódování

Huffmanovo kódování dosahovalo optimálních výsledků, pokud četnosti jednotlivých znaků byly mocninami čísla 2. V ostatních případech by bylo optimální na zakódování jednoho znaku použít neceločíselný počet bitů (např. místo 4 bitů 3.25, jinde zase místo 2 bitů 2.1, celkově by však výsledný kód byl kratší). Situace se trochu zlepší použitím delšího kódového slova (k zaokrouhlování na celé bity bude docházet méně často), tím ale prudce rostou nároky na paměť. Rafinovaným dovedením tohoto vylepšení do krajnosti je právě aritmetické kódování, které kóduje celou zprávu jako jediné kódové slovo.

Aritmetické kódování reprezentuje zprávu jako podinterval intervalu <0,1). Na začátku uvažujeme celý tento interval. Jak se zpráva prodlužuje, zpřesňuje se i výsledný interval a jeho horní a dolní mez se k sobě přibližují. Čím je kódovaný znak pravděpodobnější, tím se interval zúží méně a k zápisu delšího (to znamená hrubšího) intervalu stačí méně bitů. Na konec stačí zapsat libovolné číslo z výsledného intervalu.

Komprese

  1. Zjištění pravděpodobností P(i) výskytu jednotlivých znaků ve zdrojovém souboru
  2. Spočtení příslušných kumulativních pravděpodobností K(0)=0, K(i)=K(i-1)+P(i-1) a rozdělení intervalu <0,1) na podintervaly I(i) odpovídající jednotlivým znakům (seřazeným podle abecedy), aby délky těchto intervalů vyjadřovaly pravděpodobnosti příslušných znaků: I(i) = <K(i), K(i+1))
  3. Uložení použitých pravděpodobností
  4. Vlastní komprese:
    začínáme s intervalem I=<0,1): označme jeho dolní mez D(I),
    horni H(I) a délku intervalu L(I)=H(I)-D(I)
    while (!eof) {
      read(i)
      I = <D(I)+K(i)*L(I), D(I)+K(i+1)*L(I))
    }
    write(D(I))
    

Dekomprese

  1. Rekonstrukce použitých pravděpodobností
  2. Vlastní dekomprese
    read(X) přečteme uložené reálné číslo
    while (není obnovena celá zpráva) {
      najdeme i, aby X bylo v [K(i), K(i+1))
      write(i)
      X=(X-K(i))/P(i)
    }
    

Softwarová realizace

Výše uvedený algoritmus je (vzhledem k práci s reálnými čísly) v programátorské praxi nepoužitelný, je tedy nutné upravit ho tak, aby pracoval pouze s čísly v pevné řádové čárce.

Nahrazení reálných pravděpodobností čísly v pevné řádové čárce žádné větší problémy nepřinese (je třeba pouze ošetřit, aby příliš malé pravděpodobnosti nepodtekly do nuly). Výsledný kód pak nemusí být optimální, ale pokud dekompresor použije stejnou reprezentaci, bude všechno OK. Při reprezentaci hranic aktuálního intervalu to však již tak jednoduché není: velmi brzy by totiž díky zaokrouhlovacím chybám horní a dolní mez intervalu splynuly a pak by zprávu již nikdo nemohl obnovit.

Při kompresi se horní a dolní mez neustále přibližují, to ovšem znamená, že na začátku (významnější část) desetinného zápisu obou mezí bude čím dál tím víc číslic shodných a dále již neměnných (až na patologické případy jako 0.29999... a 0.30000...). Tyto číslice tedy můžeme zapsat na výstup a upravit meze intervalu, aby nedocházelo ke ztrátě přesnosti.

Tím dostáváme tento upravený algoritmus pro kompresi pracující s čísly v pevné řádové čárce (čísla jsou v binárním desetinném zápisu):

začínáme s intervalem I=<.00000, .11111>:
označme jeho horní a dolní mez H(I) a D(I) 
a délku intervalu L(I)=H(I)-D(I)
while (!eof) {
  read(i)
  I = <D(I)+K(i)*L(I), D(I)+K(i+1)*L(I))
  switch {
    1. D=.0xxx; H=.0yyy -> D=.xxx0, H=.yyy1, write(0)
       dokud horní i dolní mez I začíná .0...
       zapíšeme společnou 0 na výstup,
       posuneme zbývající části mezí o jedno místo vlevo
       a na uvolněné místo v dolní mezi napíšeme 0 a v horní 1
       while (shift) { write(1); shift--; }
       Pokud shift!=0 zapíšeme také shift jednotek (společná 0)
       a vynulujeme shift
    2. D=.1xxx; H=.1yyy -> D=.xxx0, H=.yyy1, write(1)
       while (shift) { write(0); shift--; }
    3. D=.01xxx; H=.10yyy -> D=.0xxx0, H=.1yyy1, shift++
       "Patologický případ:" dokud dolní mez začíná .01... a horní .10...
       vypustíme 1 v dolní a 0 v horní mezi,
       zprava doplníme jako obvykle: .0...0 a .1...1
       a zvýšíme čítač: shift++
    Následující možnosti jsou uvedeny jen pro úplnost,
       v programu je není potřeba nijak ošetřovat
    4. D=.00xxx; H=.10yyy nebo D=.01xxx, H=.11yyy
       meze jsou od sebe vzdáleny alespoň 1/4 a ke ztrátě přesnosti nedojde
    5. D=.1xxx, H=.0yyy
       nemůže nastat (musí být D<H)
  }
  write(D(I))
}
Tato implementace bude tím přesnější (a tím i výsledný kód kratší), čím bude používaný interval mít více rozlišitelných bodů. Proto dolní mez doplňujeme nulami a horní jedničkami. Po ošetření případů 1, 2, 3 je délka aktuálního intervalu alespoň 1/4 a ke ztrátě přesnosti nedojde. Aby mohla proběhnout dekomprese, je nutné zapsat ještě několik bitů tak, aby zapsané číslo bylo v daných mezích. Na konci kódování (po expanzi intervalu) je jistě D < 1/2 < H. Zapíšeme-li tedy na výstup ještě jednu binární jedničku a za ní samé nuly, dekomprese proběhne správně (do zkomprimovaného souboru přitom samozřejmě není potřeba nuly na konci vůbec zapisovat - při dekompresi si je může program "domyslet"). Při dekompresi nelze poznat konec souboru, je tedy potřeba ještě uložit délku původního souboru nebo k bězně kódovaným znakům přidat ještě jeden specialní, který bude znamenat konec souboru (tím se zhorší kompresní poměr, ale lze ukázat, že jen velmi málo). Postup dekomprese se až na nahrazení reálných čísel čísly v pevné řádové čárce nezmění. Stejně jako u Huffmanova kódování se používá i dynamická verze.

Aritmetickému kódování je velmi podobné (je to totéž, jen řečeno jinak) tzv. Range Coding, které dosahuje stejné účinnosti jako aritmetické kódování, ale je (snad) bez patentu.


Last change Mar 24 1997 by TNT