> arithmetic | fractional | optimal <
// Arithmetic Coding - Fractional bit encoding approaching entropy limit
Near-Optimal
Approaches theoretical entropy limit for compression efficiency.
Fractional Bits
Encodes symbols using fractional bits based on probability.
Streamable
Can encode and decode data incrementally as it arrives.
>> technical info
How Arithmetic Coding Works:
Arithmetic coding represents an entire message as a single number in the interval [0,1). Each symbol narrows this interval based on its probability. The final interval is encoded as a binary fraction, achieving compression very close to the entropy limit.
Encoding Process:
Text: "AAB" Probabilities: 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: Any number in [0.30, 0.45) Binary: 0.010011...
Why Use Arithmetic Coding:
- >Best compression ratios
- >Approaches entropy limit
- >Handles any probability
- >Used in JPEG2000/H.264
- >Patent-expired (2024)
>> frequently asked questions
What is arithmetic coding?
Arithmetic coding is a form of entropy encoding that converts a sequence of symbols into a single fractional number. Unlike Huffman coding which uses whole bits, arithmetic coding can use fractional bits per symbol.
Why is it better than Huffman?
Arithmetic coding can achieve compression arbitrarily close to the entropy limit, while Huffman is limited to whole bits per symbol. For highly skewed probabilities, arithmetic coding can be significantly better.
What's the precision parameter?
Precision controls the number of bits used for internal calculations. Higher precision allows encoding longer messages but requires more memory. 16-bit is usually sufficient for short texts.
Where is arithmetic coding used?
Arithmetic coding is used in modern compression standards like H.264/H.265 video, JPEG2000 images, and ZIP's DEFLATE64. It was previously patent-encumbered but key patents expired.
算术编码（Arithmetic Coding）怎么理解？手算示例
算术编码的核心想法：把整个消息编码为 [0, 1) 区间内的一个分数。每个符号按其概率缩小区间，最终输出一个落在最终区间内的二进制分数即可。
示例：编码 AAB，概率 A=0.67, B=0.33。
• 初始区间：[0.00, 1.00)，分成 A 占 [0.00, 0.67)、B 占 [0.67, 1.00)。
• 读 A：区间缩至 [0.00, 0.67)。
• 再次分：A 占前 67% [0.00, 0.4489)，B 占后 33% [0.4489, 0.67)。
• 读 A：区间缩至 [0.00, 0.4489)。
• 再次分：A 占前 67%，B 占后 33%。具体为 A=[0, 0.3008)、B=[0.3008, 0.4489)。
• 读 B：区间缩至 [0.3008, 0.4489)。
• 任取区间内的数（比如 0.40）作为编码。
解码时用同样的概率表反向拆分区间，即可恢复 A, A, B。
关键优势：不同符号能用 分数位。如果 A 的概率是 0.9，那 log2(1/0.9) ≈ 0.152 bit——算术编码真的只用 0.15 bit 编码一个 A，而 Huffman 最少也要用 1 bit。这就是为什么它在极度偏斜的分布上比 Huffman 好得多。
算术编码 vs Huffman vs Range Coding — 该选哪个？
| 算法 | 压缩率 | 速度 | 复杂度 |
|---|---|---|---|
| Huffman | 非最优（整数位） | 极快 | 简单 |
| 算术编码 | 近最优（分数位） | 较慢（乘除） | 中等 |
| Range Coding | 与算术编码等价 | 更快 | 中等 |
| ANS / rANS | 与算术编码等价 | 最快 | 较难 |
选择建议：
• 实时压缩 / 嵌入式：Huffman。
• 概率偏斜大，对压缩率敏感：算术编码（2024 年后基础专利全部失效）。
• 现代高性能（AV1、Zstandard 的熵阶段）：ANS（Asymmetric Numeral Systems）。
• 2020 年后的新格式基本都用 ANS 家族（tANS / rANS），因为它同时提供算术编码的压缩率和 Huffman 的速度。
Codage arithmétique — quelle différence avec le codage de Huffman ?
Le codage arithmétique atteint la limite d'entropie de Shannon en utilisant des bits fractionnaires, tandis que Huffman est limité à des bits entiers par symbole.
Exemple concret : soit un alphabet avec A (p=0.9), B (p=0.1). Entropie de Shannon ≈ 0.469 bit/symbole.
• Huffman ne peut pas faire mieux qu'un bit par symbole (il attribue A=0, B=1). Efficacité : 100% / 0.469 = 213% (mauvais).
• Arithmétique s'approche de 0.469 bit/symbole sur de longues séquences. Quand A apparaît 900 fois sur 1000 symboles, il code ces 1000 symboles en ~469 bits au lieu de 1000.
Usages modernes :
• H.264 / H.265 (CABAC) : Context-Adaptive Binary Arithmetic Coding, cœur des codecs vidéo.
• JPEG 2000 : MQ coder (variante binaire du codage arithmétique).
• bzip2 : utilise Huffman (plus simple et libre de brevets à l'époque), pas arithmétique.
Les brevets fondamentaux d'IBM sur le codage arithmétique adaptatif ont expiré au début des années 2000, ce qui a débloqué son adoption dans H.264 et suivants.