Aritmetické kódovanie


Aritmetické kódovanie predstavuje ďalšiu efektívnu kompresnú metódu a je kandidátom na nahradenie Huffmanovho kódovania v rôznych aplikáciách, pretože dáva lepšie kompresné výsledky o 5 až 10%, aj keď za cenu náročných aritmetických operácií s veľkými reálnymi číslami. Je veľmi náročné na pamäť a výkon procesora. Aritmetické kódovanie nepracuje na princípe nahradzovania vstupného znaku špecifickým kódom. Namiesto toho, kódovaný vstupný tok znakov nahradí jedným reálnym číslom z intervalu <0,1). Na začiatku uvažujeme celý tento interval. Ako sa správa predlžuje, spresňuje sa i výsledný interval a jeho horná a dolná hranica sa k sebe približujú. Čím je kódovaný znak pravdepodobnejší, tím sa interval zúži menej a k zápisu dlhšieho intervalu stačí menej bitov.

Spôsob aritmetického kódovania si ukážeme na príklade správy "baca".


Znak   Pravdepodobnosť

------ -----------------

  a          0.5       

  b          0.25

  c          0.25

Pravdepodobnosti výskytu znakov sú nám známe a potrebujeme prideliť každému znaku určitý interval z rozsahu <0,1) na základe pravdepodobnosti jeho výskytu. Pritom nieje jedno, ktorému intervalu bude pridelený daný znak. Naše 3 znaky budú zaradené do jednotlivých intervalov nasledovne.


 Znak   Pravdepodobnosť   Interval

------ ----------------- -----------

  a          0.5         0.00 - 0.50

  b          0.25        0.50 - 0.75

  c          0.25        0.75 - 1.00

Nakoľko, každý interval je vľavo uzavretý a vpravo otvorený tak napr. c bude v intervale 0.75 - 0.9999... . Dôležitý význam pri aritmetickom kódovaní má prvý kódovaný znak. Keď kódujeme správu "baca" , prvý znak je "b". Začiatočný znak nám určuje, že správa bude zakódovaná ako číslo, ktoré sa nachádza v intervale odpovedajúceho prvému znaku. V našom prípade môžeme očakávať číslo v rozsahu 0.5 - 0.75. Takto sme zakódovali prvý znak . Rozsah sa nám zmenšil na 0.5 - 0.75. Ďalší znak je "a" a prináleží mu interval 0.0 - 0.5. V rozsahu 0.5 - 0.75 bude časť 0% - 50% (interval pre "a" je 0.0 - 0.5) z tohto rozsahu reprezentovať znak "a". Tím sa nám rozsah zase zmenšil na rozmer 0.5 - 0.625. Analogickým spôsobom pokračujeme v delení intervalu ďalej.

Algoritmus pre uvedený postup kódovania by vyzeral nasledovne:


set Low to 0

set High to 1

while there are input symbols do

   take a symbol

   CodeRange = High – Low

   High = Low + CodeRange * HighRange(symbol)

   Low = Low + CodeRange * LowRange(symbol)

end of while

output Low


Znak   Low value   High value

------ ---------- -----------

         0.0        1.0

  b      0.5        0.75

  a      0.5        0.625

  c      0.59375    0.625

  a      0.59375    0.609375

princíp delenia intervalu

Výsledkom procesu kódovania je hodnota 0.59375, ktorá teraz reprezentuje správu "baca".

Proces dekódovania je nasledovný:

Algoritmus dekódovania bude vyzerať nasledovne:


get encoded number 

Do 

    find symbol whose range straddles the encoded number 

    output the symbol 

    range = symbol low value - symbol high value 

    subtract symbol low value from encoded number 

    divide encoded number by range 

until no more symbols 

Pre náš príklad bude proces dekódovania prebiehať nasledovne:


 Číslo  Znak  Low   High   Range

------- ----  ---   ----   -----

0.59375   b   0.5   0.75   0.25

0.375     a   0.0   0.5    0.5

0.75      c   0.75  1.0    0.25

0         a   0.0   0.5    0.5 

Hore uvedený algoritmus je vzhľadom k práci s veľkými reálnymi číslami (aritmetika floating point) v programátorskej praxi nepoužiteľný a je upravený tak, aby pracoval s číslami v pevnej rádovej čiarke (integer).Pri dekódovaní sme ignorovali problém, ako zastaviť proces dekódovania, keď už nieje viac symbolov k dekódovaniu. Tento problém môžeme riešiť dvoma spôsobmi: zakódovaním špeciálneho znaku EOF, alebo prenosom hodnoty dĺžky súboru spolu s kódovanou správou.


Informačné zdroje:

[1] Mark Nelson, "Arithmetic Coding + Statistical Modeling = Data Compression",
      Dr. Dobb's Journal February, 1991,
       http://www.dogma.net/markn/articles/arith/part1.htm
[2] Arturo San Emeterio Campos, "Arithmetic coding",
      http://www.arturocampos.com/ac_arithmetic.html
[3] DataCompression Reference Center, "Arithmetic coding",
      http://www.rasip.fer.hr/research/compress/algorithms/index.html
[4] P.G. Howard and J.S. Vitter, "Arithmetic Coding for Data Compression",
      http://www.cs.duke.edu/~jsv/Papers/catalog/node60.html


[hlavná strana]

Dušan SOVIČ