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
|
 |
Výsledkom procesu kódovania je hodnota 0.59375, ktorá teraz reprezentuje správu "baca".
Proces dekódovania je nasledovný:
- zakódovaná hodnota 0.59375 patrí do intervalu 0.5 - 0.75 a ten odpovedá znaku "b". Prvý znak sme teda dekódovali.
- teraz potrebujeme zmazať znak "b" zo zakódovanej hodnoty. Toto urobíme tak ,že od zakódovanej hodnoty 0.59375 odpočítame krajnú hodnotu intervalu pre znak "b"
0.59375 - 0.5 = 0.09375 - takto získanú hodnotu vydelíme rozsahom intervalu znaku "b", teda číslom 0.75 - 0.5
0.09375 / 0.25 = 0.375 - opakuj predchádzajúce kroky pre všetky znaky
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