Google n-gram に索引を

Google n-gram のデータが大きすぎて，簡単には使えないとのことで，索引を付けてほしいと依頼されました．AND 検索ができれば OK とのことでしたが，規模が大きいので何か良い方法がないか模索中です．

まとまっていませんが，以下，考えている方法です．

  • Google n-gram のデータ
    • http://googlejapan.blogspot.com/2007/11/n-gram.html
      • 総単語数: 255,198,240,937 (2550億)
      • 総文数: 20,036,793,177 (200億)
      • 異なり 1-gram 数: 2,565,424
      • 異なり 2-gram 数: 80,513,289
      • 異なり 3-gram 数: 394,482,216
      • 異なり 4-gram 数: 707,787,333
      • 異なり 5-gram 数: 776,378,943
      • 異なり 6-gram 数: 688,782,933
      • 異なり 7-gram 数: 570,204,252
      • 圧縮した状態で約 26GB，復元すると約 100GB

文書検索として考えると，1-gram が Word，各 n-gram が Doc となります．つまり，語彙数 2.5M，文書数 3.3G となり，各文書は短い（1-7 語）という特徴があります．

さらに，各 n-gram には prefix となる (n-1)-gram が必ず存在するという仮定が（おそらく）可能です．そのため，各ノードが各 n-gram と対応する木構造（ノード数 3.3G）を構築可能であり，Succinct Tree Structure（BP, DFUDS, LOUDS）を使用すれば，かろうじてメモリ上に展開できます（ラベルや頻度は除く）．

※ ただし，私の使っている PC はメモリが 1GB しかないので無理です．次は最低でも 4GB を確保しようと思います． :D

ラベル（1-gram）と頻度については，外部記憶に並べておけば良さそうです．Tx はそんな風にしてありそうだという情報がありましたし…．

索引は，各 1-gram に対して，その 1-gram をラベルとして持つノード番号の差分を並べたものを使います．このとき，深さ優先の木構造を採用する場合は，当該ノードからの差分ではなく，兄弟ノードからの差分を使用します．

  • 残る課題
    • AND 検索用のマージを効率良く実現できるか検証する必要があります．
      • マージ：ノードの組が与えられたとき，先祖と子孫の関係になるかどうかを確認する処理です．
    • 任意のノードから木を root 方向に辿りつつ，効率的に n-gram を復元できるかどうか検証する必要があります．
  • 修正
    • 書くのを忘れていた BP, DFUDS を追加しました．