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Č