gamma符号
gamma符号について解説。
先日unary符号というものを紹介した。
これはElias符号というP.Elias氏の考案した符号化方式の一種。Elias氏は複数の符号化方式を考案していて、自然数に関するものだとunary符号の他に、gamma符号、delta符号、omega符号がある。これらの符号もunary符号と同様、小さな数値ほど短いbit列で表現しようというもの。
じゃあunary符号でいいじゃんと思われるかもしれないが、unary符号は単純な反面、数値の増加に伴い非常に長いbit列を必要とする。これは先日の例題で示した通り。これを解決するために、数値が増加しても極端にbit列が長くならないようにしたのがgamma符号。
まず数値を普通にbinary符号化する。binary符号って何？説明されてないよ、と思われるかもしれないが、これは普通に数値を2進数で表したものなので安心。つまり
数値 二進数 binary符号 1 1 0001 2 10 0010 3 11 0011 4 100 0100 5 101 0101 6 110 0110 7 111 0111
となる。このままbinary化したbit列を並べてしまうと数値間の境界がわからなくなる。そこでbinary符号ではbit列を固定長にして二進数の前方を0で埋めている。
一方でgamma符号は短い数値に短いbit列を割り振りたい。つまり可変長符号化をしたい。可変長符号化では数値あたりのbit数が固定でないために、数値の境界を示すbit列が余分に必要になる。(これはunary符号で説明した通り)。そのため数値の境界として数値に対応する二進数のbit数-1分の0を先頭に追加する。つまり
数値 二進数 gamma符号 1 1 1 2 10 010 3 11 011 4 100 00100 5 101 00101 6 110 00110 7 111 00111
となる。よって復号化するときは、まず0を1が出現するまで読み込んで1が出現したら、1とその後ろから先程カウントした0の数だけのbitを10進数に戻せばよい。例えば
00110010 => [00] 110010 # 0が2つ続いている => [00] [110] 010 # 1と、その後ろ2bitを分がひとつの数値 => (6) 010 # 110を復号化 => (6) [0] 10 # 0が1つ続いている => (6) [0] [10] # 1と、その後ろ1bitを分がひとつの数値 => (6) (2) # 10を復号化
となる。つまりunary符号では数値分だけ0を出力していたのだが、gamma符号では数値の2進表記に必要なbit数-1だけの0出力で済むようにしている。これによって符号長はO(N)からO(logN)になった。つまり大きな数値でもbit列の増大はある程度抑えられるようになった。
