ゴロム符号(ゴロムふごう、Golomb coding)とは、南カリフォルニア大学のソロモン・ゴロムによって開発された、幾何分布に従って出現する整数を最適に符号化することのできる整数の符号化手法である。ゴロム符号と類似の手法にライス符号があるが、ゴロム符号の特別な場合がライス符号になるため、ライス符号のことをゴロム・ライス符号(Golomb-Rice coding)と呼称することが多い。特にライス符号は符号化・復号の計算量が少ないことが特徴。圧縮率は幾何分布の時はハフマン符号と同一で、それ以外ではそれよりも悪い。 符号化のパラメータとして、1 以上の整数値 m を用いる。 m > 1 のとき、符号化対象とする整数値 x(≧0) に対して、x を m で割った商を q 余りを r とする。 m = 1 のときは、unary符号に等しくなる。また、m が 2 の冪であるとき( m = 2 k {\displaystyle m=2^{k}} )は、ライス符号に等しくなる。 本質的な差はないが、ゴロム符号の原論文では、商の符号化で、通常の unary 符号とは 0 と 1 を反転させている。 m = 3 とする。このとき b = 2, 2 b − m = 1 {\displaystyle 2^{b}-m=1} である。よって、 r = 0 を 1 ビットで、r = 1, 2 を r + 2 b − m {\displaystyle r+2^{b}-m} とした上で2ビットで符号化する。 m = 3 の場合数値(x)商(q)剰余(r)商の符号剰余の符号符号(全体) その他の符号化の例xm = 4m = 5m = 8 x = 255, m = 8 なら、00000000000000000000000000000001111 となる。 整数値の符号化として用いられるほか、画像(動画・静止画)や音声の圧縮で用いられる予測符号化の一部として、予測値との残差をエントロピー符号するのに利用される。
符号化の原理
商 q をunary符号を用いて符号化する。
余り r は log 2 m {\displaystyle \log _{2}m} に従って、次のように符号化する。
log 2 m {\displaystyle \log _{2}m} が整数値である。すなわち、m が 2 の冪であるならば、r を log 2 m {\displaystyle \log _{2}m} ビットのバイナリ符号で符号化する。
それ以外の場合、 b = ⌈ log 2 m ⌉ {\displaystyle b=\lceil \log _{2}m\rceil } としたとき
r < 2 b − m {\displaystyle r<2^{b}-m} なら、b - 1 ビットで r をバイナリ符号化
それ以外は、 r + 2 b − m {\displaystyle r+2^{b}-m} を b ビットのバイナリ符号化
符号化の例
000000000
101010010
202011011
31010001000
41110101010
51210111011
6201100011000
7211101011010
01001001000
11011011001
21101101010
311111101011
4010011111100
5010101001101
6011001011110
7011101101111
8001000111001000
9001010111101001
10001100010001010
11001110010101011
120001000011001100
応用
画像 - JPEG-LS, LOCO-I, FELICS
音声 - FLAC
動画 - H.264
関連項目
データ圧縮
整数の符号化
外部リンク
Golomb, S.W. (1966). ⇒, Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
R. F. Rice (1971) and R. Plaunt, , "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data, " IEEE Transactions on Communications, vol. 16(9), pp. 889?897, Dec. 1971.
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・ ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" 。";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" - ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、 ";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" / ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:") ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}
表示
編集
エントロピー符号
一進法
算術
Asymmetric numeral systems(英語版)
ゴロム
ハフマン
適応型(英語版)
正準(英語版)
MH
レンジ
シャノン
シャノン・ファノ
シャノン・ファノ・イライアス(英語版)
タンストール(英語版)
ユニバーサル(英語版)
指数ゴロム(英語版)
フィボナッチ(英語版)
ガンマ
レーベンシュタイン(英語版)
辞書式(英語版)
BPE
Deflate
Lempel-Ziv
LZ77
LZ78
LZFSE
LZH
LZJB(英語版)
LZMA
LZO
LZRW(英語版)
LZS(英語版)
LZSS
LZW
LZWL(英語版)
LZX
LZ4
ROLZ(英語版)
統計型(英語版)
Brotli
Snappy
Zstandard
その他
BWT
CTW(英語版)
Delta
DMC(英語版)
MTF
PAQ
PPM
RLE
音声