ゴロムコーディング

ゴロム符号化は、 1960年代にソロモン・W・ゴロムによって発明されたデータ圧縮コードファミリーを使用したロスレスデータ圧縮方式です。幾何分布に従うアルファベットは、最適なプレフィックスコードとしてゴロム符号を持ちます^[1]。そのため、ゴロム符号化は、入力ストリーム内で小さな値が発生する可能性が大きな値が発生する可能性よりも大幅に高い状況に非常に適しています。

ライス コーディング(ロバート F. ライスが発明) は、ゴロム コードのファミリーのサブセットを使用して、より単純な (ただし、おそらく最適ではない) プレフィックス コードを生成することを意味します。ライスは、このコード セットを適応コーディングスキームで使用しました。「ライス コーディング」は、その適応スキームまたはゴロム コードのサブセットの使用のいずれかを指します。ゴロム コードの調整可能なパラメータは任意の正の整数値にすることができますが、ライス コードは、調整可能なパラメータが 2 の累乗であるコードです。これにより、2 による乗算と除算をバイナリ演算でより効率的に実装できるため、ライス コードはコンピューターで使用するのに便利です。

ライスがこのより単純なサブセットを提案した理由は、幾何分布は時間とともに変化することが多く、正確には分かっていないか、またはその両方であるため、一見最適と思われるコードを選択してもあまり有利ではない可能性があるからです。

ライス符号化は、多くのロスレス画像圧縮およびオーディオデータ圧縮方式におけるエントロピー符号化段階として使用されます。

ゴロム符号化では、調整可能なパラメータM を使用して、入力値x を2 つの部分に分割します。qはMによる除算の結果、rは剰余です。商は単項符号化で送信され、その後に剰余が切り捨てられたバイナリ符号化で送信されます。 の場合、ゴロム符号化は単項符号化と同等です。 ${\displaystyle M=1}$

ゴロム・ライス符号は、ビンの位置( q ) とビン内のオフセット( r )によって数値を示す符号と考えることができます。例の図は、ゴロム・ライスパラメータM = 3を使用し、ソース確率がp (0) = 0.2の幾何分布に従う整数xをエンコードするための位置qとオフセットr を示しています。

正式には、2 つの部分は次の式で表されます。ここで、xはエンコードされる非負の整数です。

${\displaystyle q=\left\lfloor {\frac {x}{M}}\right\rfloor }$

そして

${\displaystyle r=x-qM}$。

qとr は両方とも可変ビット数を使用してエンコードされます。qは単項コードでエンコードされ、r はライス コードの場合はbビットでエンコードされ、ゴロム コードの場合はbビットとb +1ビットのいずれかでエンコードされます (つまり、M は2 の累乗ではありません) 。 の場合、 bビットを使用してrをエンコードします。それ以外の場合は、b +1 ビットを使用して r をエンコードします。明らかに、M が2 の累乗であれば、 rのすべての値をbビットでエンコードできます。 ${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$${\displaystyle r<2^{b+1}-M}$${\displaystyle b=\log _{2}(M)}$

ゴロムが扱った整数x は、0 から始まる幾何分布を持つベルヌーイ過程の実行長でした。パラメータMの最適な選択は、対応するベルヌーイ過程の関数であり、特定のベルヌーイ試行での成功確率によってパラメータ化されます。Mは分布の中央値または中央値 ±1 のいずれかです。これは、次の不等式によって決定できます。 ${\displaystyle p=P(x=0)}$

${\displaystyle (1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},}$

これらは次のように解決される

${\displaystyle M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil }$。

p (0) = 0.2の例では次のようになります。

${\displaystyle M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3}$。

この分布のゴロム コードは、ソース値の無限セットのハフマン コードを計算できる場合、同じ確率の ハフマン コードと同等になります。

ゴロムの方式は、非負数のシーケンスをエンコードするために設計されました。ただし、オーバーラップとインターリーブ方式を使用して、負の数を含むシーケンスを受け入れるように簡単に拡張できます。オーバーラップとインターリーブ方式では、すべての値が一意かつ可逆的な方法で何らかの正の数に再割り当てされます。シーケンスは、0、-1、1、-2、2、-3、3、-4、4、... で始まります。n番目の負の値 (つまり、)は${\displaystyle -n}$n^番目の奇数 ( )に${\displaystyle 2n-1}$マッピングされ、m^{番目の正の値は}m番目${\displaystyle 2m}$の偶数 ( )にマッピングされます。これは、数学的には次のように表現できます。正の値xは ( ) にマッピングされ、負の値y は( ) にマッピングされます。このようなコードは、最適ではない場合でも、簡潔さのために使用できます。両側幾何分布の真に最適なコードには、分布パラメータに応じて、このコードを含むゴロム コードの複数のバリエーションが含まれます。^[2]${\displaystyle x'=2|x|=2x,\ x\geq 0}$${\displaystyle y'=2|y|-1=-2y-1,\ y<0}$

以下は、ライス・ゴロム符号化です。剰余コードは、ライス符号化とも呼ばれる単純な切り捨てバイナリ符号化を使用します (剰余コードの統計分布が平坦でない場合、特に除算後のすべての可能な剰余が使用されていない場合は、算術符号化やハフマン符号化などの他の可変長バイナリ符号化が剰余コードに使用できます)。このアルゴリズムでは、Mパラメータが 2 の累乗である場合、より単純なライス符号化と同等になります。

1. パラメータM を整数値に固定します。
2. エンコードする数値 Nについて、
   1. 商 = q = floor( N / M )
   2. 剰余 = r = N を法としてM
3. コードワードを生成する
   1. コード形式: <商コード><剰余コード>、ここで
   2. 商コード（単項コーディング）
      1. 1ビット（または0ビット）の長さqの文字列を書き込む
      2. 0ビット（それぞれ1ビット）を書き込む
   3. 剰余コード（切り捨てバイナリエンコード）
      1. させて${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
         1. bビットを使用してr をバイナリ表現でコード化する場合。${\displaystyle r<2^{b+1}-M}$
         2. b + 1 ビットを使用して数値をバイナリ表現でコード化します。${\displaystyle r\geq 2^{b+1}-M}$${\displaystyle r+2^{b+1}-M}$

デコード:

1. qの単項表現をデコードします(コードの先頭の 1 の数を数えます)
2. 0区切り文字をスキップする
3. させて${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
   1. 次のbビットを2進数r'として解釈する。成立する場合、余りは${\displaystyle r'<2^{b+1}-M}$${\displaystyle r=r'}$
   2. それ以外の場合は、 b + 1ビットを2進数r'として解釈し、剰余は次のように表される。${\displaystyle r=r'-2^{b+1}+M}$
4. 計算${\displaystyle N=q*M+r}$

M = 10と設定します。したがって、カットオフは です。 ${\displaystyle b=\lfloor \log _{2}(10)\rfloor =3}$${\displaystyle 2^{b+1}-M=16-10=6}$

たとえば、パラメータM = 10を使用するライス・ゴロム符号化では、10 進数 42 はまずq = 4 とr = 2 に分割され、qcode( q ),rcode( r ) = qcode(4),rcode(2) = 11110,010として符号化されます(出力ストリームで区切りのコンマを符号化する必要はありません。q コードの末尾の 0 でqが終了してr が始まることがわかるからです。qcode と rcode はどちらも自己区切型です)。

このセクションでは、 pと1 – p の使用法が、前のセクションの使用法とは逆になっていることに注意してください。

2 つの記号のアルファベット、または確率がそれぞれpと ( 1 − p ) である 2 つのイベントのセットPとQ が与えられた場合( p ≥ 1/2 )、ゴロム符号化を使用して、単一のQ ′ で区切られた 0 個以上のP ′の連続を符号化できます。このアプリケーションでは、パラメータMの最適な設定は に最も近い整数です。p = 1/2 の場合、M = 1 となり、ゴロム符号は単項 ( n ≥ 0 のP ′ の後にQが続く場合は、 n個の 1 の後に 0 が続くものとして符号化されます) に対応します。より単純なコードが必要な場合は、ゴロム–ライス パラメータb (つまり、ゴロム パラメータ) を に最も近い整数に割り当てることができます。これは常に最適なパラメータとは限りませんが、通常は最適なライス パラメータであり、圧縮パフォーマンスは最適なゴロム符号に非常に近くなります。 （ライス自身は、同じデータに対してさまざまなコードを使用してどれが最適かを判断することを提案しました。その後、JPLの研究者がコードパラメータを最適化または推定するさまざまな方法を提案しました。^[3]） ${\displaystyle -{\frac {1}{\log _{2}p}}}$ ${\displaystyle M=2^{b}}$${\displaystyle -\log _{2}(-\log _{2}p)}$

確率Pがpであるシーケンスをランレングスエンコードするために、bビットのバイナリ部分を持つライスコードを使用することを考えてみます。 がビットがkビットのラン（P sと1つのQ ）の一部になる確率であり、 がそのランの圧縮率である場合、期待される圧縮率は ${\displaystyle \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]}$${\displaystyle k-1}$ ${\displaystyle ({\text{compression ratio of }}k{\text{-run}})}$

${\displaystyle {\begin{aligned}\mathbb {E} [{\text{compression ratio}}]&=\sum _{k=1}^{\infty }({\text{compression ratio of }}k{\text{-run}})\cdot \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}}$

圧縮は、圧縮された割合で表されることが多い。 の場合、ランレングス符号化アプローチでは、エントロピーに近い圧縮率が得られる。たとえば、 のライスコードを使用すると、${\displaystyle 1-\mathbb {E} [{\text{compression ratio}}]}$${\displaystyle p\approx 1}$${\displaystyle b=6}$${\displaystyle p=0.99}$91.89%の圧縮率である一方、エントロピーの限界は91.92% .

整数の確率分布が不明な場合、ゴロム・ライス エンコーダの最適なパラメータを決定することはできません。そのため、多くのアプリケーションでは、2 パス アプローチが使用されます。まず、データ ブロックをスキャンして、データの確率密度関数 (PDF) を推定します。次に、推定された PDF からゴロム・ライス パラメータを決定します。このアプローチのより単純なバリエーションは、PDF がパラメータ化されたファミリに属していると仮定し、データから PDF パラメータを推定し、最適なゴロム・ライス パラメータを計算することです。これは、以下で説明するほとんどのアプリケーションで使用されるアプローチです。

PDF が不明または変化する整数データを効率的にエンコードする別の方法は、後方適応エンコーダを使用することです。RLGR エンコーダ [1] は、最後にエンコードされたシンボルに応じて Golomb–Rice パラメータを上下に調整する非常に単純なアルゴリズムを使用してこれを実現します。デコーダは同じルールに従ってエンコード パラメータの変化を追跡できるため、サイド インフォメーションは送信する必要はなく、エンコードされたデータのみを送信すればよいことになります。マルチメディア コーデックの予測誤差や変換係数などのデータに見られる幅広い統計をカバーする一般化ガウス PDF を想定すると、RLGR エンコード アルゴリズムはこのようなアプリケーションで非常に優れたパフォーマンスを発揮します。

多くの信号コーデックは、予測残差にライス コードを使用します。予測アルゴリズムでは、このような残差は両側幾何分布に当てはまる傾向があり、小さな残差は大きな残差よりも頻繁に発生します。ライス コードは、ハフマン テーブルを転送しなければならないというオーバーヘッドなしで、このような分布のハフマン コードに近似します。幾何分布に一致しない信号の 1 つに正弦波があります。これは、差分残差が正弦波信号を作成し、その値が幾何分布を作成しないためです (最高残差値と最低残差値は同様に高い発生頻度を持ち、正の残差と負の残差の中央値のみ発生頻度が低くなります)。

Shorten、^[4] FLAC、^[5] Apple Lossless、MPEG-4 ALSなどのいくつかのロスレスオーディオコーデックは、線形予測ステップの後にライスコードを使用します（Apple Losslessでは「適応型FIRフィルタ」と呼ばれます）。ライスコーディングは、FELICSロスレス画像コーデックでも使用されています。

Golomb-Rice コーダは、Rice アルゴリズム ベースのロスレス画像コーデックのエントロピー コーディング ステージで使用されます。このような実験の 1 つで、図に示す圧縮率のグラフが生成されます。

JPEG -LS方式では、ライス・ゴロム法を使用して予測残差をエンコードします。

前述のゴロム・ライス符号化の適応型バージョンであるRLGRエンコーダ[2]は、MicrosoftリモートデスクトッププロトコルのRemoteFXコンポーネントの仮想マシンの画面コンテンツをエンコードするために使用されます。

• エリアスデルタコーディング
• 可変長コード

• ゴロム、ソロモン W. (1966)。ランレングス符号化。IEEE Transactions on Information Theory、IT--12(3):399--401
• Rice, Robert F.; Plaunt, R. (1971). 「宇宙船テレビデータの効率的な圧縮のための適応型可変長コーディング」IEEE Transactions on Communications . 16 (9): 889–897. doi :10.1109/TCOM.1971.1090789.
• Robert F. Rice (1979)、「いくつかの実用的なユニバーサルノイズレスコーディングテクニック」、ジェット推進研究所、カリフォルニア州パサデナ、JPL 出版物 79—22、1979 年 3 月。
• ウィッテン、イアン・モファット、アリスター・ベル、ティモシー。「ギガバイトの管理: 文書と画像の圧縮とインデックス作成」第 2 版。Morgan Kaufmann Publishers、サンフランシスコ、カリフォルニア州。1999 年 ISBN 1-55860-570-3 
• David Salomon、「データ圧縮」、ISBN 0-387-95045-1。 
• HS Malvar、「未知の統計を持つ量子化された一般化ガウス情報源の適応型ランレングス/ゴロム・ライス符号化」、Proc. Data Compression Conference、2006 年。
• RLGR エントロピー エンコーディング、Microsoft MS-RDPRFX オープン仕様、リモート デスクトップ プロトコル用の RemoteFX コーデック。
• S. Büttcher、CLA Clarke、GV Cormack。情報検索：検索エンジンの実装と評価。Wayback Machineに2020年10月5日にアーカイブ。MIT Press、マサチューセッツ州ケンブリッジ、2010年。