Aritmetické kódování představuje další přístup ke kompresi dat. Jeho výhoda je, že nepracuje pouze s celými čísly na výstupu. Jde o zdokonalení Huffmana.

Aritmetické kódování

Aritmetické kódování slouží ke kompresi vstupu. Stejně jako u Huffmanova kódování očekáváme, že na vstupu jsou znaky s různou incidencí (pravděpodobností výskytu). Na rozdíl od Huffmanova kódování pracuje aritmetické nikoli s celými čísly, nýbrž se zlomky, může tedy vykazovat lepší vlastnosti komprese při stejném vstupu.

Princip

Předpokládejme, že máme vstupní abecedu složenou z n znaků, dále máme (obvykle procentuální) incidenci těchto znaků (tj. v s jakou četností v procentech se vyskytují ve vstupním textu). Zbytek probíhá dle následujícího postupu:

  1. Rozdělíme vhodný celek (graficky např. svislou osu) na části dle pravděpodobností výskytu jednotlivých znaků:

    Ukázka aritmetického kódování

  2. Nyní dělíme následujícím způsobem: na začátku máme na počátku hodnotu 0 a na horní části hodnotu 100 (například, nebo 1 apod.). První znak vstupní abecedy nám určí podinterval, pokud je to v našem případě A, bude roven hodnotě (46, 70), v dalším kroku vybíráme stejným způsobem jako v prvním, pouze na počátku je hodnota 46 (místo 0) a na konci je hodnota 70 (místo 100). Takto vybíráme až do posledního intervalu v posledním znaku vstupní abecedy. Logika kódování je zachycena na následujícím obrázku:

    Ukázka aritmetického kódování - dělení znaků

  3. Poslední interval je určen právě posledním znakem kódové abecedy. Vybereme z něj vhodnou hodnotu, ta bude reprezentovat náš kód. Pro jednoznačné dekódování je třeba znát délku zprávy a incidenci jednotlivých znaků (případně způsob jejich seřazení), obě tyto hodnoty se tedy stávají součástí výsledného kódu.

Výstupem kódovacího procesu je interval hodnot, ze kterého vhodně vybereme vhodné číslo (v podstatě libovolné) a to je zakódovaná (komprimovaná) hodnota.

Dekódování

Probíhá přesně stejně jako kódování, ale v inverzi (vždy víme, v jakém intervalu se pohybujeme).