Suffix Array

suffix array とは、高速な全文検索を可能とするデータ構造のことです。 接尾辞配列ともよばれています。

特徴

特徴は以下の通りです。

  • あらかじめ検索用のインデックスを作成しておく必要がある
    • このインデックス構築(=SuffixArrayの構築)に時間がかかる。
  • 検索がめちゃくちゃ速い
    • インデックス構築時間とのトレードオフ
    • このトレードオフをいかに隠蔽してシステムとしてUIを提供するかが応用するにあたっての鍵となる(と思っている)
  • 検索の際に元データが必要である
  • 簡単なデータ構造なので実装が簡単(難しいことをしなければ)

suffix array に関連する情報は以下で入手できます。が、とにかく一度シンプルなアルゴリズムを使って実装してみると感覚がつかめると思います。

関連する論文などは以下で入手できます。

特徴

suffix array だけでは単に高速に検索できるっていうだけなので、応用するにあたって必要になってくる関連技術があります。以下の通りです。

応用を考えると、サーチエンジン的なアーキテクチャになるので以下も参考に。

Share this post:
Child pages:

Comments