linkSuggest0907

pLinkSuggest

• 木を構築しないまま木の探索と等価な処理をするアルゴリズム

  • 「先祖かどうかの判定」と「最近共通先祖の取得」ができる必要がある。
  • 接尾辞配列の場合
    • 位置と長さの対が木の頂点だとみなせて
    • 先祖かどうかの判定は長さの比較で代用、
    • 最近共通先祖の取得にはLCP arrayの構築で前計算しておいた値を使えばO(1)でできる

• 木のノードを後置順巡回はできる

  • 子供にたどることはできないので、
  • 「どのドキュメントで出現したか」の情報は巡回の過程で親に伝える必要がある
  • 文書IDごとの出現回数を計算すれば出現集中を使ったキーワードっぽさの判定や、DFを使った高頻度すぎる単語の足切りもできるので良さそう

• いま単語がオブジェクトで、文書IDや自分自身の位置も持ってる

  • けど
    • これを複数ドキュメントまとめて、単語IDに変換して、そのまとめた列の中の位置で文書IDを引けるようにする
    • そしたらその長い列をまとめてSAISして出現頻度カウントもできる
  • 出現頻度カウントは一旦おいといて、今と同じ機能を実装して速度を比較するのがいいかな

• 既存のアルゴリズムが「与えられた文書セットの中での統計」なのに対してこちらは「新しい文書と、既存の文書セットの間の統計」なのが一工夫必要かな？

  • 接尾辞木に変換した方が良かったりするかも？
  • トップダウンで探索した方が探索範囲狭そうだし？
  • 混ぜてSA構築して、前後のノードを見れば良いのか？