Adaptivní aritmetické kódování - inicializace jednotek konstantou 1

Základní informace

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

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

Historie

Podle odkazu 1 byly aritmetické kódy vynalezeny Eliasem, Rissanenem a Pascem a následně dovedeny k praktické použitelnosti Wittenem v roce 1987.

Popis

Aritmetické kódování, na rozdíl od mnohých jiných metod, nekóduje jednotlivé znaky, ale rovnou celý vstup do jediného čísla z intervalu <0,1).

Celý interval je rozdělen na disjunktní části, z nichž každá připadá jedné zdrojové jednotce. Každá nově načtená jednotka se reprezentuje novým intervalem o stejném rozsahu, jaký připadal jednotce v předchozím intervalu. Nový interval se posléze rozdělí v souladu s četnostmi jednotek. Jako výsledek je možné vzít libovolné číslo z intervalu poslední načtené jednotky.

Tato modifikace, tedy adaptivní s počátečním nastavením četností všech zdrojových jednotek, se od statické verze liší tím, že četnosti jednotek se počítají v průběhu kódování podle vstupních dat.

Tato implementace používá vyhrazený znak # pro detekci konce vstupu.

Pseudokód


 1:  begin
 2:     nastavení iniciálních četností všech zdrojových jednotek na 1
 3:     interval I := nový interval <0;1)
 4:     rozděl I podle četností jednotek (rovnoměrně)
 5:     readSymbol(X)
 6:     while (X != EOF) do 
 7:      begin
 8:        nové I := podinterval I odpovídající X
 9:        rozděl I podle četností jednotek
10:        zvyš četnost X
11:        readSymbol(X)
12:      end
13:  end

Odkazy

David J. C. MacKay: Information Theory, Inference, and Learning Algorithms.
Arithmetic coding. Wikipedia, the free encyclopedia.
E. Bodden, M. Clasen, J. Kneis: Arithmetic Coding revealed - podrobný popis kompresní metody.
Context-Based Adaptive Binary Arithmetic Coding (CABAC) - implementace kompresní metody.