最終更新:2009-10-28 (水) 20:52:27 (5293d)  

Compressed Suffix Arrays
Top / Compressed Suffix Arrays

圧縮接尾辞配列 - CSA

Sedue

  • Sedueは全文検索を実現するのにCompressed Suffix Arrays (CSA)を利用しています。従来の全文検索システムでは前もって辞書などで決めておいた各単語?の出現位置を記録した転置ファイル方式、または、全ての長さNの部分文字列の出現位置を記録したN-gram方式が利用されていました。
  • 転置ファイル方式では高速な検索が実現できる一方、検索漏れが生じる恐れがあり、またN-gram方式においては漏れなく検索できますが、索引自体が大きくなりやすく、また検索クエリによっては速度が低下する可能性があります。
  • CSAは、
    • (1)どのようなクエリ?に対しても検索時間が変わらないことがアルゴリズムで保障されている
    • (2)検索時にインデクスを持つ必要が無く、テキストを索引のみから復元することができる（self-indexing）
  • 優れた特徴がある索引手法です。そのため数百万文書といった大規模なテキスト情報に対し高速に検索することが可能となります。
  • 例えば、クエリの検索結果として1件だろうが100万件だろうが検索に必要な時間は同じ数msで検索結果が得られます。(genome sedueで'a'を検索しても'aaaaaaaaaaaaaaaaa'を検索しても高速にでてきます。これは従来では難しかった技術です）。
  • また、索引自体に検索対象テキストの情報が含まれているためスニペット（検索結果の周辺の文字列）情報を提供するところがボトルネックにもなりますが、CSAでは索引をメモリ上においておけば、スニペット生成も高速に行うことができます。
  • また、転置ファイル方式やN-gram方式と同じもしくはそれより高速なインデックス構築を実現しています（詳細はベンチマークを参照）。この実現のためにいくつかのSuffix Array構築方法を組み合わせ、さらにチューニングを施しています。これに加え分散処理や随時更新を可能とするための機構が備わっています。
↑

参考

↑

関連




検索：