人工 知能学会誌 15 巻 6 号(2000 年 11 月) 1 用語 Suffix Array 解 説 suffix array とは高速な文字列検索を可能にするデー タ構造である。UNIX の grep コマンドのような「テキ ストに対するあらゆる部分文字列の検索」を高速∗1 に行 なうことができる。ただし、あらかじめ検索用インデッ クス ( = suffix array) を作成しておく必要がある。 suffix array のしくみについて説明する前に、まず suffix について説明する。suffix とは検索対象となるテキス ト中のある位置から始まりテキスト末尾までの範囲の文 字列である。どの suffix も開始位置が特定されれば一意 に決まる。この開始位置をインデックスポイント (index point) と呼ぶ [Baeza-Yates 99]。例えば、テキスト「さ くさくさくら」に