Elias Delta Code
Elias デルタ符号は、ガンマ符号の長さ部にガンマ符号化をもう一度適用したもので、大きな整数に対してガンマよりコンパクトになる。万能前置符号である。
目的
値の範囲が広い場合にガンマ符号より効率的に整数を符号化し、符号長は log2(n)+2*log2(log2(n))+O(1) となる。
メカニズム
k = floor(log2(n)) とすると、gamma(k) に続けて n の下位 k ビットを出力する。長さ自体も可変長で符号化されるため、大きな整数のオーバーヘッドが減る。
ユースケース
- 広範囲な整数の可変長コーディング
- ユニバーサル圧縮
- 情報理論のチュートリアル