Google n-gram の検索

以前のエントリ（7/19）から既に 2 週間以上経過し，当初の計画より随分と簡単になって完成しました．

通常の検索システムであれば転置インデックスを使いますが，相手が n-gram なので，転置 n-gram（インデックスじゃなくて n-gram 本体）を使います．つまり，各 1-gram に対して，その 1-gram を含む n-gram のリストを保存しておくわけです．

特定の 1-gram を含む n-gram は単なる表引きにより実現されるので，何のひねりもありません．AND 検索時は，最も候補が少ない 1-gram を含む n-gram のリストに対してフィルタリングをおこなうだけです．データ構造は安直なものの，ディスクアクセスがシーケンシャルになるので高速です．


転置 n-gram の構築手順は以下のとおりです．

  1. 1-gram に対して頻度降順に ID を割り当てる．
    • これにより Variable Byte Encoding（VBE）の効率が上がる．
  2. 上述の ID を用いて n-gram をバイナリデータに変換する．
    • この時点で VBE により圧縮する．
  3. 1-gram, 2-gram, ..., 7-gram をそれぞれ頻度順に整列する．
  4. 各 1-gram に対して，その 1-gram を含む n-gram を列挙する．

2 日もあれば構築できると思います．
元データが約 100GB なのに対して，出力は 140GB 程度に収まりました．

※ 途中でデータを分割，マージするため，作業領域は 500GB くらい欲しいところです．


気が向いたらソースコードも公開します．