転置インデックスの索引の効率的な保存
はじめに
索引データの保存に関する記事を読んだのでメモ。
索引データの効率的な保存
- ドキュメント数やできた索引数が多くなるにつれ、効率的に索引データを保存することが重要になってくる
- 工夫して索引データを保存することで、いろんなメリットがある
- メモリの節約
- ディスクのIO処理が減って読み込みスピードアップ
各手法
例えば転置インデクスでの索引では「索引単語：ページ番号1、ページ番号2、、、」という感じになっているので、右側のページ番号(整数列)を効率よく格納することを考える。
整数列をそのまま保存するのではなく、ソートしてその差分を保持するようにして符号化することで、効率よく格納することを考える。
VarByte
- バイト単位の操作のみで符号化できる
- 整数を1〜5byteで符号化(最上位1bit+下位7bit)
- 整数の1byte分読み込む
- 下位7bitに整数を入れる。もし、もとの整数が入りきらないならば、最上位bitに0を入れて、次の1byte分を読み込む
- もし入りきったらば最上位bitに1を入れて終了
- 可変長バイト型？
Rice符号
- Unary符号(整数を0の個数で保持)+Binary符号(整数をそのまま2進数で保持)
- 整数の(n+1)bit以降をUnary符号、下位nbitをBinary符号で符号化
- 欠点として、Unary符号の復元が遅かったりする
Simple9
- 整数列を同じビット幅で32bitに格納する
- 上位4bit(格納方式のタイプ)+下位28bit(実際の値)
- 9通りある(1bitごと、2bitごと、3、4、5、7、9、14、28bitごと)
- Simple9の由来
- Simple16とかもある
- Simple9を(11通りに)少し拡張した方がいた
new PFOR
- PForDelta?
- Simple9と同じように、同じbit幅で格納する
- 128個の整数を1ブロックとしてみる
- ブロック内の値の90%を格納できるbit幅nを求める
- 2^nより小さい値はそのまま記録
- そうでない場合は、下位nbitをそのまま格納し、入りきらない上位bitは別の整数列に格納
- 格納できなかった位置の差分を整数列として格納する
- 復元が非常に高速
ガンマ符号
- http://ja.wikipedia.org/wiki/%E3%82%AC%E3%83%B3%E3%83%9E%E7%AC%A6%E5%8F%B7
- 可変長符号
- 整数を2進数としてみたときのbit数-1の0を上位bitに追加
- 整数5なら「101」で3bitなので、「00101」
デルタ符号
- http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%AB%E3%82%BF%E7%AC%A6%E5%8F%B7
- 可変長符号
- 整数を2進数としてみたときのbit数をガンマ符号で出力(上位bit)
- 整数の2進数の最上位bitをのぞいたものを出力(下位bit)
