ユニバーサルコード（データ圧縮）

データ圧縮において、整数用のユニバーサル コードは、正の整数を 2 進コードワードにマッピングするプレフィックス コードであり、整数の真の確率分布が何であれ、分布が単調である限り (つまり、すべての正のiに対してp ( i ) ≥  p ( i  + 1) である限り)、コードワードの期待される長さは、その確率分布の最適コードが割り当てる期待される長さの定数倍以内になるという追加の特性があります。ユニバーサル コードは、実際の期待される長さと最適な期待される長さの比率がコードの情報エントロピーの関数によって制限される場合に漸近的に最適です。この関数は、制限されていることに加えて、エントロピーが無限大に近づくにつれて 1 に近づきます。

一般に、整数のプレフィックス コードのほとんどは、大きい整数に長いコードワードを割り当てます。このようなコードを使用すると、メッセージのセットを確率の降順で並べ、目的のメッセージのインデックスを送信するだけで、可能なメッセージのセットから抽出したメッセージを効率的に通信できます。ユニバーサル コードは、一般に、正確にわかっている確率分布には使用されず、実際に使用される分布に最適なユニバーサル コードはありません。

ユニバーサル コードは、ユニバーサル ソース コーディングと混同しないでください。ユニバーサル ソース コーディングでは、データ圧縮方法が固定プレフィックス コードである必要はなく、実際の予測長さと最適な予測長さの比率が 1 に近づく必要があります。ただし、漸近的に最適なユニバーサル コードは、ユニバーサル ソース コーディングの方法として、徐々に大きくなるブロックを使用することで、独立した同一に分散されたソースで使用できることに注意してください。

これらは整数のユニバーサルコードです。アスタリスク( * )は辞書順に簡単に言い換えられるコードを示し、二重ダガー( ‡ )は漸近的に最適なコードを示します。

• エリアスガンマコーディング*
• エリアスデルタコーディング*‡
• エリアスオメガコーディング* ^{[さらなる説明が必要]} ‡
• Exp-Golomb コーディング*。Elias ガンマ コーディングを特殊なケースとして持ちます。( H.264/MPEG-4 AVCで使用)
• フィボナッチコーディング
• レーベンシュタイン符号化*‡、オリジナルのユニバーサル符号化技術[1]
• バイト コーディングでは、特別なビット パターン (少なくとも 2 ビット) を使用してコードの終わりを示します。たとえば、整数が、より自然な16 進数ではなく15 進数の数字を表すニブルのシーケンスとしてエンコードされている場合、最も高いニブル値 (つまり、2 進数で 4 つの 1 のシーケンス) を使用して整数の終わりを示すことができます。
• 可変長数量

これらは非普遍的なものです:

• エリアス符号で使用される単項符号化
• ライスコーディングはFLAC オーディオコーデックで使用され、単項コーディングを特別なケースとして持つ。
• ゴロム符号化。ライス符号化と単項符号化を特殊なケースとして持ちます。

これらの非普遍性は、これらのいずれかをパラメータs=2のガウス・クズミン分布またはゼータ分布の符号化に使用した場合、期待される符号語長が無限大になることに気づくことで観察できます。たとえば、ゼータ分布に単項符号化を使用すると、期待される長さは次のようになります。

${\displaystyle E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty 。 \,}$

一方、ガウス・クズミン分布にユニバーサル・エリアス・ガンマ符号化を使用すると、エントロピー（約 3.43 ビット）に近い予想されるコードワード長（約 3.51 ビット）が得られます - Академия Google。

ハフマン符号化と算術符号化（使用可能な場合）は、少なくともどの汎用コードよりも優れた圧縮率を実現します。

ただし、ユニバーサル コードは、ハフマン コーディングを使用できない場合に役立ちます。たとえば、各メッセージの正確な確率はわからないが、確率の順位のみがわかっている場合などです。

ユニバーサル コードは、ハフマン コードが不便な場合にも役立ちます。たとえば、送信側はメッセージの確率を知っているが、受信側は知らない場合、ハフマン コーディングでは、それらの確率を受信側に送信するオーバーヘッドが必要になります。ユニバーサル コードを使用すると、そのオーバーヘッドは発生しません。

各ユニバーサル コードには、他の自己区切り (プレフィックス) バイナリ コードと同様に、P ( i )=2 ^{− l ( i )}で示される独自の「暗黙の確率分布」があります。ここで、l ( i )はi番目のコードワードの長さ、P ( i ) は対応するシンボルの確率です。実際のメッセージ確率がQ ( i ) で、Kullback-Leibler ダイバージェンスが l ( i )のコードによって最小化される場合、そのメッセージ セットの最適なハフマン コードは、そのコードと同等になります。同様に、コードが最適にどれだけ近いかは、このダイバージェンスによって測定できます。ユニバーサル コードは、ハフマン コード (ハフマン コードも算術エンコードよりも単純で高速) よりもエンコードとデコードが簡単で高速であるため、が十分に小さい 場合はユニバーサル コードの方が適しています。ロスレス データ圧縮プログラム: ハイブリッド LZ77 RLE${\displaystyle D_{\text{KL}}(Q\|P)}$${\displaystyle D_{\text{KL}}(Q\|P)}$

任意の幾何分布（整数の指数分布）に対して、ゴロムコードが最適です。ユニバーサルコードの場合、暗黙の分布は、 （より正確にはジップ分布）などのべき乗法則に近似します。フィボナッチコードの場合、暗黙の分布は、近似的にで、 ${\displaystyle 1/n^{2}}$${\displaystyle 1/n^{q}}$

${\displaystyle q=1/\log _{2}(\varphi )\simeq 1.44,}$

ここで、 は黄金比です。3 進コンマ コード(つまり、シンボルごとに 2 ビットで表される基数 3 のエンコード) の場合、暗黙の分布は のべき乗法則になります。したがって、これらの分布には、それぞれのべき乗法則を持つほぼ最適なコードがあります。 ${\displaystyle \varphi}$${\displaystyle q=1+\log _{3}(4/3)\simeq 1.26}$

• データ圧縮、Debra A. Lelewer および Daniel S. Hirschberg (カリフォルニア大学アーバイン校)
• David MacKay著の『Information Theory, Inference, and Learning Algorithms』には、Elias コードの紹介を含む整数のコードに関する章があります。
• Кодирование целых чисел には、ユニバーサル コードやその他の整数コードに関する英語の論文がほとんどです。