> golomb | 最適 | 圧縮 <
// Golomb 符号化 - 柔軟な除数で整数を最適圧縮
>> 特長
柔軟な除数
任意の M 値を選択して圧縮効率を最大化できます。
途中打ち切りバイナリ
余りを符号化するために必要なビット数を最小限に抑えます。
汎用用途
任意の非負整数分布に対して機能します。
>> 技術情報
Golomb 符号化のしくみ
Golomb 符号化では、各整数 n を除数 M で割り、商 q と余り r を得ます。商はユニタリ符号で、余りは途中打ち切りバイナリで符号化され、M 個の値を表現するのに必要なビット数を最小化します。これにより、パラメータ p = 1/M を持つ幾何分布に対する最適な符号が得られます。
Golomb 符号化の例 (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (r<3 に 2 ビット) 1 → q=0, r=1 → 0|01 → 001 (r<3 に 2 ビット) 2 → q=0, r=2 → 0|10 → 010 (r<3 に 2 ビット) 3 → q=0, r=3 → 0|110 → 0110 (r≥3 に 3 ビット) 4 → q=0, r=4 → 0|111 → 0111 (r≥3 に 3 ビット) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 途中打ち切りバイナリ: r<3 には 2 ビット、r≥3 には 3 ビットを使用
Golomb 符号化を使う理由
- 幾何分布に対して最適
- 柔軟な M パラメータ
- 最小限のビット使用量
- 実装が簡単
- 最適性が理論的に証明されている
>> よくある質問
Golomb 符号化とは何ですか？
Golomb 符号化は、幾何分布のための最適なプレフィックスフリー可変長コードです。調整可能なパラメータ M で整数を割り、商をユニタリ符号、余りを途中打ち切りバイナリで表現することで、P(n) = (1-p)^n × p に従うデータを最適に圧縮します。
M パラメータはどのように選べばよいですか？
最適な M はデータの幾何パラメータ p に依存します。平均値 μ を持つデータの場合、おおよそ M ≈ μ + 1 とできます。パラメータ p を持つ指数関数的に減衰する確率では、最適な M は M = ⌈-1/log₂(1-p)⌉ となります。解析機能を使って、データに最も適した M を見つけてください.
途中打ち切りバイナリとは何ですか？
途中打ち切りバイナリは、M 個の可能な値のうち 1 つを符号化するときに必要なビット数を最小化する方法です。M が 2 のべき乗であれば通常のバイナリを使います。それ以外の場合、いくつかの値は ⌊log₂M⌋ ビット、残りはいくつかは ⌈log₂M⌉ ビットを使い、最小平均長で一意に復号できるようにします。
Golomb 符号化はどこで使われていますか？
Golomb 符号化は JPEG-LS 画像圧縮、H.264 動画符号化 (Exp-Golomb として)、およびロスレス音声フォーマットで使用されています。ランレングス符号化、予測後の残差符号化、幾何分布や指数分布に従うあらゆるデータに最適です。