stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(8): ポスティングリストの圧縮

前回は、検索インデックスで使用する辞書の圧縮について扱った。今回は、ポスティングリストの圧縮について解説する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の8日目の記事です。

adventar.org

ポスティングリストの圧縮

  • ポスティングファイル（ポスティングリストが収められたファイル）は辞書よりも少なくとも10倍、しばしば100倍以上大きい
  • ポスティングの docID を小さくする
  • Reuters-RCV1 (80 万文書) では docID に 32 ビット（4バイト）の整数値を使った
    • \log_2 800000 \approx 20 ビットまでは普通に小さくできる
  • docID を 20 ビットよりも小さくするのが今回のゴール
    • ほとんどの文書に登場するような単語 ("the" など) はもっと小さくしたい

差分符号化

  • ポスティングリストでは docID を昇順で保存する
    • 例： computer: 33, 47, 154, 159, 202, ...
  • docID の差分 (gap) だけを保存すれば十分
    • 33, 14, 107, 5, 43, ...
  • ほとんどの差分は 20 ビットよりも小さく保存できるはず
    • とくによく出てくる単語は

f:id:takuya-a:20201208234450p:plain
(IIR p.96 Table 5.3) 3つのポスティングリストの docID とその差分

可変長符号化

  • "arachnocentric" のようなレアな単語のポスティングリストには ~20 bits/gap 使ってもよい
  • "the" のような単語には ~1 bit/gap にしたい
  • それぞれの差分 (gap) について、できるだけ少ないビットで符号化したい
    • 可変長符号化 (variable length encoding) が必要
    • 可変長符号化では、小さい数字に対して小さなコードにできる

単進符号

  • 単進符号 (unary code) は、数 n を、連続した n 個の 1 と、最後の 1 つの 0 で表現する
    • 3
      • 1110
    • 40
      • 11111111111111111111111111111111111111110
  • P(n) = 2^(-n) のときには最適
  • 普通のユースケースではあまり有用ではない

ガンマ符号

  • ガンマ符号 (γ code) は、差分 (gap) G を、 length と offset のペアで表現する
  • offset は G を2進数にしたあと、先頭の 1 を削ったもの
    • 13 --> 1101 (2進数) --> 101
  • length は offset の長さを単進符号でエンコードしたもの
    • 13 (offset 101) の length は 3 --> 1110
  • ガンマ符号は length と offset を繋げたもの
    • 13 のガンマ符号は 1110101

f:id:takuya-a:20201208234539p:plain
(IIR p.98 Table 5.5) 単進符号とガンマ符号の例

ガンマ符号の特徴

  • G は 2 \lfloor \log G \rfloor + 1 ビットでエンコードされる
    • offset は \lfloor \log G \rfloor ビット
    • length は \lfloor \log G \rfloor + 1 ビット
  • ガンマ符号は奇数個のビットからなる
  • あらゆる分布の数値で使える
    • P(n) ~ 1/(2n^2) のとき最適
  • ガンマ符号はパラメータがない

ガンマ符号の速度

  • コンピュータはワード境界をもつ（8, 16, 32, 64ビット）
    • ワード境界をまたぐ操作は遅い
  • ビット単位での操作はとても遅い
  • 現代的な方法は、バイトやワードにアライン (align) した符号化を使っている

Variable-Byte (VB) 符号

  • Variable-Byte (VB) 符号 は、差分 (gap) G を、バイト単位で符号化していく
    • 7ビットのデータと、1ビットの継続ビット (continuation bit) c の並び（最上位ビットが継続ビット c ）
    • （継続ビットと言っているが、実際には最後のバイトのときだけこのビットが 1 になるので、ストップビットと言ったほうが意味的には通る気がする）
  • G が 127 以下なら、7ビット以下で表現できるので、その7ビットに継続ビット c = 1 をセットして終わり
  • そうでないなら、 G の低位の 7 ビットをエンコードしたあと、高位のビットは同じアルゴリズムでエンコードする
    • 最後のバイトの継続ビットは 1 (c = 1)
    • それ以外の継続ビットは 0 (c = 0)

f:id:takuya-a:20201208234619p:plain
(IIR p.97 Table 5.4) VB 符号の例

Group Variable Integer 符号

  • Google で使用されていた符号化方式
    • Jeff Dean, keynote at WSDM 2009 and presentations at CS276
  • 5 ~ 17 バイトのブロック内に 4 つの整数値を符号化
  • 先頭バイト
    • 4 つの 2ビットの長さを入れる
    • L1 L2 L3 L4, それぞれ 1, 2, 3, 4 のいずれかの数値が入る
    • それぞれが、あとに続く4つの整数値のバイト長を表現している
  • そのあと、 L1 + L2 + L3 + L4 バイト（4 ~ 16 バイトの範囲）の4つの数値をエンコード
    • それぞれの数値は 8/16/24/32 ビット（1 ~ 4 バイト）
  • VB 符号より2倍ほど速いらしい
    • ビットマスクの操作が不要なのでデコードが速い

Simple-9

f:id:takuya-a:20201209002438p:plain
Simple-9 は、32 ビットのブロックの中に、様々なレイアウトで複数の数値をエンコードする

  • Simple-9 [Anh & Moffat, 2004] は、ワード (32 ビット) でアラインされた数値符号化で、複数の数値符号化を使い分ける
  • 4 バイト (32 ビット) ごとにブロック化して符号化する
  • 最上位の 4 ビットをレイアウト (layout) といい、残りの 28 ビットの符号化方法（全9種類）を指定するのに使用する
    • 0: 1つの 28 ビットの数値
    • 1: 2つの 14 ビットの数値
    • 2: 3つの 9 ビットの数値（+ 1つのスペアビット）
    • 3: 4つの 7 ビットの数値
    • 4: 5つの 5 ビットの数値（+ 3つのスペアビット）
    • 5: 7つの 4 ビットの数値
    • 6: 9個の 3 ビットの数値（+ 1つのスペアビット）
    • 7: 14個の 2 ビットの数値
    • 8: 28個の 1 ビットの数値
  • ビットマスクを使って効率的にデコードできる
  • Simple-16 は 16 種類の符号化を使うバージョン
  • 他にも 64 ビットワードへの拡張など

講義資料

参考資料