Aritmetické kódování - celočíselná implementace
Základní informace
- statistická kompresní metoda
- dvouprůchodová kompresní metoda
- semiadaptivní kompresní metoda
- symetrická kompresní metoda
- Celý vstupní řetězec je zakódován do jediného reálného čísla <0,1).
- Nekonečně dlouhé reálné číslo je v praxi nahrazeno posloupností integerů.
Časová a paměťová složitost algoritmu
Časová složitost algoritmu: O(|Σ|+n)
Paměťová složitost algoritmu: O(|Σ|)
Paměťová složitost je dána počtem různých symbolů ve zprávě, tedy maximálně O(|Σ|). Časová složitost závisí na počtu různých symbolů a na délce zprávy. Platí n+n*|Σ|, kde |Σ| je počet různých symbolů 0 < |Σ| < n, tedy asymptoticky O(n*|Σ|).
Historie
První aritmetický kód vymyslel Peter Elias někdy před rokem 1963. I když tento kód má optimální kompresní poměr, je nepraktický, protože potřebuje nekonečnou přesnost a tím pádem nekonečně velký buffer. Tato nevýhoda může být však modifikací odstraněna. I když se dnes aritmetické kódování v praxi hojně využívá, praktické schéma nebylo k dispozici do roku 1976, kdy ho publikovali Jorma Rissanen and Richard Pasco.
Popis
Základní myšlenka
Na základě pravděpodobnosti výskytu jednotlivých symbolů vstupní abecedy je každému symbolu přiřazena odpovídající poměrná část intervalu <0,1). Při kódování je pak celý interval <0,1) postupně omezován z obou stran na základě postupně přicházejících symbolů. Každý symbol vybere z aktuálního intervalu odpovídající poměrnou část a ta se stane novým základem pro následující symbol. Kódovaná hodnota se reprezentuje libovolným reálným číslem, které leží ve výsledném intervalu získaném po přečtení všech vstupních symbolů. Vzhledem k tomu, že z takto reprezentované hodnoty nelze při dekódování určit konec zprávy, je třeba navíc ke zprávě přidat speciální znak označující konec, případně musí být uložena délka původní posloupnosti.Modifikace
Interval <0,1) (<low, high)) je nahrazen intervalem celých čísel, např. <0,9999). Rovnají-li se nejvýznamnější číslice obou čísel, je tato číslice dána na výstup, protože už se nemůže změnit. Obě čísla jsou pak posunuta doleva doplněním číslice zprava (nulou pro low a devítkou pro high).Problém podtečení (underflow)
K podtečení může dojít, když se obě čísla high a low k sobě těsně přiblíží, ale jejich nejvýznamnější číslice se nerovnají: High = 3001 Low = 2997. Kdyby nastala taková situace, pak by se čísla stále více přibližovala a nikdy by nebylo možno dát nejvýznamnější číslici na výstup. Co musíme udělat v této situaci je to, že posuneme čísla do leva od druhé pozice, a když se konečně nejvýznamnější číslice rovnají, na výstup dáme také číslice zahozené.Vzorce
Low=Low + (High - Low + 1)*LowCumFreq(x)/TotalFreqHigh=Low + (High - Low + 1)*HighCumFreq(x)/TotalFreq - 1
Pseudokód
1: begin
2: spočti četnosti zdrojových jednotek
3: output(četnosti)
4: interval I := nový interval 0..9999
5: rozděl I podle četnosti jednotek
6: readSymbol(X)
7: while (X!=EOF) do
8: begin
9: if (MSB(Low) == MSB(High)) then
10: begin
11: output(MSB)
12: případné zahozené číslice na výstup
13: shift left High i Low
14: end
15: else
16: begin
17: if (nebezpečí podtečení) then
18: begin
19: shift left High i Low od druhé pozice
20: end
21: end
22: nový I := podinterval I odpovídající X
23: rozděl I podle četnosti jednotek
24: readSymbol(X)
25: end
26: output(zbytek)
27: end
Odkazy
- Richard C. Pasco: Source Coding Algorithms for Fast Data Compression. Ph.D. Dissertation, Stanford University, CA, May 1976.
- Jorma Rissanen, Glen G. Langdon Jr.: Arithmetic Coding. IBM Journal of Research and Development 23(2), 149-162 (1979).
- Arturo San Emeterio Campos: Arithmetic coding.
- Mark Nelson: Arithmetic Coding + Statistical Modeling = Data Compression.
- Arithmetic coding. Wikipedia, the free encyclopedia.