Aritmetisk koding

Den aritmetiske kodingen er en form for entropikoding som i den tapsfrie datakomprimeringen blir brukt og oppnår kompresjonshastigheter som ligger veldig nær den teoretiske grensen til entropien . Jorma Rissanen anses å være grunnleggeren av aritmetisk koding. Fra 1976 til begynnelsen av 1980-tallet utførte han betydelig arbeid med denne grenen av informasjonsteori .

Konvensjonelle kodinger er basert på representasjonen av informasjonen med et fast antall heltallbiter, for eksempel i ASCII-kode med 7 biter, eller ofte brukte tegn lagres med færre biter og sjeldnere tegn lagres med flere biter, som i den Huffman-koding er tilfelle. Den aritmetiske kodingen skiller seg fra dette i det vesentlige punktet at kildeinformasjonen ikke er delt inn i individuelle komponenter, men hele kildeinformasjonen eller en lengre del av den er representert som et rasjonelt tall . Kartleggingen er vanligvis i form av en vilkårlig presis brøk q bestående av to naturlige tall med intervallgrensene 0,0 ≤ q <1,0. Det er også variasjoner av den aritmetiske kodingen for en kortere beregningstid, som bare bruker et enkelt naturlig tall av en hvilken som helst lengde for å representere informasjon. Generelt er aritmetisk koding mer beregningsintensiv enn konvensjonelle metoder som danner kodeord med et antall heltallbiter.

Grunnleggende prinsipp

Fremgangsmåten fungerer teoretisk med uendelig presise reelle tall , selv om de faktiske implementeringene da må falle tilbake på endelig presise heltall , fast punkt eller flytende tall . Dette betyr imidlertid alltid at avrunding må utføres, og resultatet er ikke lenger optimalt.

Inngangene for den aritmetiske koderen er referert til nedenfor som et symbol . Utgangen til koderen er et reelt tall (her betegnet med x ).

Først må koderen og dekoderen avtale et intervall der tallet x skal være plassert. Vanligvis brukes området mellom 0 og 1 (eksklusiv) her, dvs. det halvåpne intervallet (se). ${\ displaystyle [0,1) = \ {x \ in \ mathbb {R} \, | \, 0 \ leq x <1 \}}$

I tillegg, når koding eller koding av et tegn, må kodere og dekodere alltid ha identiske tabeller tilgjengelig med sannsynligheten for alle mulige dekoderbare tegn. Modellen er ansvarlig for å gi disse sannsynlighetene .

En mulighet er å lage en frekvensanalyse spesielt for inngangsdata før koding og å kommunisere dette til dekoderen i tillegg til den faktiske meldingen. Kodere og dekodere bruker deretter denne tabellen for alle tegn.

Koder

1. Initialiser gjeldende intervall med avtalt startintervall - som nevnt ovenfor, er dette vanligvis intervallet .${\ displaystyle [0,1)}$
2. Fordel det aktuelt intervall inn i underintervaller Størrelsen på delintervallene bestemmes av hyppigheten av karakteren ( sannsynlighet for forekomst ). Intervallenes rekkefølge bestemmes av en avtale (f.eks. I alfabetisk rekkefølge).
3. Underintervallet som tilsvarer neste tegn i oppføringen blir det gjeldende intervallet .
4. Hvis det fortsatt er flere tegn som skal kodes, fortsett med punkt 2. Ellers fortsett med neste punkt.
5. Skriv ut et hvilket som helst tall fra gjeldende intervall pluss antall kodede tegn. Dette er tallet x som kan dekodes av dekoderen som beskrevet ovenfor. Dette tallet er valgt på en slik måte at det har så få desimaler som mulig, dvs. er så "rund" som mulig og kan derfor representeres med relativt få biter .

Dekoder

Dekoderen kan nå dekode ett tegn om gangen ved å gjøre følgende:

1. Initialiser gjeldende intervall med avtalt intervall - vanligvis intervallet .${\ displaystyle [0,1)}$
2. Del gjeldende intervall i underintervaller på samme måte som koderen, og tildel et tegn til hvert underintervall (se ovenfor).
3. Finn ut i hvilket av disse underintervallene tallet x ligger, og skriv ut tegnet som er tilordnet dette underintervallet. I tillegg blir dette underintervallet nå det nåværende intervallet .
4. Hvis det fortsatt er flere tegn å dekode, fortsett med punkt 2 med det nye nåværende intervallet .

Det merkes med denne algoritmen at den ikke avsluttes : Antallet x alene forteller ikke når det siste tegnet ble dekodet. Dekoderen må derfor alltid informeres om tilleggsinformasjon når den er ferdig med arbeidet. Dette implementeres vanligvis i form av en lengdespesifikasjon, men det kan også (for eksempel hvis bare et enkelt datapass kreves for koding) ved hjelp av et spesialtegn med betydningen "slutt".

Intervall divisjon

Underintervallene må velges slik at koderen og dekoderen bestemmer størrelsen og posisjonen likt. Som nevnt ovenfor, er størrelsen på underintervallene resultatet av tegnene.

Rekkefølgen (sekvensen) av intervallene har derimot ingen betydning for kvaliteten på algoritmen, slik at en hvilken som helst sekvens kan spesifiseres her. Dette er gjenstand for en avtale (f.eks. Alfabetisk rekkefølge).

En måte å beregne intervallene på er som følger:

${\ displaystyle {\ begin {align} I_ {l} (n + 1) & = I_ {l} (n) + I_ {s} L \\ I_ {h} (n + 1) & = I_ {l} (n) + I_ {s} H \ end {align}}}$

${\ displaystyle I_ {l}}$og er grensene for intervallet. er lengden på intervallet, så . De to verdiene og er summen av sannsynlighetene for alle tegn med en indeks mindre enn eller lik tegnet som skal kodes . ${\ displaystyle I_ {h}}$${\ displaystyle I_ {s}}$${\ displaystyle I_ {h} -I_ {l}}$${\ displaystyle L}$${\ displaystyle H}$${\ displaystyle x}$

${\ displaystyle {\ begin {align} L & = \ sum p (i), i <x \\ H & = \ sum p (i), i \ leq x \ end {align}}}$

Hvis det for eksempel brukes et alfabet A = {A, B, C}, hvor sannsynligheten er p (A) = 0,75, p (B) = 0,125, p (C) = 0,125 og neste tegn x som skal kodes er C, så vil og beregnet som følger: ${\ displaystyle L}$${\ displaystyle H}$

${\ displaystyle {\ begin {align} L & = p (A) + p (B) = 0,875 \\ H & = p (A) + p (B) + p (C) = 1 \ end {align}}}$

eksempel

I dette eksemplet er strengen "AAABAAAC" komprimert. For det første kreves frekvensene til alle tegn for størrelsen på delintervallene. For enkelhets skyld brukes en statisk sannsynlighet for alle tegn.

karakter	Frekvens	sannsynlighet	optimalt antall biter
EN.	Sjette	p (A) = 75%	${\ displaystyle I (A) = - \ log _ {2} (A) = - \ log _ {2} (0 {,} 75) = 0 {,} 415}$
B.	1	P (B) = 12,5%	${\ displaystyle I (B) = - \ log _ {2} (B) = - \ log _ {2} (0 {,} 125) = 3}$
C.	1	P (C) = 12,5%	${\ displaystyle I (C) = - \ log _ {2} (C) = - \ log _ {2} (0 {,} 125) = 3}$

Det optimale antall biter er resultatet av formelen for entropien . Med denne verdien kan det beregnes at informasjonsinnholdet i tegnstrengen tilsvarer 8,49 bits.

${\ displaystyle I _ {\ text {ges}} = \ sum _ {i = 1} ^ {3} n_ {i} \ cdot I ({z_ {i}}) = 6 * 0 {,} 415 + 1 * 3 + 1 * 3 = 8 {,} 49}$

Nå til prosessen. Tabellen nedenfor viser de nøyaktige verdiene for delintervallene etter koding av de enkelte tegnene. Grafikken til høyre illustrerer valget av delintervallene igjen.

	intervall		Intervallstørrelse
	0 -	1	1
EN.	0 -	0,75	0,75
EN.	0 -	0,5625	0,5625
EN.	0 -	0,421875	0,421875
B.	0,31640625 -	0,369140625	0,052734375
EN.	0,31640625 -	0,35595703125	0,03955078125
EN.	0,31640625 -	0,3460693359375	0,0296630859375
EN.	0,31640625 -	0.338653564453125	0,022247314453125
C.	0,335872650146484375 -	0.338653564453125	0,002780914306640625

Ethvert tall fra det siste intervallet som er så kort som mulig lagres, f.eks. B. 0,336.

Dette tilsvarer mellom 8 og 9 bits. De Huffman-koding , på den annen side, ville ha krevet 10 bits for den gitte strengen (en for hver A og 2 hver for B og C)

Forskjellen i dette eksemplet er 10%. Fortjenesten øker når antall biter som faktisk brukes av Huffman-koding, avviker mer fra det optimale, dvs. når et tegn forekommer ekstremt ofte.

Dekoderen tar dette nummeret for å dekode. Følgende finner sted:

• Det starter med startintervallet [0; 1]. Dette intervallet er delt inn i tre underintervaller av dekoderen (som i første linje på bildet).
• 0,336 ligger i delintervallet A [0; 0,75]. Så den første karakteren er A.
• Gjeldende delintervall er [0; 0,75]
• [0; 0,75] brytes ned igjen i henhold til det kjente opplegget
• 0,336 er igjen i det første intervallet [0; 0.5625], dvs. utgang A.
• [0; 0.5625] brytes ned igjen i henhold til det kjente opplegget
• 0,336 er igjen i det første intervallet [0; 0.421875], dvs. utgang A.
• [0; 0.421875] brytes ned igjen i henhold til det kjente opplegget
• Denne gangen er 0,336 i det andre intervallet [0,31640625; 0.369140625], så B vil skrive ut.
• [0,31640625; 0.369140625] brytes ned igjen i henhold til den kjente ordningen
• ...

Optimalitet

Aritmetisk koding er asymptotisk optimal:

Etter at det siste symbolet er behandlet, får du et intervall med ${\ displaystyle [r, r + s)}$

${\ displaystyle s = \ prod _ {i = 1} ^ {N} p (x_ {i})}$

Dette tilsvarer sannsynligheten for å motta nøyaktig en slik sekvens for gitte symbolsannsynligheter . ${\ displaystyle p (x_ {i})}$

For å spesifisere en binær verdi i intervallet , trenger man ${\ displaystyle [r, r + s)}$

• i det minste biter, hvis${\ displaystyle - \ lceil \ log _ {2} (s) \ rceil = - \ log _ {2} (s)}$${\ displaystyle \ eksisterer \; x = 0 \ mod 2 ^ {- \ lceil \ log _ {2} (s) \ rceil}, x \ i [r, r + s)}$
• på det meste imidlertid biter (for å beskrive intervallet med en nøyaktighet på s / 2, som i det binære systemet er akkurat nok til å skille om verdien er innenfor).${\ displaystyle - \ lceil \ log _ {2} (s) \ rceil +1}$

Der

${\ displaystyle {\ begin {align} - \ log _ {2} (s) & = - \ log _ {2} {\ big (} \ prod _ {i = 1} ^ {N} p (x_ {i }) {\ big)} \\ & = - \ sum _ {i = 1} ^ {N} \ log _ {2} p (x_ {i}) \\ & =: n \ cdot H (X) \ slutt {justert}}}$

og

${\ displaystyle - \ lceil \ log _ {2} (s) \ rceil +1 <- \ log _ {2} (s) +2}$

vi kan estimere lengden på den aritmetisk kodede sekvensen: ${\ displaystyle l}$

${\ displaystyle n \ cdot H (X) \ leq l <n \ cdot H (X) +2}$

Dette betyr at du trenger minst like mange biter som entropien , men ikke mer enn to biter mer.

Gjennomsnittlig lengde på et kodet symbol er begrenset til ${\ displaystyle l_ {Sym} = {\ frac {l} {n}}}$

${\ displaystyle H (X) \ leq l_ {Sym} <H (X) + {\ frac {2} {n}}}$

For lange sekvenser fordeles disse (høyst to) tilleggsbitene jevnt over alle symboler, slik at den gjennomsnittlige lengden på et kodet symbol deretter går asymptotisk mot den sanne entropien:

${\ displaystyle \ lim _ {n \ to \ infty} {\ Big (} H (X) + {\ frac {2} {n}} {\ Big)} = H (X)}$

Sammenlignet med Huffman-koding

Hvis alle symbolsannsynligheter kan være representert i formen , produserer aritmetisk koding og Huffman-koding en identisk lang datastrøm og er like (dvs. optimalt) effektive. I praksis er dette imidlertid nesten aldri tilfelle. ${\ displaystyle p_ {i}}$${\ displaystyle p_ {i} = 2 ^ {- k_ {i}}, k_ {i} \ in \ mathbb {N ^ {+}}}$

gjennomføring

Siden man ikke kan jobbe med uendelig presise reelle tall i en konkret implementering , må den konkrete implementeringen av algoritmen gjøres noe annerledes. Den maksimale presisjonen til tallene er vanligvis fast (f.eks. 32 bits) og kan ikke overstige denne verdien. Dette er grunnen til at en aritmetisk koder ikke kan implementeres på en ekte datamaskin.

For å omgå problemet med begrenset nøyaktighet tas to trinn:

1. Stedene etter den øvre nøyaktighetsgrensen er avskåret. Som et resultat samsvarer ikke intervallstørrelsene nøyaktig med de nødvendige verdiene. Dette fører til en forverring av resultatet.
2. Intervallet må økes fra tid til annen, ellers vil nøyaktigheten til tallene bli brukt etter noen kodede tegn. Derfor vises høyere tall som er faste og fjernes fra tallene. I eksemplet ovenfor, etter koding av tegnet B, kan du trygt si at resultatnummeret starter med 0,3. Så du kan allerede sende ut 0,3 her og trekke den fra intervallgrensene. Intervallgrensen skaleres deretter med 10, og beregningen fortsetter med denne verdien.

Punkt 1 betyr faktisk at algoritmen ikke lenger er en aritmetisk koder, men bare lik. Det er imidlertid noen uavhengige algoritmer som kommer fra den aritmetiske koderen; disse er:

Den rekkevidde koderen

Denne koderen er en relativt grei implementering av den aritmetiske koderen med heltall .

Den Q-Coder ( utviklet og patentert av IBM )

Dette forenkler også alfabetet til bare to tegn. Denne prosedyren gjør at intervallinndelingen kan tilnærmes med tillegg i stedet for multiplikasjoner som med områdekoderen.

Den ELS koder

Dette fungerer også bare med to tegn, men er mer effektivt med tegn som er relativt like sannsynlige, mens med Q-koderen skal begge tegn ha så forskjellige sannsynligheter som mulig.

Til tross for disse metodene forblir forskjellige problemer med aritmetisk koding:

hastighet

Aritmetiske kodere er relativt dyre og sakte. Med områdekoderen må det utføres en inndeling for hvert tegn . De andre koderne krever at kodingsprosessen utføres flere ganger for alle biter av tegnet.

Patenter

De fleste av programvarepatentene innen aritmetisk koding ble gitt på 1980- og begynnelsen av 1990-tallet og er nå utløpt. Q-koderen er tillatt sammen med Huffman-koderen for JPEG , men brukes nesten aldri fordi den ble patentert av IBM.

Lite overskudd

Ulike metoder kan brukes for å sikre at den mye raskere Huffman-kodingen bare gir marginalt dårligere resultater enn den komplekse aritmetiske koderen. Dette inkluderer at noen ganger strenger behandles som uavhengige tegn. Dette reduserer "avfallet" som oppstår fra det faktum at hvert tegn er representert med en heltallbitlengde.

weblenker

• Utdyping om grunnleggende aritmetisk koding, inkludert kildetekst (E. Bodden et al. 2002; PDF-fil; 568 kB)
• Q-koderside fra IBM
• Nettsted for områdekoder, kildekode for nedlasting
• Beskrivelse av algoritmen til områdekoderen i pseudokode
• Kapittel 6 i den elektroniske boka Information Theory, Inference, and Learning Algorithms av David JC MacKay forklarer aritmetisk koding.

Individuelle bevis

1. ↑ Jorma Rissanen: Generalisert Kraft-ulikhet og aritmetisk koding. Red.: IBM Journal of Research and Development. Nei. 20 . IBM (selskapspublikasjon), 1976, s. 198-203 . 
2. ↑ Khalid Sayood: Introduksjon til datakomprimering . Morgan Kaufmann, 2000, ISBN 978-1-55860-558-9 , kapittel 4: Arithmetic Coding . 
3. ^ Strutz: bildedatakomprimering. SpringerVieweg, 2009
4. ↑ Guy E. Blelloch, Introduksjon til Data Compression (PDF; 408 kB), p 18, 2010.
5. ↑ Amir Said, Introduction to Arithmetic Coding - Theory and Practice (PDF; 462 kB), s.13
6. ↑ E. Bodden et al., Utdyping om grunnleggende aritmetisk koding, inkludert kildetekst (PDF; 581 kB), 2002, s.41