> arithmetische Kodierung | Bruchteilsbits | optimal <
// Arithmetische Kodierung – Bit-kodierung mit Bruchteilen nahe der Entropiegrenze
Nahezu optimal
Erreicht Kompressionsraten sehr nah am theoretischen Entropielimit.
Bruchteilsbits
Kodiert Symbole mit Bruchteilen von Bits basierend auf ihrer Wahrscheinlichkeit.
Streaming-fähig
Kann Daten schrittweise kodieren und dekodieren, während sie eintreffen.
>> Technische Infos
Wie arithmetische Kodierung funktioniert:
Arithmetische Kodierung stellt eine gesamte Nachricht als eine einzige Zahl im Intervall [0,1) dar. Jedes Symbol verengt dieses Intervall entsprechend seiner Wahrscheinlichkeit. Das Endintervall wird als binärer Bruch kodiert und ermöglicht eine Kompression sehr nah am Entropielimit.
Kodierablauf:
Text: "AAB" Wahrscheinlichkeiten: 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) Ausgabe: Jede Zahl in [0.30, 0.45) Binär: 0.010011...
Warum arithmetische Kodierung verwenden?:
- >Beste Kompressionsraten
- >Nähert sich dem Entropielimit
- >Unterstützt beliebige Wahrscheinlichkeiten
- >Wird in JPEG2000/H.264 eingesetzt
- >Patente abgelaufen (2024)
>> Häufig gestellte Fragen
Was ist arithmetische Kodierung?
Arithmetische Kodierung ist eine Form der Entropiekodierung, die eine Folge von Symbolen in eine einzige Bruchzahl umwandelt. Im Gegensatz zur Huffman-Kodierung, die ganze Bits verwendet, kann arithmetische Kodierung Bruchteilsbits pro Symbol nutzen.
Warum ist sie besser als Huffman?
Arithmetische Kodierung kann eine Kompression erreichen, die beliebig nahe an das Entropielimit herankommt, während Huffman auf ganze Bits pro Symbol beschränkt ist. Bei stark schiefen Wahrscheinlichkeitsverteilungen kann arithmetische Kodierung deutlich besser sein.
Was ist der Präzisionsparameter?
Die Präzision steuert die Anzahl der Bits, die für interne Berechnungen verwendet werden. Höhere Präzision erlaubt das Kodieren längerer Nachrichten, erfordert aber mehr Speicher. 16 Bit sind für kurze Texte meist ausreichend.
Wo wird arithmetische Kodierung eingesetzt?
Arithmetische Kodierung wird in modernen Kompressionsstandards wie H.264/H.265-Video, JPEG2000-Bildern und ZIPs DEFLATE64 verwendet. Früher war sie patentgeschützt, aber die wichtigsten Patente sind abgelaufen.
// Durchgerechnetes Beispiel
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// Codebeispiele
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
>> Weitere Fragen
F: Warum ist arithmetische Kodierung oft besser als Huffman?
A: Huffman weist jedem Symbol eine ganze Zahl von Bits zu (mindestens 1). Die arithmetische Kodierung kodiert die ganze Nachricht als einen einzigen Bruch in [0, 1) und kommt damit nahe an die Entropie, auch bei Symbolen mit Wahrscheinlichkeit über 50 %, die bei Huffman trotzdem 1 Bit kosten.
F: Wie funktioniert das Intervall-Beispiel ABC?
A: Mit A=0,5, B=0,25, C=0,25 wird das Intervall pro Symbol verengt: [0,1) → [0,0,5) → [0,25, 0,375) → [0,34375, 0,375). Jede Zahl darin, etwa 0,34375 = 0,01011 binär, kodiert „ABC“ mit 5 Bit, genau der Entropie.
F: Wo wird arithmetische Kodierung eingesetzt?
A: In CABAC bei H.264/HEVC, im MQ-Coder von JPEG 2000 und JBIG2 sowie in Varianten wie Range Coding (AV1) und ANS (zstd, JPEG XL). Frühe Patente bremsten die Verbreitung, heute sind sie weitgehend abgelaufen.