接尾辞配列(Suffix Array)

接尾辞配列(Suffix Array)は，全文検索などに用いられるデータ構造です． それ以外にも，単語の出現回数を高速に求められたり， データ圧縮に使えたりなど，様々な応用例が提案されています．

2012年現在，SA-ISと呼ばれる手法がもっとも効率的に Suffix Array を求められるようです． その基礎となる考え方を１つずつ見ていくことにしましょう．

Suffix Arrayとは

Suffix Array とはどんなものなのでしょう？ 定義にそった，もっとも簡単なアルゴリズムを紹介します．

バケットソート

基数ソートとバケットソートは，ソートする対象の種類が有限で範囲がはっきりしている場合に 非常に有効なソート手法です． これを使って Suffix Array を求めてみます．

2段階ソート

隣り合った接尾辞の比較は非常に簡単にできます． ことのことを利用してソートを高速化します．

SA-IS

バケットソート，そして2段階ソートの考え方をベースに さらなる高速化を行います． 2012年現在，最速な Suffix Array の構築法のようです．

SA-ISを試してみる

参考

• Wikipedia:接尾辞配列
• suffix array
  いろんなアルゴリズムについての説明がある
• SAIS(Suffix Array - Induced Sorting)
• SA-IS - (iwi) ｛ 反省します - TopCoder部
• Two Efficient Algorithms for Linear Suffix Array Construction
• esaxx
  Suffix Array を求めるための C++ テンプレート