linkSuggest0907

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

「先祖かどうかの判定」と「最近共通先祖の取得」ができる必要がある。

接尾辞配列の場合

位置と長さの対が木の頂点だとみなせて

先祖かどうかの判定は長さの比較で代用、

最近共通先祖の取得にはLCP arrayの構築で前計算しておいた値を使えばO(1)でできる

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

子供にたどることはできないので、

「どのドキュメントで出現したか」の情報は巡回の過程で親に伝える必要がある

文書IDごとの出現回数を計算すれば出現集中を使ったキーワードっぽさの判定や、DFを使った高頻度すぎる単語の足切りもできるので良さそう

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

けど

これを複数ドキュメントまとめて、単語IDに変換して、そのまとめた列の中の位置で文書IDを引けるようにする

そしたらその長い列をまとめてSAISして出現頻度カウントもできる

出現頻度カウントは一旦おいといて、今と同じ機能を実装して速度を比較するのがいいかな

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

接尾辞木に変換した方が良かったりするかも？

トップダウンで探索した方が探索範囲狭そうだし？

混ぜてSA構築して、前後のノードを見れば良いのか？