English
předchozí hlavní stránka obsah další

Aritmetické kódování - implementace s neomezenou aritmetikou

Základní informace

Časová a paměťová složitost algoritmu

Časová složitost algoritmu: O(|Σ|+n)
Paměťová složitost algoritmu: O(|Σ|)

Popis

Aritmetické kódování dosahuje téměř optimální komprese pro množinu symbolů a jejich pravděpodobnosti výskytu. Kompresní algoritmy, které používají atrimetické kódování, začínají výpočet zjištěním modelu dat. Čím přesnější tato predikce bude, tím víc se bude výstup podobat optimálnímu zakódování.

Příklad: jednoduchý statický mmodel charakerizující vstupní data:

  • 60% pravděpodobnost výskytu symbolu 'a' -> interval [0, 0.6)
  • 20% pravděpodobnost výskytu symbolu 'b' -> interval [0.6, 0.8)
  • 10% pravděpodobnost výskytu symbolu 'c' -> interval [0.8, 0.9)
  • 10% pravděpodobnost výskytu symbolu KONEC-VSTUPU. -> interval [0.9, 1)

Symbol KONEC-VSTUPU ukončuje vstupní datový proud. Dekodér při nalezení tohoto symbolu ukončí výpočet.

Kodér potřebuje znát v každém kroku vlastního kódování pouze tyto informace: další vstupní symbol pro zakódování, aktuální interval a pravděpodobnosti výskytu vstupních symbolů. Díky tomuto lze základní algortimus aritmetického kódování upravit na adaptivní model.

Kodér rozděluje aktuální interval na podintervaly, z nichž každý reprezentuje část o velikosti odpovídající pravděpodobnosti vstupního symbolu v aktuálním kontextu. Ten interval, který odpovídá právě přečtenému vstupnímu symbolu, bude v dalším kroku zvolen jako aktuální interval.

Když jsou všechny vstupní symboly zakódovány, výsledný interval identifikuje jednoznačně sekvenci symbolů, které byly použity k jeho konstrukci. Každý, kdo má k dispozici tento interval a model, který byl použit pro jeho výpočet, může rekonstruovat původní posloupnost symbolů.

Není nutné přenášet celý finální interval. Úplně stačí přenést jedno číslo z tohoto intervalu. Číslo z výsledného intervalu je vhodné volit tak, aby obsahovalo co nejméně nezbytných číslic (nezávisle na číselném základu).

Pseudokód

 
 1:  begin 
 2:     spočítej počty zdrojových jednotek
 3:     interval I := new interval 0..1
 4:     rozděl I podle počtu početnosti jednotek
 5:     readSymbol(X)
 6:     while (X!=EOF) do 
 7:      begin
 8:        new I := podinterval I odpovídající X
 9:        rozděl I podle počtu početnosti jednotek
10:        readSymbol(X)
11:      end
12:     output(nejlepší číslo z intervalu I)
13:  end

Odkazy

  1. Arithmetic coding. Wikipedia, the free encyclopedia.
  2. Arturo San Emeterio Campos: Arithmetic coding.

Ukázka