> aritmetisk kodning | brøkbits | optimal <
// Aritmetisk kodning - kodning med brøkbits tæt på entropigrænsen
Næsten optimal
Nærmer sig den teoretiske entropigrænse for komprimeringseffektivitet.
Brøkbits
Koder symboler med brøkdele af bits baseret på sandsynlighed.
Streaming
Kan kode og dekode data løbende, efterhånden som de ankommer.
>> tekniske detaljer
Sådan fungerer aritmetisk kodning:
Aritmetisk kodning repræsenterer en hel besked som ét tal i intervallet [0,1). Hvert symbol indsnævrer intervallet baseret på dets sandsynlighed. Det endelige interval kodes som en binær brøk og giver komprimering meget tæt på entropigrænsen.
Kodningsforløb:
Tekst: "AAB" Sandsynligheder: A=0.67, B=0.33 1. Start: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) Output: Et vilkårligt tal i [0.30, 0.45) Binær: 0.010011...
Hvorfor bruge aritmetisk kodning:
- >Bedste komprimeringsforhold
- >Nærmer sig entropigrænsen
- >Håndterer vilkårlige sandsynligheder
- >Bruges i JPEG2000/H.264
- >Patenter udløbet (2024)
>> ofte stillede spørgsmål
Hvad er aritmetisk kodning?
Aritmetisk kodning er en form for entropikodning, der omdanner en sekvens af symboler til ét brøktal. I modsætning til Huffman-kodning, som bruger hele bits, kan aritmetisk kodning bruge brøkbits pr. symbol.
Hvorfor er den bedre end Huffman?
Aritmetisk kodning kan opnå komprimering vilkårligt tæt på entropigrænsen, mens Huffman er begrænset til hele bits pr. symbol. Ved stærkt skæve sandsynligheder kan aritmetisk kodning være markant bedre.
Hvad er præcisions-parameteren?
Præcision styrer antallet af bits, der bruges til interne beregninger. Højere præcision gør det muligt at kode længere beskeder, men kræver mere hukommelse. 16 bit er normalt nok til korte tekster.
Hvor bruges aritmetisk kodning?
Aritmetisk kodning bruges i moderne komprimeringsstandarder som H.264/H.265-video, JPEG2000-billeder og ZIPs DEFLATE64. Den var tidligere dækket af patenter, men de vigtigste er udløbet.
// Gennemregnet eksempel
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// Kodeeksempler
Model P(A)=0.5 P(B)=0.25 P(C)=0.25 -> A:[0,0.5) B:[0.5,0.75) C:[0.75,1)
Update width = high - low
high = low + width * cum_high(symbol)
low = low + width * cum_low(symbol)
Output any value in [0.34375, 0.375) e.g. 0.34375 = 0.01011b (5 bits = 1 + 2 + 2)
Entropy -log2 P(A) - log2 P(B) - log2 P(C) = 1 + 2 + 2 = 5 bits
>> Flere spørgsmål
S: Hvorfor er aritmetisk kodning ofte bedre end Huffman?
S: Huffman giver hvert symbol et helt antal bit (mindst 1). Aritmetisk kodning koder hele beskeden som ét enkelt brøktal i [0, 1) og nærmer sig entropien, også for symboler med sandsynlighed over 50 %, som alligevel koster 1 bit i Huffman.
S: Hvordan virker intervaleksemplet ABC?
S: Med A=0,5, B=0,25, C=0,25 indsnævres intervallet for hvert symbol: [0,1) → [0,0,5) → [0,25, 0,375) → [0,34375, 0,375). Ethvert tal heri, fx 0,34375 = 0,01011 binært, koder “ABC” med 5 bit, præcis entropien.
S: Hvor bruges aritmetisk kodning?
S: I CABAC (H.264/HEVC), MQ-koderen i JPEG 2000 og JBIG2 samt varianter som range coding (AV1) og ANS (zstd, JPEG XL). Tidlige patenter bremsede udbredelsen; i dag er de fleste udløbet.