読者です 読者をやめる 読者になる 読者になる

FM-Indexで気になるところ

Computer

通勤の電車の中で漠然と脳内でN-gram IndexとFM-Indexを比べてて、気になるところをメモとして書いておく。

  • 動的な更新が難しい。まぁ、これは研究が進めば解決されそうな気はするが、現在は難しそう。
  • 基本、オンメモリで動作する。まぁ、N-gram Indexに比べてインデックスサイズが小さいからいいかなと思うけど、大規模なテキストを扱おうと思うとオンメモリは現実的ではないような気もする。オンディスクの実装は遅そうだな。N-gramは、オンディスクも十分可能である(Luceneとか)。
  • ヒット位置が必要なクエリの処理。ヒット位置を求めるには、SAの値をサンプリングして求めるらしいので、AというキーワードとBというキーワードが3文字以内に出現しているかどうかを検索する近傍検索とかだと、キーワードのすべてのヒット位置を求めないといけないので、いちいちサンプリング点から復元していたら効率が悪そう。N-gramならヒット位置を連続して復元してチェックするだけ。
  • XMLとかの構造を持つテキストに対する検索をどうする?まぁ、これは別途、XML構造を表現する情報を持たないと無理そうな気がする。
  • 複数のキーワードの検索は?例えば、同義語の検索とか。まぁ、キーワードごとに検索するしかないか。

的外れかもしれない。もう少し検討してみよう。