Golomb-Rice符号
Golomb符号のmが2冪の場合を特にライス符号という
たとえば32bitまでの整数のサブセットが与えられて、これを表現したいとする
もしそのほとんどが小さい数で、大きい数は稀にかつ疎にしか出現しない場合、32bitよりも小さいbitで数を表現できそうな気がするでしょう？
たとえば、ほとんどが1桁の数字で、2桁以上の数は123456789しか現れないと分かって入れば、10を123456789に読み換えることで、どの数もたった4bitで表現できることになる
あるいは、「大きい数では32bit以上必要になるが、小さい数では少しのbitで表現できる」符号化を考えれば、分布次第で総合的に軽量化される
そういうモチベーションです
ゴロム符号は幾何分布する整数の符号化に最適化された符号化形式
非負整数を対象とする単純な符号化で、正整数nと「n個の0の後に1が出現する」符号とを対応させる
たとえば0は1、1は01、3は0001、10は00000000001
パラメータkを与える
整数pを q = n / 2^kとr = n % 2^kに分ける
qをunary符号化、rをkビット固定長数として表現したものがライス符号
2冪にするために2^kとしたが、これを2冪に限定しないものがゴロム符号
ソート済み整数列を圧縮するアルゴリズムで、空間効率が理論値に近いらしい