接尾辞配列(Suffix Array)は，全文検索などに用いられるデータ構造です． それ以外にも，単語の出現回数を高速に求められたり， データ圧縮に使えたりなど，様々な応用例が提案されています． 2012年現在，SA-ISと呼ばれる手法がもっとも効率的に Suffix Array を求められるようです． その基礎となる考え方を１つずつ見ていくことにしましょう． Suffix Arrayとは Suffix Array とはどんなものなのでしょう？ 定義にそった，もっとも簡単なアルゴリズムを紹介します． バケットソート 基数ソートとバケットソートは，ソートする対象の種類が有限で範囲がはっきりしている場合に 非常に有効なソート手法です． これを使って Suffix Array を求めてみます． 2段階ソート 隣り合った接尾辞の比較は非常に簡単にできます． ことのことを利用してソートを高速化します