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

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

Základní informace

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

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

Popis

Algoritmus tohoto kódování je velice podobný své neadaptivní verzi. Jediné, v čem se liší, je metoda výpočtu pravděpodobnosti symbolů abecedy. U adaptivní verze se pravděpodobnost upravuje po zakódování každého symbolu. Tato nová pravděpodobnost slouží k dělení nového intervalu. Dekodér je tak schopen během dekódování pravděpodobnosti počítat stejně jako kodér při kódování a tyto pravděpodobnosti se tedy nemusí ukládat do výsledného zakódovaného souboru.

Applet vizuálně zobrazuje tuto metodu kódovaní. V levé části okna s vizuálním vystupem jsou symboly spolu s jejich aktuální pravděpodobností. Pro reprezentaci čitatele i jmenovatele všech zlomků byla použita třída BigInteger, nedochází tedy ke ztrátě přesnosti.

Pseudokód


 1:  begin
 2:     nastav pravděpodobnost všech symbolů podle zvolené metody
 3:     interval I := nový interval 0..1
 4:     rozděl I podle pravděpodobnosti symbolů
 5:     readSymbol(X)
 6:     while (X!=EOF) do
 7:      begin
 8:        nové I := podinterval I odpovídající X
 9:        uprav pravděpodobnosti symbolů
10:        rozděl I podle pravděpodobnosti symbolů
11:        readSymbol(X)
12:      end
13:     output(libovolné číslo z intervalu I)
14:  end

Odkazy

  1. Arithmetic coding. Wikipedia, the free encyclopedia.
  2. US patents on arithmetic coding. Wikipedia, the free encyclopedia.
  3. David J. C. MacKay: Information theory, inference and learning algorithms. Cambridge University Press 2003.
  4. The Arithmetic Coding Page.
  5. Arithmetic Coding. Binary Essence.
  6. Mark Nelson: Arithmetic Coding + Statistical Modeling = Data Compression.

Ukázka