Arithmetic Coding
算術符号はメッセージ全体を [0,1) 区間内の一つの実数に写像し、有限精度で表現し、圧縮率が情報源エントロピーに任意に近づく。
目的
符号確率分布が既知の場合、Huffman より高い圧縮率を達成する（某符号確率が 1 に近い場合に特に顕著）。
メカニズム
区間 [0,1) から始め、各記号ごとに現在の区間を記号確率に比例する小区間へ分割し、その記号に対応する小区間を選択する。出力は最終区間内の任意の数の二進表現である。有限精度実装ではアンダーフローを避けるため、正規化を伴う整数区間を用いる。
ユースケース
- JPEG 2000 エントロピー符号
- PPM バックエンド
- 高圧縮率テキスト圧縮