5分でわかる(気がする)Suffix Array

SuffixArrayはしくみが単純だが簡単に全文検索を実現できる。知っておくと便利なので解説する。

例えば

banana

という文字列に対して、それぞれの文字から始まる文字列を接尾辞(Suffix)という。つまり

1: banana
2: anana
3: nana
4: ana
5: na
6: a

こういうのがSuffix。何文字目から始めたのか(Index)を先頭に書いておいた。これを辞書順に並べ替える。

6: a
4: ana
2: anana
1: banana
5: na
3: nana

このときのIndexを並べたものが接尾辞配列(SuffixArray)と呼ばれるもの。

6 4 2 1 5 3

Indexと元の文字列があればSuffixが復元できるのでこれだけ持っておけばOK。
Suffixは辞書順にソートされているので任意のキー(例えばanaとか)が単語中のどこに出てくるかを二分探索で検索できる。

# 真ん中(6/2 = 3番目)のSuffix(anana)と比較
   6: a
   4: ana
→ 2: anana    > ana
   1: banana
   5: na
   3: nana


# キー(ana)のほうが小さいので、anana以下のSuffixを捨てる。
   6: a
   4: ana

# 真ん中(2 / 2 = 1番目)のSuffix(a)と比較
→ 6: a      < ana
   4: ana


# キー(ana)のほうが大きいので、a以上のSuffixを捨てる。
   4: ana

# 残ったSuffix(ana)と比較
→ 4: ana    = ana

# 発見。周辺にキー(ana)ではじまるSuffixがないか調べる
× 6: a
○ 4: ana
○ 2: anana

# よって文字列(banana)の2,4文字目の位置に
# キー(ana)があることがわかった
  v   v
b a n a n a