wataメモ

日々のメモをつらつらと書くだけ

ゴロム・ライス符号を試してみた

 前回のKazuhoさんのブログでブルームフィルタがソート済の整数列として表現できるという記載があった。 「ブルームフィルタを試してみた」のやり方ではソート済の整数列として扱ってはいない。 では「ソート済みの整数列として扱える」ということはどういうことかというと以下のページ(ブログの参考リンクの内の1つ)に書いてあった。 今回は上記のブログの解説的な話になっている。

Golomb-coded sets: smaller than Bloom filters - Giovanni Bajo's swapfile

 上記のブログによるとブルームフィルタでハッシュ値を計算した値を整数として扱うのだ。 上記のページでは「alpha」という文字は「1017」と計算されている。 *1

要素 ハッシュ値
alpha 1017
bravo 591
charlie 1207

 この1017という値を使って本来なら1017ビット目を立てるのだが、今回はそのまま整数として扱う。 そして、すべての値を計算したらハッシュ値をソートするのだ。 ブルームフィルタの特性上、どの値がどの要素だったから覚えておく必要はない。 以下はブログより引用したNATO フェネティックコードの文字列の計算結果。

[151L, 192L, 208L, 269L, 461L, 512L, 526L, 591L, 662L, 806L, 831L, 866L, 890L, 997L, 1005L, 1017L, 1134L, 1207L, 1231L, 1327L, 1378L, 1393L, 1418L, 1525L, 1627L, 1630L]

 これでブルームフィルタをソート済の整数列として扱うことが出来る。

ゴロム符号

 Wikipediaより引用

ゴロム符号(ゴロムふごう、Golomb coding)とは、南カリフォルニア大学のソロモン・ゴロムによって開発された、幾何分布に従って出現する整数を最適に符号化することのできる整数の符号化手法である。 ゴロム符号と類似の手法にライス符号があるが、ゴロム符号の特別な場合がライス符号になるため、ライス符号のことをゴロム・ライス符号(Golomb-Rice coding)と呼称することが多い。特にライス符号は符号化・復号の計算量が少ないことが特徴。圧縮率は幾何分布の時はハフマン符号と同一で、それ以外ではそれよりも悪い。

ライス符号

 符号化のパラメータmが2の冪であるときにライス符号となる。 これだけだと何を言っているのかわからないので、ブルームフィルタの例を上げる。

 ハッシュ値計算に用いる関数は1つとし26要素が登録されていて、1/64の確立で偽陽性が発生するデータ構造にしたい場合。 ハッシュ値の計算が数値になる都合上、26要素×64=1664ビット用意すれば満たすことになる。 この64というのが符号化のパラメータになり、64は2の6乗なので2の冪となる。

Golomb-coded sets

 さて、ここからが本題になる。 ブルームフィルタをソート済みの整数列として扱えたとしても表現するのに元のブルームフィルタより多くのビットが必要では意味が無い。 Kazuhoさんのブログにも書いてある通り、ソート済の整数列というのは汎用的なデータ構造で検索エンジン転置インデックスとか、色々なところで使うらしい。 その為、このデータ構造の様々な研究がなされている。 その内の空間効率が理論限界に近いのが今回のアルゴリズムということだ。

 整数列を圧縮するには、zlibのような汎用アルゴリズムは向かない。 なぜなら文字列をハッシュ値に変換した値はzlibからするとランダムデータに見えるからだ。

 今回の考え方を理解するために例を上げながら考えてみよう。 26x64=1664の範囲から26個の数値をランダムに選択したとする。 あなたがある値とその次の値との差がどの程度になる予想するとなると「64ぐらい」と考えないだろうか。 もちろん全要素が均一に64の差で選択されることは殆どないが、大体それぐらいに分布することがイメージできる。 つまり、ある値とその次の値の差は64未満や64から128未満に収まる可能性は非常に高く、128から194未満に収まるのは少し稀で194から256未満に収まるのはさらに少し稀と続いていく。 これは幾何分布に従っていると言える。

 そしてこの性質を利用することでデータと圧縮しようと言うのだ。 ある値とその次の値の差を普通に数値として表現するのではなく、符号化パラメータ(今回は64)の余りに分けて考える。 「商」は幾何分布の特性上恐らく0か1になる可能性が高く、それ以上になるのは確率的に低くなっていくので、アルファ符号で表現する。 そして「余り」の部分はどんな値になるかはランダムなので通常のビットで表現する。 今回の場合は0から63(0相対)となるので6ビットで表現する。

商の符号化

数値 符号
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110

 より大きい数値の場合は表現するのにビット数がより多く要るようになっている。

符号化

 全体としての符号化した結果の一部は以下のようになる。 ※最初の要素は差としては0との差とする

数値 余り ゴロム符号
151 2 23 110 010111
41 0 41 0 010111
16 0 16 0 010000
61 0 61 0 11101

 そして最終的な符号化結果は以下となる。

11001011 10101001 00100000 11110111 10000000 01100110 00111010 00000110 00011111 00100000 01100101 00011001 10001010 10110001 00000011 00101101 01100010 01001100 01010000 00110011 00011110 01100110 10101110 10011000 00011

 これは197ビットとなり、約7.57ビット/単語となる。 理論値は26×log2(64)=156なので、そこまでは及ばないが非常に近いのがわかる。

復号

 符号化の手順を逆にすることで復号することが出来る。

まとめ

 こういったアルゴリズムの理解は場合によっては不要なこともあると思うが、知っておいても損は無いのではないだろうか。 ただ、無数有るアルゴリズムすべてを勉強することは難しい。 そういう場合はやはり自分が関わっている、もしくは興味がある分野で使われているアルゴリズムを学ぶのが良いと考えている。

*1:ハッシュ値計算ロジックとしては要素のmd5値を計算し、それを16進数の数値として扱い余りを使っている。