Aritmetické kódování - Arithmetic coding

Aritmetické kódování ( AC ) je forma kódování entropie používaná při bezztrátové kompresi dat . Řetězec znaků je obvykle reprezentován pomocí pevného počtu bitů na znak, jako v kódu ASCII . Když je řetězec převeden na aritmetické kódování, často používané znaky budou uloženy s méně bity a méně často se vyskytující znaky budou uloženy s více bity, což povede k celkovému použití méně bitů. Aritmetické kódování se liší od jiných forem entropického kódování, jako je Huffmanovo kódování , tím, že aritmetické kódování namísto rozdělení vstupu na symboly komponent a jejich nahrazení kódem kóduje celou zprávu na jedno číslo, zlomek s libovolnou přesností q , kde 0,0 ≤ q <1,0 . Představuje aktuální informace jako rozsah definovaný dvěma čísly. Nedávná rodina entropických kodérů nazývaných asymetrické číselné systémy umožňuje rychlejší implementaci díky přímému provozu na jediném přirozeném čísle představujícím aktuální informace.

Příklad aritmetického kódování za předpokladu pevného rozdělení pravděpodobnosti tří symbolů „A“, „B“ a „C“. Pravděpodobnost „A“ je 50%, pravděpodobnost „B“ je 33% a pravděpodobnost „C“ 17%. Dále předpokládáme, že hloubka rekurze je známa v každém kroku. V prvním kroku kódujeme „B“, které je uvnitř intervalu [0,5, 0,83): Binární číslo „0,10 x “ je nejkratší kód, který představuje interval, který je zcela uvnitř [0,5, 0,83). „ x “ znamená libovolnou bitovou sekvenci. Existují dva extrémní případy: nejmenší x znamená nulu, což představuje levou stranu znázorněného intervalu. Pak je levá strana intervalu dec (0,10) = 0,5. Na druhém konci znamená x konečnou posloupnost jedniček, která má horní limit dec (0,11) = 0,75. Proto „0,10 x “ představuje interval [0,5; 0,75), který je uvnitř [0,5; 0,83]. Nyní můžeme vynechat „0.“ část, protože všechny intervaly začínají na „0.“ a část „ x “ můžeme ignorovat, protože bez ohledu na to, jakou bitovou sekvenci představuje, zůstaneme uvnitř [0,5, 0,75).

Podrobnosti a příklady implementace

Kódování zprávy „WIKI“ aritmetickým kódováním

1.	Jsou nalezeny četnosti písmen.
2.	Interval [0, 1) je rozdělen v poměru frekvencí.
3–5.	Odpovídající interval je iterativně rozdělen pro každé písmeno ve zprávě.
6.	K reprezentaci zprávy je zvolena libovolná hodnota v posledním intervalu.
2 * –6 *.	Rozdělení a hodnota, pokud byla zpráva místo toho „KIWI“.

Výše uvedený příklad vizualizovaný jako kruh, hodnoty v červené barvě kódující „WIKI“ a „KIWI“ - na obrázku SVG najeďte kurzorem na interval, abyste jej zvýraznili a ukázali jeho statistiky

Rovné pravděpodobnosti

V nejjednodušším případě je pravděpodobnost výskytu každého symbolu stejná. Zvažte například sadu tří symbolů, A, B a C, u nichž je každý stejně pravděpodobný výskyt. Jednoduché kódování bloku by vyžadovalo 2 bity na symbol, což je zbytečné: nikdy se nepoužívá jedna z bitových variant. To znamená, že symboly A, B a C mohou být kódovány v tomto pořadí jako 00, 01 a 10, s 11 nepoužitými.

Efektivnějším řešením je představit posloupnost těchto tří symbolů jako racionální číslo v základně 3, kde každá číslice představuje symbol. Například sekvence „ABBCAB“ by se mohla stát 0,011201 ₃ , v aritmetickém kódování jako hodnota v intervalu [0, 1). Dalším krokem je kódování tohoto ternárního čísla pomocí binárního čísla s pevným bodem s dostatečnou přesností pro jeho obnovení, například 0,0010110010 ₂ - to je pouze 10 bitů; Ve srovnání s naivním kódováním bloku jsou uloženy 2 bity. To je možné u dlouhých sekvencí, protože existují účinné místní algoritmy pro převod báze libovolně přesných čísel.

Chcete-li dekódovat hodnotu, protože původní řetězec měl délku 6, lze jej jednoduše převést zpět na základnu 3, zaokrouhlit na 6 číslic a obnovit řetězec.

Definování modelu

Obecně platí, že aritmetické kodéry mohou produkovat téměř optimální výstup pro jakoukoli danou sadu symbolů a pravděpodobností. (Optimální hodnota je −log ₂ P bity pro každý symbol pravděpodobnosti P ; viz teorém o zdrojovém kódování .) Kompresní algoritmy, které používají aritmetické kódování, začínají určením modelu dat - v podstatě predikce toho, jaké vzory budou v symbolech nalezeny zprávy. Čím přesnější je tato předpověď, tím blíže k optimálnímu bude výstup.

Příklad : jednoduchý statický model pro popis výstupu konkrétního monitorovacího nástroje v čase může být:

• 60% šance na symbol NEUTRÁLNÍ
• 20% šance na symbol POZITIVNÍ
• 10% šance na symbol NEGATIVNÍ
• 10% šance na symbol KONEC DAT. (Přítomnost tohoto symbolu znamená, že stream bude interně ukončen, což je při kompresi dat poměrně běžné; pokud se tento symbol objeví v datovém proudu, dekodér bude vědět, že byl dekódován celý stream.)

Modely mohou také zpracovávat jiné abecedy než jednoduchou sadu čtyř symbolů zvolenou pro tento příklad. Jsou také možné sofistikovanější modely: modelování vyššího řádu mění svůj odhad aktuální pravděpodobnosti symbolu na základě symbolů, které mu předcházejí ( kontext ), takže například v modelu pro anglický text je procentuální šance „ u "by bylo mnohem vyšší, pokud by následovalo za" Q "nebo" q ". Modely mohou být dokonce adaptivní , takže neustále mění svou predikci dat na základě toho, co stream ve skutečnosti obsahuje. Dekodér musí mít stejný model jako kodér.

Kódování a dekódování: přehled

Obecně je každý krok procesu kódování, s výjimkou posledního, stejný; kodér má v podstatě jen tři údaje, které je třeba vzít v úvahu:

• Další symbol, který je třeba kódovat
• Aktuální interval (na samém začátku procesu kódování je interval nastaven na [0,1], ale to se změní)
• Pravděpodobnosti, které model přiřadí každému z různých symbolů, které jsou v této fázi možné (jak již bylo zmíněno dříve, modely vyššího řádu nebo adaptivní modely znamenají, že tyto pravděpodobnosti nemusí být nutně stejné v každém kroku.)

Kodér rozděluje aktuální interval na dílčí intervaly, z nichž každý představuje zlomek aktuálního intervalu úměrný pravděpodobnosti daného symbolu v aktuálním kontextu. Kterýkoli interval odpovídá aktuálnímu symbolu, který má být dále kódován, se stane intervalem použitým v dalším kroku.

Příklad : pro model se čtyřmi symboly výše:

• interval pro NEUTRAL by byl [0, 0,6)
• interval pro POZITIVNÍ by byl [0,6; 0,8)
• interval pro NEGATIVNÍ by byl [0,8; 0,9)
• interval pro KONEC DAT by byl [0,9, 1).

Když byly všechny symboly zakódovány, výsledný interval jednoznačně identifikuje posloupnost symbolů, které jej vytvořily. Kdokoli, kdo má stejný konečný interval a model, který se používá, může rekonstruovat posloupnost symbolů, která musí vstoupit do kodéru, aby výsledkem byl tento konečný interval.

Není však nutné přenášet konečný interval; je nutné přenést pouze jeden zlomek, který leží v tomto intervalu. Zejména je nutné pouze přenést dostatek číslic (v jakékoli základně) zlomku, aby všechny zlomky, které začínají těmito číslicemi, spadaly do konečného intervalu; to zaručí, že výsledný kód bude kód předpony .

Kódování a dekódování: příklad

Diagram ukazující dekódování 0,538 (kulatá tečka) v ukázkovém modelu. Oblast je rozdělena do podoblastí úměrných kmitočtům symbolů, potom je podoblast obsahující bod postupně rozdělena stejným způsobem.

Zvažte postup dekódování zprávy zakódované daným čtyřmístným modelem. Zpráva je zakódována ve zlomku 0,538 (za účelem srozumitelnosti místo binárního použití desetinného místa; také za předpokladu, že pro dekódování zprávy existuje pouze tolik číslic, kolik je potřeba.)

Proces začíná stejným intervalem, jaký používá kodér: [0,1) a používá stejný model a dělí jej na stejné čtyři dílčí intervaly, které musí mít kodér. Frakce 0,538 spadá do dílčího intervalu pro NEUTRÁL, [0, 0,6); to znamená, že první symbol načtený z kodéru musel být NEUTRÁLNÍ, takže se jedná o první symbol zprávy.

Dále rozdělte interval [0, 0,6) na dílčí intervaly:

• interval pro NEUTRAL by byl [0, 0,36), 60% z [0, 0,6) .
• interval pro POZITIVNÍ by byl [0,36; 0,48), 20% z [0, 0,6] .
• interval pro NEGATIVNÍ by byl [0,48; 0,54), 10% z [0, 0,6] .
• interval pro END-OF-DATA by byl [0,54; 0,6), 10% z [0, 0,6] .

Protože 0,538 je v intervalu [0,48; 0,54), musel být druhý symbol zprávy NEGATIVNÍ.

Znovu rozdělte náš aktuální interval na dílčí intervaly:

• interval pro NEUTRAL by byl [0,48; 0,516).
• interval pro POZITIVNÍ by byl [0,516, 0,528).
• interval pro NEGATIVNÍ by byl [0,528, 0,534).
• interval pro KONEC DAT by byl [0,534; 0,540).

Nyní 0,538 spadá do intervalu symbolu END-OF-DATA; proto to musí být další symbol. Jelikož se jedná také o interní symbol ukončení, znamená to, že je dekódování dokončeno. Pokud stream není interně ukončen, musí existovat nějaký jiný způsob, jak označit, kde se stream zastaví. Jinak by proces dekódování mohl pokračovat navždy a omylem číst více symbolů z frakce, než do kterých bylo ve skutečnosti zakódováno.

Zdroje neúčinnosti

Zpráva 0,538 v předchozím příkladu mohla být kódována stejně krátkými zlomky 0,534, 0,535, 0,536, 0,537 nebo 0,539. To naznačuje, že použití desetinných míst místo binárních přineslo určitou neefektivitu. Toto je správně; informační obsah třímístného desetinného místa jsou bity ; stejná zpráva mohla být zakódována v binárním zlomku 0,10001010 (ekvivalent 0,5390625 desetinně) za cenu pouhých 8 bitů. (Konečná nula musí být zadána v binárním zlomku, jinak by byla zpráva nejednoznačná bez externích informací, jako je velikost komprimovaného streamu.) ${\ displaystyle 3 * \ log _ {2} (10) \ přibližně 9 966}$

Tento 8bitový výstup je větší než informační obsah nebo entropie zprávy, která je

${\ displaystyle \ sum - \ log _ {2} (p_ {i}) = - \ log _ {2} (0,6) - \ log _ {2} (0,1) - \ log _ {2} (0,1) = 7,381 {\ text {bits}}}$

V binárním kódování však musí být použit celočíselný počet bitů, takže kodér pro tuto zprávu by použil alespoň 8 bitů, což by vedlo ke zprávě o 8,4% větší než obsah entropie. Tato neefektivita maximálně 1 bitu má za následek relativně menší režii, jak roste velikost zprávy.

Kromě toho byly nárokované pravděpodobnosti symbolů [0,6; 0,2; 0,1; 0,1), ale skutečné frekvence v tomto příkladu jsou [0,33; 0; 0,33; 0,33). Pokud jsou intervaly upraveny pro tyto frekvence, entropie zprávy by byla 4,755 bitů a stejná zpráva NEUTRAL NEGATIVE END-OF-DATA by mohla být zakódována jako intervaly [0, 1/3); [1/9, 2/9); [5/27, 6/27); a binární interval [0,00101111011; 0,00111000111). Toto je také příklad toho, jak statistické metody kódování, jako je aritmetické kódování, mohou vytvořit výstupní zprávu, která je větší než vstupní zpráva, zvláště pokud je vypnutý model pravděpodobnosti.

Adaptivní aritmetické kódování

Jednou z výhod aritmetického kódování oproti jiným podobným metodám komprese dat je pohodlí adaptace. Přizpůsobení je změna frekvenčních (nebo pravděpodobnostních) tabulek během zpracování dat. Dekódovaná data odpovídají původním datům, pokud je frekvenční tabulka v dekódování nahrazena stejným způsobem a ve stejném kroku jako v kódování. Synchronizace je obvykle založena na kombinaci symbolů vyskytujících se během procesu kódování a dekódování.

Přesnost a renormalizace

Výše uvedená vysvětlení aritmetického kódování obsahují určité zjednodušení. Zejména se zapisují, jako by kodér nejprve vypočítal zlomky představující koncové body intervalu v plné míře, s použitím nekonečné přesnosti , a zlomek do konečné podoby převedl pouze na konci kódování. Spíše než se pokoušet simulovat nekonečnou přesnost, většina aritmetických kodérů místo toho pracuje na pevném limitu přesnosti, o kterém vědí, že dekodér bude schopen odpovídat, a zaokrouhluje vypočítané zlomky na jejich nejbližší ekvivalenty s touto přesností. Příklad ukazuje, jak by to fungovalo, pokud by model volal po rozdělení intervalu [0,1) na třetiny, a to by bylo aproximováno s 8bitovou přesností. Všimněte si, že nyní je známa přesnost, stejně tak binární rozsahy, které budeme moci použít.

Proces zvaný renormalizace udržuje konečnou přesnost, aby se nestal limitem celkového počtu symbolů, které lze kódovat. Kdykoli je rozsah snížen na místo, kde všechny hodnoty v rozsahu sdílejí určité počáteční číslice, jsou tyto číslice odeslány na výstup. Pro mnoho číslic přesnosti, které počítač dokáže zpracovat, však nyní zpracovává méně než to, takže stávající číslice jsou posunuty doleva a napravo jsou přidány nové číslice, aby se rozsah co nejvíce rozšířil. Všimněte si, že k tomuto výsledku dochází ve dvou ze tří případů z našeho předchozího příkladu.

Aritmetické kódování jako obecná změna radixu

Připomeňme, že v případě, že symboly měly stejnou pravděpodobnost, mohlo být aritmetické kódování implementováno jednoduchou změnou základny nebo radixu. Obecně lze aritmetické (a rozsahové) kódování interpretovat jako obecnou změnu radixu . Například se můžeme podívat na jakoukoli posloupnost symbolů:

${\ displaystyle \ mathrm {DABDDB}}$

jako číslo v určité základně za předpokladu, že zúčastněné symboly tvoří uspořádanou množinu a každý symbol v uspořádané množině označuje postupné celé číslo A = 0, B = 1, C = 2, D = 3 atd. Výsledkem jsou následující frekvence a kumulativní frekvence:

Kumulativní frekvence pro položku je součet všech frekvencí předcházejících položku. Jinými slovy, kumulativní frekvence je průběžný součet frekvencí.

V pozičním číslovacím systému se radix neboli základna číselně rovná počtu různých symbolů použitých k vyjádření čísla. Například v desítkové soustavě je počet symbolů 10, jmenovitě 0, 1, 2, 3, 4, 5, 6, 7, 8 a 9. Radix se používá k vyjádření jakéhokoli konečného celého čísla v předpokládaném multiplikátoru v polynomiální forma. Například číslo 457 je ve skutečnosti 4 × 10 ²  + 5 × 10 ¹  + 7 × 10 ⁰ , kde se předpokládá základ 10, ale není explicitně zobrazen.

Zpočátku převedeme DABDDB na číslici base-6, protože 6 je délka řetězce. Řetězec je nejprve mapován na číslicový řetězec 301331, který je poté polynomem mapován na celé číslo:

${\ displaystyle 6 ^ {5} \ krát 3 + 6 ^ {4} \ krát 0 + 6 ^ {3} \ krát 1 + 6 ^ {2} \ krát 3 + 6 ^ {1} \ krát 3 + 6 ^ {0} \ krát 1 = 23671}$

Výsledek 23671 má délku 15 bitů, což není příliš blízko teoretickému limitu ( entropie zprávy), což je přibližně 9 bitů.

Abychom zakódovali zprávu o délce blíže k teoretickému limitu stanovenému informační teorií, musíme trochu zobecnit klasický vzorec pro změnu radixu. Vypočítáme dolní a horní mez L a U a zvolíme číslo mezi nimi. Pro výpočet L vynásobíme každý člen ve výše uvedeném výrazu součinem frekvencí všech dříve vyskytujících se symbolů:

${\ displaystyle {\ begin {aligned} L = {} & (6 ^ {5} \ krát 3) + {} \\ & 3 \ krát (6 ^ {4} \ krát 0) + {} \\ & (3 \ krát 1) \ krát (6 ^ {3} \ krát 1) + {} \\ & (3 \ krát 1 \ krát 2) \ krát (6 ^ {2} \ krát 3) + {} \\ & ( 3 \ krát 1 \ krát 2 \ krát 3) \ krát (6 ^ {1} \ krát 3) + {} \\ & (3 \ krát 1 \ krát 2 \ krát 3 \ krát 3) \ krát (6 ^ { 0} \ krát 1) {} \\ = {} & 25002 \ end {zarovnáno}}}$

Rozdíl mezi tímto polynomem a polynomem výše je v tom, že každý člen je vynásoben součinem frekvencí všech dříve vyskytujících se symbolů. Obecněji lze L vypočítat jako:

${\ displaystyle L = \ sum _ {i = 1} ^ {n} n ^ {ni} C_ {i} {\ prod _ {k = 1} ^ {i-1} f_ {k}}}$

kde jsou kumulativní frekvence a jsou frekvence výskytů. Rejstříky označují pozici symbolu ve zprávě. Ve zvláštním případě, kdy jsou všechny frekvence 1, se jedná o vzorec změny báze. ${\ displaystyle \ scriptstyle C_ {i}}$${\ displaystyle \ scriptstyle f_ {k}}$${\ displaystyle \ scriptstyle f_ {k}}$

Horní mez U bude L plus součin všech frekvencí; v tomto případě U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. U je obecně dáno vztahem:

${\ displaystyle U = L + \ prod _ {k = 1} ^ {n} f_ {k}}$

Nyní můžeme zvolit libovolné číslo z intervalu [ L , U ), které reprezentuje zprávu; jednou pohodlnou volbou je hodnota s nejdelší možnou stopou nul, 25100, protože nám umožňuje dosáhnout komprese reprezentací výsledku jako 251 × 10 ² . Nule mohou být také zkráceny, což dává 251, pokud je délka zprávy uložena samostatně. Delší zprávy budou mít tendenci mít delší stopy nul.

K dekódování celého čísla 25100 lze polynomiální výpočet obrátit, jak je znázorněno v tabulce níže. V každé fázi je identifikován aktuální symbol, poté je od výsledku odečten odpovídající člen.

Během dekódování si vezmeme slovo po vydělení odpovídající silou 6. Výsledek se poté porovná s kumulativními intervaly a z vyhledávací tabulky se vybere příslušný symbol. Po identifikaci symbolu je výsledek opraven. Proces pokračuje po známou délku zprávy nebo zatímco zbývající výsledek je pozitivní. Jediným rozdílem ve srovnání s klasickou změnou základny je to, že s každým symbolem může být spojena řada hodnot. V tomto příkladu je A vždy 0, B je 1 nebo 2 a D je libovolná z 3, 4, 5. To je v přesném souladu s našimi intervaly, které jsou určeny frekvencemi. Když jsou všechny intervaly rovny 1, máme speciální případ klasické základní změny.

Teoretický limit komprimované zprávy

Dolní mez L nikdy nepřekročí n ⁿ , kde n je velikost zprávy, a proto může být vyjádřena v bitech. Po výpočtu horní hranice U a zmenšení zprávy výběrem čísla z intervalu [ L ,  U ) s nejdelší stopou nul můžeme předpokládat, že tuto délku lze zmenšit o bity. Vzhledem k tomu, že každá frekvence v produktu se vyskytuje přesně stejně často jako hodnota této frekvence, můžeme pro výpočet produktu použít velikost abecedy A${\ displaystyle \ scriptstyle \ log _ {2} (n ^ {n}) \; = \; n \ log _ {2} (n)}$${\ displaystyle \ scriptstyle \ log _ {2} \ left (\ prod _ {k = 1} ^ {n} f_ {k} \ right)}$

${\ displaystyle \ prod _ {k = 1} ^ {n} f_ {k} = \ prod _ {k = 1} ^ {A} f_ {k} ^ {f_ {k}}}$

Aplikováním protokolu ₂ na odhadovaný počet bitů ve zprávě bude finální zpráva (nepočítaje logaritmickou režii pro tabulky délky a frekvence zpráv) odpovídat počtu bitů daných entropií , která je u dlouhých zpráv velmi blízká optimálnímu:

${\ displaystyle - \ left [\ sum _ {i = 1} ^ {A} f_ {i} \ log _ {2} (f_ {i}) \ right] * n}$

Spojení s jinými kompresními metodami

Huffmanovo kódování

Protože aritmetické kódování nekomprimuje jeden údaj najednou, může se při komprimaci řetězců iid libovolně přiblížit entropii . Naproti tomu za použití rozšíření o Huffmanovo kódování (na řetězce) nedosahuje entropie, pokud všechny pravděpodobnosti abecedy symbolů jsou umocněny dvěma, v tomto případě jak Huffmanovo a aritmetické kódování dosáhnout entropie.

Když naivně Huffman kóduje binární řetězce, není možná žádná komprese, i když je entropie nízká (např. ({0, 1}) má pravděpodobnosti {0,95, 0,05}). Huffmanovo kódování přiřadí každé hodnotě 1 bit, což má za následek kód stejné délky jako vstup. Naproti tomu aritmetické kódování komprimuje bity dobře a přibližuje se optimálnímu kompresnímu poměru

${\ displaystyle 1 - [- 0,95 \ log _ {2} (0,95) + - 0,05 \ log _ {2} (0,05)] \ přibližně 71,4 \%.}$

Jedním z jednoduchých způsobů řešení suboptimality kódování podle Huffmana je zřetězení symbolů („blokování“) za účelem vytvoření nové abecedy, ve které každý nový symbol představuje posloupnost původních symbolů - v tomto případě bitů - z původní abecedy. Ve výše uvedeném příkladu by seskupení sekvencí tří symbolů před kódováním vytvořilo nové „supersymboly“ s následujícími frekvencemi:

• 000: 85,7%
• 001, 010, 100: Každý 4,5%
• 011, 101, 110: 0,24% každý
• 111: 0,0125%

V tomto seskupení má Huffmanovo kódování v průměru 1,3 bitu na každé tři symboly, nebo 0,433 bitu na symbol, ve srovnání s jedním bitem na symbol v původním kódování, tj. Kompresi. Povolení libovolně velkých sekvencí se libovolně blíží entropii - stejně jako aritmetické kódování - ale vyžaduje k tomu obrovské kódy, takže to není tak praktické jako aritmetické kódování pro tento účel. ${\ displaystyle 56,7 \%}$

Alternativou je kódování délek běhu pomocí kódů Golomb-Rice založených na Huffmanovi . Takový přístup umožňuje jednodušší a rychlejší kódování / dekódování než aritmetické kódování nebo dokonce Huffmanovo kódování, protože toto vyžaduje vyhledávání v tabulce. V příkladu {0,95, 0,05} dosahuje kód Golomb-Rice se čtyřbitovým zbytkem kompresního poměru , mnohem blíže k optimálnímu, než při použití tříbitových bloků. Kódy Golomb-Rice se vztahují pouze na vstupy Bernoulli , jako je ten v tomto příkladu, takže nejde o náhradu blokování ve všech případech. ${\ displaystyle 71,1 \%}$

Historie a patenty

Základní algoritmy pro aritmetické kódování vyvinuli nezávisle Jorma J. Rissanen z IBM Research a Richard C. Pasco, Ph.D. student na Stanford University ; oba byly publikovány v květnu 1976. Pasco uvádí předpublikační návrh článku Rissanena a komentáře ke vztahu mezi jejich díly:

Jeden algoritmus rodiny vyvinul nezávisle Rissanen [1976]. Posune element kódu na nejvýznamnější konec akumulátoru pomocí ukazatele získaného sčítáním a umocněním. Nyní porovnáme alternativy ve třech možnostech a uvidíme, že je lepší posunout element kódu spíše než akumulátor a přidat prvky kódu na nejméně významný konec akumulátoru.

Méně než rok po zveřejnění požádala IBM o americký patent na práci Rissanena. Pascova práce nebyla patentována.

Americké patenty historicky pokrývaly řadu specifických technik pro aritmetické kódování, ačkoli od doby, kdy patenty vypršely, prošly do veřejného vlastnictví různé známé metody. Techniky, na které se vztahují patenty, mohou být nezbytné pro implementaci algoritmů pro aritmetické kódování, které jsou specifikovány v některých formálních mezinárodních standardech. V takovém případě jsou takové patenty obecně k dispozici pro licencování na základě takzvaných „rozumných a nediskriminačních“ ( RAND ) licenčních podmínek (alespoň v rámci politiky výboru pro standardy). V některých dobře známých případech (včetně některých zahrnujících patenty IBM, které mezitím vypršely) byly tyto licence k dispozici zdarma a v jiných případech byly vyžadovány licenční poplatky. Dostupnost licencí podle podmínek RAND nemusí nutně uspokojit každého, kdo by tuto technologii chtěl použít, protože to, co se může zdát „rozumné“ pro společnost připravující proprietární komerční softwarový produkt, se může zdát mnohem méně rozumné pro bezplatný software nebo open source projekt.

Alespoň jeden významný softwarový program pro kompresi, bzip2 , záměrně přerušil používání aritmetického kódování ve prospěch Huffmanova kódování kvůli vnímané patentové situaci v té době. Kodéry a dekodéry také ve formátu souboru JPEG , který má možnosti jak pro Huffmanovo kódování, tak pro aritmetické kódování, obvykle podporuje pouze možnost Huffmanova kódování, což bylo původně kvůli problémům s patentem; výsledkem je, že téměř všechny obrázky JPEG, které se dnes používají, používají kódování Huffman, i když platnost aritmetických kódovacích patentů JPEG vypršela z důvodu stáří standardu JPEG (jehož design byl přibližně dokončen do roku 1990). JPEG XL , stejně jako archivátory jako PackJPG, Brunsli a Lepton, které mohou bezztrátově převést soubory kódované Huffmanem na soubory s aritmetickým kódováním (nebo asymetrické číselné systémy v případě JPEG XL), což ukazuje až 25% úsporu velikosti.

Aritmetický kódovací algoritmus formátu komprese obrazu JPEG je založen na následujících citovaných patentech (od vypršení platnosti).

• Patent USA 4 652 856 - ( IBM ) Podáno 4. února 1986, uděleno 24. března 1987 - Kottappuram MA Mohiuddin, Jorma Johannen Rissanen - aritmetický kód bez multiplikace
• US Patent 4,905,297 - (IBM) Podáno 18. listopadu 1988, uděleno 27. února 1990 - Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannen Rissanen - aritmetický kódovací kódovací a dekódovací systém
• Patent USA 4 935 882 - (IBM) Podáno 20. července 1988, uděleno 19. června 1990 - William B. Pennebaker, Joan L. Mitchell - Adaptace pravděpodobnosti pro aritmetické kodéry
• Patent JP 1021672 - ( Mitsubishi ) Podáno 21. ledna 1989, uděleno 10. srpna 1990 - Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida - kódovací systém
• Patent JP 2-46275 - (Mitsubishi) Podáno 26. února 1990, uděleno 5. listopadu 1991 - Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino - Kódovací zařízení a metoda kódování

Mezi další patenty (většinou také s prošlou platností) týkající se aritmetického kódování patří následující.

• US Patent 4,122,440 - (IBM) Podáno 4. března 1977, uděleno 24. října 1978 - Glen George Langdon, Jorma Johannen Rissanen - Metoda a prostředky pro aritmetické kódování řetězců
• US Patent 4,286,256 - (IBM) Podáno 28. listopadu 1979, uděleno 25. srpna 1981 - Glen George Langdon, Jorma Johannen Rissanen - Metoda a prostředky pro aritmetické kódování využívající omezený počet operací
• US Patent 4 467 317 - (IBM) Podáno 30. března 1981, uděleno 21. srpna 1984 - Glen George Langdon, Jorma Johannen Rissanen - Vysokorychlostní aritmetické kódování komprese pomocí souběžné aktualizace hodnoty
• Patent USA 4 891 643 - (IBM) Podáno 15. září 1986, uděleno 2. ledna 1990 - Joan L. Mitchell, William B. Pennebaker - Aritmetické kódování komprese / dekomprese dat selektivně použitými, různými aritmetickými kódovacími kodéry a dekodéry
• Patent JP 11782787 - ( NEC ) Podáno 13. května 1987, uděleno 18. listopadu 1988 - Michio Shimada - aritmetické kódovací zařízení pro kompresi dat
• JP 15015487 - ( KDDI ) Soubor 18 června, 1987, uděleno 22 prosince 1988 - Shuichi Matsumoto, Masahiro Saito - Systém pro prevenci, nesoucí šíření v aritmetické kódování
• Patent USA 4 933 883 - (IBM) podaný 3. května 1988, udělen 12. června 1990 - William B. Pennebaker, Joan L. Mitchell - Adaptace pravděpodobnosti pro aritmetické kodéry
• Patent USA 4 989 000 - (IBM) Podáno 19. června 1989, uděleno 29. ledna 1991 - Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach - Komprese datového řetězce pomocí aritmetického kódování se zjednodušeným odhadem pravděpodobnosti podintervalu
• Patent USA 5 099 440 - (IBM) Podáno 5. ledna 1990, uděleno 24. března 1992 - William B. Pennebaker, Joan L. Mitchell - Adaptace pravděpodobnosti pro aritmetické kodéry
• US Patent 5,272,478 - ( Ricoh ) Podáno 17. srpna 1992, uděleno 21. prosince 1993 - James D. Allen - Způsob a zařízení pro entropické kódování

Poznámka: Tento seznam není vyčerpávající. Seznam dalších patentů v USA najdete na následujících odkazech. Dirac kodek používá aritmetické kódování a není patent.

Patenty na aritmetické kódování mohou existovat v jiných jurisdikcích; diskuse o patentovatelnosti softwaru po celém světě najdete v softwarových patentech .

Srovnávací hodnoty a další technické vlastnosti

Každá programová implementace aritmetického kódování má jiný kompresní poměr a výkon. Zatímco kompresní poměry se liší jen málo (obvykle pod 1%), doba spuštění kódu se může lišit o faktor 10. Výběr správného kodéru ze seznamu veřejně dostupných kodérů není jednoduchý úkol, protože výkon a kompresní poměr závisí také na typ dat, zejména o velikosti abecedy (počet různých symbolů). Jeden ze dvou konkrétních kodérů může mít lepší výkon pro malé abecedy, zatímco druhý může vykazovat lepší výkon pro velké abecedy. Většina kodérů má omezení velikosti abecedy a mnoho z nich se specializuje na abecedy přesně dvou symbolů (0 a 1).

Viz také

• Asymetrické číselné soustavy
• Kontextově adaptivní binární aritmetické kódování (CABAC)
• Komprese dat
• Entropické kódování
• Huffmanovo kódování
• Kódování rozsahu

Poznámky

Reference

• MacKay, David JC (září 2003). „Kapitola 6: Streamovací kódy“ . Informační teorie, odvození a výukové algoritmy . Cambridge University Press . ISBN 0-521-64298-1. Archivovány z originálu (PDF / PostScript / DjVu / LaTeX ) dne 22. prosince 2007 . Vyvolány 30 December 2007 .
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Oddíl 22.6. Aritmetické kódování“ . Numerické recepty: The Art of Scientific Computing (3. vyd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Rissanen, Jorma (květen 1976). "Zobecněná Kraftova nerovnost a aritmetické kódování" . IBM Journal of Research and Development . 20 (3): 198–203. doi : 10,1147 / kolo 203.0198 . Vyvolány 21 September 2007 .
• Rissanen, JJ; Langdon GG, Jr. (březen 1979). „Aritmetické kódování“ (PDF) . IBM Journal of Research and Development . 23 (2): 149–162. doi : 10,1147 / kolo.232.0149 . Archivovány z původního (PDF) dne 28. září 2007 . Vyvolány 22 September 2007 .
• Witten, Ian H .; Neal, Radford M .; Cleary, John G. (červen 1987). „Aritmetické kódování pro kompresi dat“ (PDF) . Komunikace ACM . 30 (6): 520–540. doi : 10.1145 / 214762.214771 . Archivováno (PDF) z originálu 28. září 2007 . Vyvolány 21 September 2007 .

• Rodionov Anatoly, Volkov Sergey (2010) „p-adic arithmetic coding“ Contemporary Mathematics Volume 508, 2010 Contemporary Mathematics
• Rodionov Anatoly, Volkov Sergey (2007) „p-adic arithmetic coding“, https://arxiv.org/abs//0704.0834v1

externí odkazy

•  Tento článek obsahuje public domain materiál  z  dokumentu NIST :  Black, Paul E. „aritmetické kódování“ . Slovník algoritmů a datových struktur .
• Zveřejňování v diskusních skupinách s krátkým příkladem aritmetického kódování (pouze celé číslo).
• Článek PlanetMath o aritmetickém kódování
• Anatomie Range Encoder Článek vysvětluje rozsahové i aritmetické kódování. Má také ukázky kódu pro 3 různé aritmetické kodéry spolu s porovnáním výkonu.
• Úvod do aritmetického kódování . 60 stran.
• Eric Bodden, Malte Clasen a Joachim Kneis: Arithmetic Coding odhaleni . Technická zpráva 2007-5, Sable Research Group, McGill University.
• Aritmetické kódování + statistické modelování = komprese dat od Marka Nelsona.
• Komprese dat s aritmetickým kódováním , Mark Nelson (2014)
• Rychlá implementace kódování dosahu a rANS od Jamese K. Bonfielda