ゴロム符号化

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

ライス符号化（ロバート・F・ライスによって考案）とは、ゴロム符号のサブセットを用いて、より単純な（ただし最適ではない可能性のある）接頭符号を生成することを指します。ライスはこの符号セットを適応符号化方式で使用しました。「ライス符号化」とは、その適応符号化方式、あるいはゴロム符号のサブセットの使用のいずれを指す場合もあります。ゴロム符号は任意の正の整数値をとることができる調整可能なパラメータを持ちますが、ライス符号は調整可能なパラメータが2のべき乗である符号です。これにより、ライス符号はコンピュータでの使用に便利になります。なぜなら、2による乗算と除算は、2進演算でより効率的に実装できるからです。

ライス氏がこのより単純な部分集合を提案した動機は、幾何分布は時間とともに変化したり、正確には分かっていなかったり、あるいはその両方である場合が多く、そのため一見最適に見えるコードを選択してもあまり有利ではない可能性があるという事実に基づいていた。

ライス符号化は、多くの可逆画像圧縮および音声データ圧縮方式において、エントロピー符号化段階として使用される。

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

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

デコード:

1. qの単項表現をデコードする（コードの先頭にある1の数を数える）
2. 0区切り文字をスキップする
3. させて${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
   1. 次のbビットをバイナリ数r'として解釈します。${\displaystyle r'<2^{b+1}-M}$保持すると、残りは${\displaystyle r=r'}$
   2. それ以外の場合は、b + 1ビットをバイナリ数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を使用した Rice–Golomb エンコーディングでは、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の最適な設定は、最も近い整数です。${\displaystyle -{\frac {1}{\log _{2}p}}}$p = 1/2の場合、 M = 1 となり、ゴロム符号は単項符号 ( n ≥ 0 P ′ s の後にQが続く場合、n 個の1 の後に 1が続くものとして符号化される) に対応します。より単純な符号が必要な場合は、ゴロム・ライス パラメータb (すなわち、ゴロム パラメータ)を割り当てることができます。${\displaystyle M=2^{b}}$) に最も近い整数に${\displaystyle -\log _{2}(-\log _{2}p)}$常に最適なパラメータとは限らないものの、通常は最適なライスパラメータであり、その圧縮性能は最適なゴロム符号に非常に近い。（ライス自身は、どの符号が最適かを判断するために、同じデータに対してさまざまな符号を使用することを提案した。後にJPLの研究者が、符号パラメータを最適化または推定するためのさまざまな方法を提案した。^{[ 3 ]}）

Pが確率pを持つシーケンスをランレングス符号化するために、bビットのバイナリ部分を持つライスコードを使用することを検討します。${\displaystyle \mathbb {P} [{\text{ビットは}}k{\text{-run}}の一部である}]}$ビットがkビット連続の一部となる確率(${\displaystyle k-1}$P s と 1 つのQ ) および${\displaystyle ({\text{k-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エンコーダは、RLGR は、最後にエンコードされたシンボルに応じて Golomb–Rice パラメータを上下に調整する非常にシンプルなアルゴリズムを使用してこれを実現します。デコーダは同じルールに従ってエンコード パラメータの変動を追跡できるため、付加情報を送信する必要はなく、エンコードされたデータのみを送信すれば済みます。マルチメディア コーデックの予測誤差や変換係数など、データに見られる幅広い統計量をカバーする一般化ガウス PDF を仮定すると、RLGR エンコード アルゴリズムはこのようなアプリケーションで非常に優れた性能を発揮します。

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

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

ゴロム・ライス符号化器は、ライスアルゴリズムに基づく可逆画像コーデックのエントロピー符号化段階で使用されます。そのような実験の一例として、図に示す圧縮率グラフがあります。

JPEG -LS方式は、予測残差を符号化するためにライス・ゴロム法を使用する。

上記で述べたRLGR適応型ゴロム・ライス符号化これは、Microsoft Remote Desktop ProtocolのRemoteFXコンポーネントにおいて、仮想マシン内の画面コンテンツをエンコードするために使用されます。また、最近制定されたG-PCC MPEG規格ISO/IEC 23090-9においても、点群属性の圧縮に使用されています。

• エリアスデルタコーディング
• 可変長コード
• 指数ゴロム符号化

• ゴロンブ、ソロモン 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 . Bibcode : 1971ITCoT..19..889R . doi : 10.1109/TCOM.1971.1090789 .
• Robert F. Rice (1979)、「いくつかの実用的な汎用ノイズレス符号化技術」、ジェット推進研究所、カリフォルニア州パサデナ、JPL出版物79-22、1979年3月。
• ウィッテン、イアン・モファット、アリスター・ベル、ティモシー。「ギガバイトの管理：文書と画像の圧縮とインデックス作成」第2版。モーガン・カウフマン出版、サンフランシスコ、カリフォルニア州。1999年 ISBN 1-55860-570-3
• デビッド・サロモン著「データ圧縮」、ISBN 0-387-95045-1。
• HS Malvar、「未知の統計を持つ量子化された一般化ガウス源の適応型ランレングス/ゴロム-ライス符号化」、データ圧縮会議議事録、2006年。
• RLGRエントロピー符号化、Microsoft MS-RDPRFXオープン仕様、リモートデスクトッププロトコル用RemoteFXコーデック。
• S. Büttcher、CLA Clarke、GV Cormack。『情報検索：検索エンジンの実装と評価』Wayback Machineに2020年10月5日にアーカイブ済み。MIT Press、マサチューセッツ州ケンブリッジ、2010年。