接尾辞配列
tl;dr
全文検索などで使われる接尾辞配列(suffix array)について調べたのでメモ
接尾辞配列とは
文書すべての位置から始まる部分文字列を辞書式順序で小さい順に並べ、その位置を格納したものです。 全文検索では接尾辞配列をインデックスとして利用すると、任意の文字列を漏れなく高速に検索できます。
例えば、文字列 T[0, n) があたえられたとき、末尾をT[n-1]=$は他に出現しない、どの文字よりも小さい文字=適当な記号にします。
このとき、このTのすべての接尾辞Si = T[i, n)、0 <= i < nを辞書順にソートして、添字番号iを格納した配列を接尾辞配列(Suffix Array)と呼び、 SAt[0, n)で表します。
例として「abracadabra」という文字列を考えてみます。
末尾にどの文字より小さい文字として$をつけます。「abracadabra$」
これで、文字列 「abracadabra$」はT[0, 11)で表されます。
このときの文字列のある開始位置から末尾までの文字列である「接尾辞(suffix)」は以下のようになります。
| 開始位置 i | suffix(Si) |
|---|---|
| 0 | abracadabra$ |
| 1 | bracadabra$ |
| 2 | racadabra$ |
| 3 | acadabra$ |
| 4 | cadabra$ |
| 5 | adabra$ |
| 6 | dabra$ |
| 7 | abra$ |
| 8 | bra$ |
| 9 | ra$ |
| 10 | a$ |
| 11 | $ |
これをSiでソートして配列にすると、
| 開始位置 i | suffix(Si) |
|---|---|
| 11 | $ |
| 10 | a$ |
| 7 | abra$ |
| 0 | abracadabra$ |
| 3 | acadabra$ |
| 5 | adabra$ |
| 8 | bra$ |
| 1 | bracadabra$ |
| 4 | cadabra$ |
| 6 | dabra$ |
| 2 | racadabra$ |
| 9 | ra$ |
という並びになります。 これが配列を、接尾辞配列 (suffix array)です。
部分文字列の探索
接尾辞配列(Suffix Array)と呼び、 SA[0, n)があったとき、文字列 T[0, n) の部分文字列はSA[sp, se)で表現できます。
例えば「abracadabra$」の部分文字列 abraはSA[2,4]=(S7, S0)の接頭辞です。
つまり、部分文字列がTのどこに出現したかはSAの範囲を調べたらわかります。
このときの計算量は、長さｍのクエリ文字列Q[0,m)が出現している接尾辞配列の範囲SA[sp, ep)は接尾辞配列上の[二分探索]で求められるので、O(m log n)です。
さらに部分文字列の出現回数はse - spです。
そしてこれは、 N-gramインデックスの拡張にも使えます。 ngramの場合、同じ文字列が別の位置に出現する可能性がありますが、接尾辞配列の場合は文字列T中の開始位置だけ指定すれば表現できて、T中の開始位置は一意に決まるため、集合位置リストを格納する必要はなく長さnの整数配列として格納できるので効率的です。
