ゴロム符号化

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

ライスコーディング

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

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

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

概要

コードの構築

ゴロム符号化は、調整可能なパラメータ $M$ を用いて入力値 $x を$ 2つの部分に分割します。q $は$ $M$ による除算の結果、 $r$ は剰余です。商は単項符号化で送信され、続いて剰余は切り捨て2進符号化で送信されます。の場合、ゴロム符号化は単項符号化と等価です。 $M=1$

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

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

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

そして

$r=x-qM.$

$この図は、 1 -$ $p$ $(0) \geq 0.45に対して$ $M$ が最適に選択された場合のゴロム符号の冗長性（ビット単位）を示しています。

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

ゴロムが扱った整数 $xは、0から始まる$ 幾何分布に従うベルヌーイ過程のランレングスである。パラメータ $M$ の最適な選択は、対応するベルヌーイ過程の関数であり、これは与えられたベルヌーイ試行における成功確率によってパラメータ化される。M $は$ 分布の中央値か、中央値±1のいずれかである。これは以下の不等式によって決定され、次のように解かれる。 $p=P(x=0)$ $(1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},$ $M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil .$

$p (0) = 0.2$ の例では、 $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番目の負の値 (つまり) はn^番目の奇数 ( )にマッピングされ、m^{番目の正の値は}m番目の偶数 ( )にマッピングされます。これは数学的に次のように表現できます: 正の値 $x$ は ( ) にマッピングされ、負の値 $y$ は ( ) にマッピングされます。このようなコードは、最適ではなくても、簡潔さのために使用できます。両側幾何分布の真に最適なコードには、分布パラメータに応じて、このコードを含むゴロムコードの複数のバリエーションが含まれます。^[²^] $-n$ $2n-1$ $2m$ $x'=2|x|=2x,\ x\geq 0$ $y'=2|y|-1=-2y-1,\ y<0$

シンプルなアルゴリズム

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

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

デコード:

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

例

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

商部分のエンコード
$q$	出力ビット
0	0
1	10
2	110
3	1110
4	11110
5	111110
6	1111110
$\vdots$	$\vdots$
北	$\underbrace {111\cdots 111} _{N}0$

剰余部分のエンコード
$r$	オフセット	バイナリ	出力ビット
0	0	0000	000
1	1	0001	001
2	2	0010	010
3	3	0011	011
4	4	0100	100
5	5	0101	101
6	12	1100	1100
7	13	1101	1101
8	14	1110	1110
9	15	1111	1111

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

確率Pが $p$ であるシーケンスをランレングス符号化するために、 $b$ ビットの2進部分を持つライス符号を用いることを考えてみよう。あるビットが $k$ ビットのラン（Pと1つのQ）の一部となる確率をとし、そのランの圧縮率をとすると、期待される圧縮率は $\mathbb {P} [{\text{ビットはk{\text{-run}}の一部です}}]$ $k-1$ $({\text{k{\text{-run}} の圧縮率)$ ${\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}}$

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

適応型ランレングスゴロム・ライス符号化

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

PDFが不明、または変化する整数データを効率的に符号化する別の方法として、後方適応型エンコーダを用いる方法があります。RLGRエンコーダ[1]は、最後に符号化されたシンボルに応じてゴロム・ライスパラメータを上下に調整する非常に単純なアルゴリズムを用いてこれを実現します。デコーダも同じ規則に従って符号化パラメータの変化を追跡できるため、付加情報は不要で、符号化データのみを送信すれば済みます。マルチメディアコーデックにおける予測誤差や変換係数など、データに見られる幅広い統計量をカバーする一般化ガウスPDFを仮定すると、RLGR符号化アルゴリズムはこのようなアプリケーションにおいて非常に優れた性能を発揮します。

アプリケーション

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

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

ゴロム・ライス符号化器は、ライスアルゴリズムに基づくロスレス画像コーデックのエントロピー符号化段階で使用されます。このような実験の1つから、図に示す圧縮率のグラフが得られます。

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

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

参照

参考文献

^ Gallager, RG; van Voorhis, DC (1975). 「幾何学的に分布した整数アルファベットの最適ソースコード」. IEEE Transactions on Information Theory . 21 (2): 228– 230. doi : 10.1109/tit.1975.1055357 .
^ Merhav, N.; Seroussi, G.; Weinberger, MJ (2000). 「両側幾何分布と未知のパラメータを持つ情報源の符号化」. IEEE Transactions on Information Theory . 46 (1): 229– 236. Bibcode : 2000ITIT...46..229M . doi : 10.1109/18.817520 .
^ Kiely, A. (2004).ライスコーディングにおけるゴロムパラメータの選択（技術レポート）.ジェット推進研究所. 42-159.
^ “man shorten” . 2014年1月30日時点のオリジナルよりアーカイブ。2008年12月7日閲覧。
^ 「FLAC - フォーマットの概要」 . xiph.org .

さらに読む

ゴロム、ソロモン W. (1966).ランレングス符号化. IEEE Transactions on Information Theory, IT--12(3):399--401
ライス, ロバート F.; プラウント, 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、「未知の統計量を持つ量子化一般化ガウス情報源の適応型ランレングス/ゴロム・ライス符号化」、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年。

[1] Gallager, RG; van Voorhis, DC (1975). 「幾何学的に分布した整数アルファベットの最適ソースコード」. IEEE Transactions on Information Theory . 21 (2): 228– 230. doi : 10.1109/tit.1975.1055357 .

[2] Merhav, N.; Seroussi, G.; Weinberger, MJ (2000). 「両側幾何分布と未知のパラメータを持つ情報源の符号化」. IEEE Transactions on Information Theory . 46 (1): 229– 236. Bibcode : 2000ITIT...46..229M . doi : 10.1109/18.817520 .

[3] Kiely, A. (2004).ライスコーディングにおけるゴロムパラメータの選択（技術レポート）.ジェット推進研究所. 42-159.

[4] “man shorten” . 2014年1月30日時点のオリジナルよりアーカイブ。2008年12月7日閲覧。

[5] 「FLAC - フォーマットの概要」 . xiph.org .

[

[

[

[

[