ゴロム符号

ゴロム符号：効率的な整数符号化手法

ゴロム符号は、南カリフォルニア大学のソロモン・ゴロムによって開発された、整数を符号化する手法です。この符号化方式は、幾何分布に従って出現する整数データに対して最適な符号長を実現することで知られています。そのため、データの出現頻度が幾何分布に近い場合、高い圧縮率が期待できます。

ライス符号との関係

ゴロム符号と密接に関連する符号化手法として、ライス符号があります。ライス符号は、ゴロム符号の特別な場合と見なすことができ、計算量が少なく高速な符号化・復号が可能なため、実用上はライス符号（ゴロム・ライス符号とも呼ばれる）が広く利用されています。ただし、ゴロム符号の方がより広い範囲のデータに対応できる柔軟性を持っています。圧縮率は、データの分布が幾何分布の場合、ハフマン符号と同等となり、それ以外の場合はハフマン符号より劣ることが知られています。

符号化の原理

ゴロム符号は、正の整数値m（パラメータ）を用いて符号化を行います。符号化対象の整数x（0以上の整数）に対して、以下の手順で符号化します。

1. 商と余りの計算: x を m で割ったときの商をq、余りをrとします。
2. 商の符号化: 商qは、unary符号を用いて符号化されます。Unary符号とは、qの値を1の系列で表す符号化方式です。例えば、q=3ならば「1110」のように表現されます。
3. 余りの符号化: 余りrの符号化方法は、mの値によって異なります。
mが2のべき乗（2^k）の場合: rをkビットの2進数で表現します。
mが2のべき乗でない場合: b = ⌈log₂m⌉ （mを超えない最小の2のべき乗のビット数）とします。r < 2^b - m ならば、rをb-1ビットの2進数で表現し、そうでない場合は r + 2^b - m をbビットの2進数で表現します。

m = 1 の場合は、ゴロム符号はUnary符号と等価になります。また、mが2のべき乗の場合、ライス符号と等価になります。ゴロム符号の原論文では、商のUnary符号において、通常とは0と1が反転した表現を用いている点が、一般的なUnary符号との違いです。

符号化の例

m = 3 の場合を例に考えてみましょう。このとき、b = 2、2^b - m = 1 となります。

r = 0 の場合: 1ビット（「0」）で符号化
r = 1 の場合: 2ビット（「10」）で符号化
r = 2 の場合: 2ビット（「11」）で符号化

例えば、x = 5 の場合、q = 1、r = 2 となり、「1011」と符号化されます。

応用

ゴロム符号は、整数データの圧縮に広く利用されています。特に、画像、音声、動画データの圧縮において、予測符号化の一部として用いられることが多く、予測値との残差（予測誤差）をエントロピー符号化するために活用されます。具体的には、以下の技術などで活用されています。

画像: JPEG-LS、LOCO-I、FELICS、SFALIC
音声: FLAC
動画: H.264

まとめ

ゴロム符号は、幾何分布に従うデータに対して高い圧縮効率を示す、強力な整数符号化手法です。その特殊なケースであるライス符号は、計算量の少なさから、様々なデータ圧縮技術に広く用いられています。本記事で解説した原理と応用事例を理解することで、データ圧縮技術の更なる理解に繋がるでしょう。

もう一度検索