レンジ符号

レンジ符号：高速で効率的なデータ圧縮技術

レンジ符号（range encoding）は、データ圧縮において広く用いられるエントロピー符号化方式の一種です。1979年、G. Nigel N. Martinによって定義され、Richard Clark Pascoによる算術符号の概念を基に発展しました。シンボルとその確率に基づき、効率的なビットストリームに変換するエンコーダと、その逆変換を行うデコーダから構成されます。

レンジ符号は算術符号と非常に類似していますが、重要な違いは符号化処理においてビットではなく、任意の基数の数字を使用する点にあります。これにより、バイト単位での処理が可能となり、圧縮効率をわずかに犠牲にすることで、処理速度の大幅な向上が実現されます。

特に、レンジ符号は特許の制約を受けないため、オープンソースソフトウェアでの利用が盛んです。1998年のMichael Schindlerによる発表や、1999年のDmitry Subbotinによる「ロシア人民のレンジコーダ」の発表などによって、注目を集めてきました。

レンジ符号の仕組み

レンジ符号は、ハフマン符号のように各シンボルに固有のビットパターンを割り当てるのではなく、メッセージ全体のシンボルを一つの数値として表現します。そのため、ハフマン符号よりも高い圧縮率を実現し、確率が2の累乗でない場合にも効率的な符号化が可能です。

その核心は、与えられた整数範囲とシンボルの確率分布に基づき、初期範囲を確率に比例した部分範囲に分割することです。メッセージの各シンボルは、現在の範囲を対応する部分範囲に縮小することで順次符号化されます。復号器は、エンコーダと同じ確率分布を用いて、逆の処理を行います。この確率分布は、事前に送るか、圧縮データから導出するか、圧縮器・復号器に組み込まれます。

すべてのシンボルが符号化されると、部分範囲を特定することでメッセージ全体を復元できます。この部分範囲は、整数で表すことができ、必ずしも整数全体を送信する必要はありません。部分範囲を識別するのに必要な先頭の数字列のみを送信すれば良いのです。

例：メッセージの符号化

例として、「AABA 」というメッセージを符号化してみましょう。はメッセージの終了を示す記号です。復号器は、確率分布{A: 0.60, B: 0.20, : 0.20}と、基数10（範囲[0, 100000)）を使用すると仮定します。

エンコーダは、初期範囲[0, 100000)を確率に応じて3つの部分範囲に分割します。

A: [0, 60000)
B: [60000, 80000)
* : [80000, 100000)

最初のシンボルAにより、範囲は[0, 60000)に縮小されます。以下、同様にシンボルを符号化していきます。この過程で、範囲は徐々に狭まっていきます。最終的に得られた範囲[25056, 25920)から、元のメッセージを復元できる接頭辞（例：「251」）が得られます。

実際の実装では、基数10ではなく、二進数（バイト単位）を使用します。これにより、処理速度が向上します。復号化も同様の手順で行われます。

算術符号との関係

算術符号とレンジ符号は非常に類似しており、本質的には同じ符号化方法の異なる解釈です。算術符号は分数を用いるのに対し、レンジ符号は整数を用いますが、どちらも確率に基づいた範囲の縮小を用いて符号化を行います。そのため、算術符号器はレンジコーダとして、レンジコーダは算術符号器として機能します。

まとめ

レンジ符号は、算術符号と比較して高速な処理が可能なデータ圧縮技術です。特許の制約がなく、オープンソースコミュニティでも広く利用されており、様々な圧縮アプリケーションに適用されています。その効率性と柔軟性から、今後もデータ圧縮技術として重要な役割を果たし続けるでしょう。

もう一度検索