Aritmetické kódovanie

Aritmetické kódovanie sa dá zaradiť niekde medzi Huffmanov kód a LZ algoritmy. Potrebuje predspracovanie, alebo frekvenčnú tabuľku ako Huffmanov kód, ale na rozdiel od neho nie je to blokový kód.

Delenie intervalu

V tomto algoritme nie je nutné usporiadať symboly vstupnej abecedy podľa ich početnosti a preto sú aj v tabuľke 3.5 usporiadané podľa abecedy. Interval medzi 0 a 1 je rozdelený na 6 podintervalov, každý veľkosti . Pri každom symbole je uvedená jeho CP (cumulative portability - Langdon, 1984), kde . Teraz vidieť, že spodná hranica každého podintervalu je hodnota. Šírka podintervalu je rovná početnosti odpovedajúceho znaku zo zdrojovej abecedy.

Tento algoritmus produkuje jedno kódové slovo, je to číslo z intervalu , pre skupinu zdrojových znakov. Záleží iba na dohode, koľko znakov to je. To značí, že pri dekódovaní z jedného kódového slova vieme dekódovať hneď niekoľko zdrojových symbolov.

Na príklade si ukážeme kompresiu a dekompresiu reťazca .

Tabuľka 3.5: Aritmetické kódovanie

Zdroj. symbol	Početnosť	Pridelený interval	CP
			0

Obrázok 3.12: Delenie intervalu pri aritmetickom kódovaní

Kompresia

Na začiatku máme interval rozdelený na šesť častí (viď obrázok 3.12a). Keďže prvý symbol je , zoberieme podinterval . To znamená, že výsledné kódové slovo bude z tohto intervalu. Tento interval znova rozdelíme v takom istom pomere, teda podľa početnosti zdrojových symbolov, ako interval (viď obrázok 3.12b). Znak vyberie z tohto intervalu podinterval , ktorý následne rozdelíme ako v predchádzajúcom kroku. Pomerne jednoducho sa dá napísať vzťah, podľa ktorého získame pozíciu nového podintervalu (na určenie nám stačí jeho spodná hranica a veľkosť).

Nech je index znaku, ktorý bol z daného intervalu vybratý. Potom pre všetky zdrojové symboly aplikujeme následovný výpočet:

Tieto dve rekurzie, tiež nazývané dvojitá rekurzia ( double recursion, Langdon, 1984), hrajú hlavnú úlohu v aritmetickom kódovaní.

Podobným spôsobom by prebiehalo delenie intervalu pre . Po poslednom delení nám ostane podinterval (obrázok 3.12f). Tento interval reprezentuje dosiaľ zakódované dáta. Kódové slovo, ktoré bude reprezentovať tieto dáta, bude reálne číslo z tohto intervalu. Najvhodnejším kandidátom je číslo, ktorého zápis v binárnej podobe má najmenej znakov, aby úroveň kompresie bola čo najviac účinná.

Dekompresia

Dekódovanie je v tomto algoritme presne opačný proces. Na začiatku máme k dispozícii frekvenčnú tabuľku 3.5, interval a reálne číslo, ktoré nám reprezentuje zakódovanú postupnosť. V našom prípade nech to reálne číslo je spodná hranica posledného intervalu, ktorý sme dostali pri kompresii, teda .

Na začiatku rozdelíme interval podľa tabuľky 3.5 rovnako ako v prvom kroku kompresie. Zistíme, v ktorom intervale z vytvorených sa nachádza naše kódové slovo. Zdrojový symbol prislúchajúci danému intervalu, teda , je dekódovaný symbol. Hranice intervalu, ktorý reprezentoval tento znak budú slúžiť na ďalšie delenie, presne tak isto ako pri kompresii.

Preskočme niekoľko krokov a posuňme sa až k dekódovaniu symbola . Po jeho dekódovaní nám ostane interval . Otázka znie: ako vieme, že máme v tomto bode prestať s ďalším delením intervalu? Tu záleží na dohode medzi kóderom a dekóderom. V princípe existuje niekoľko dohôd, spomeniem iba dva:

• kóduje sa pevný počet znakov (v našom prípade by to bolo 6).
• do zdrojovej abecedy sa pridá ďalší špeciálny znak (napr. $), ktorý sa v nej predtým nevyskytoval s početnosťou . Keď sa kóder rozhodne ukončiť sekvenciu, tak zakóduje tento znak a na výstup dá reálne číslo z daného intervalu. Keď dekóder tento znak rozpozná, tak vie, že má skončiť, ale tento znak nepošle na výstup.

Záverečné poznámky

Oba procesy, kompresia aj dekompresia, používajú iba aritmetické operácie (sčítanie, násobenie, odčítanie, delenie). Preto sa tento algoritmus volá aritmetické kódovanie.

Kódovaním zdrojových znakov sa výsledný podinterval stáva menším a menším, teda spodná a horná hranica intervalu sa stále približujú. Tu sa stretávame s problémom presnosti reprezentácie reálnych čísel v počítačoch, kde ich presnosť je obmedzená a môže sa stať, že tieto hranice splynú do jedného čísla. Tento problém bol vyriešený v tzv. inkrementálnej implementácii aritmetického kódovania\footnote{viac o tejto technike sa môžete dozvedieť v [3].