部分文字列インデックス

コンピュータサイエンスにおいて、部分文字列インデックスは、テキストまたはテキストコレクション内の部分文字列検索を準線形時間で実行できるデータ構造です。文書または文書セットから構築された部分文字列インデックスは、パターンサイズに対して線形またはほぼ線形の時間でパターンのすべての出現箇所を特定するために使用でき、文書サイズには依存しないか、対数的にのみ依存します。^{[ 1 ]}

全文インデックスという用語は、部分文字列インデックスを指す場合によく使われます。しかし、これは曖昧です。なぜなら、転置ファイルや文書検索などの通常の単語インデックスにも使われるからです。全文検索を参照してください。

これらのデータ構造は通常、テキストとパターンを固定アルファベット上の文字列として扱い、パターンがテキストのサブストリングとして出現する場所を検索します。アルファベットの記号は文字（たとえばUnicode ）である場合もありますが、テキスト検索の実用的なアプリケーションでは、テキストとパターンの両方の長さを記号の数で測って短縮できるため、文書の（語幹抽出された）単語をアルファベットの記号として扱う方が望ましい場合があります。^{[ 2 ]}

部分文字列インデックスとして使用できる具体的なデータ構造には、以下のようなものがあります。

• 接尾辞木は、文字列の接尾辞の基数木であり、部分文字列検索をシンボルごとに実行できます^{[ 1 ] [ 3 ]。}
• 接尾辞オートマトンとは、与えられたテキストの部分文字列を認識する最小の決定性有限オートマトンであり、接尾辞木と密接に関連しており、同じアルゴリズムの変種によって構築できる。^{[ 4 ]}
• 接尾辞配列は、文字列の接尾辞の開始位置をソートした配列であり、部分文字列検索を二分探索で実行できます。 ^{[ 1 ] [ 3 ]}接尾辞配列に、連続する接尾辞の共通接頭辞の長さのLCP 配列を追加すると、検索をシンボルごとに実行でき、接尾辞ツリーの検索時間と一致します。^{[ 5 ]}
• 圧縮サフィックス配列は、データ圧縮とサフィックス配列を組み合わせたデータ構造であり、テキストの長さに対して準線形な空間に構造を格納することを可能にする^{[ 1 ] [ 3 ]。}
• FMインデックスは、 Burrows–Wheeler変換に基づく別の圧縮部分文字列インデックスであり、接尾辞配列^{[ 6 ]と密接に関連しています。}