Suffix Arrays: A New Method for On-Line String Searches

May 16, 2021

接尾辞配列 Suffix Arrayは、長さ$P$の文字列が長さ$W$の文字列のどこに出現するかを時間計算量$\mathcal{O}(P + \log N)$で判定できるデータ構造で、接尾辞木 suffix treeよりもメモリ効率が3-5倍よい。一方、検索の準備にかかる最悪時間計算量はsuffix treeよりも大きい。 suffix arrayの構築にかかる最悪時間計算量が$\mathcal{O}(N\log N)$に対して、suffix treeは$\mathcal{O}(N)$しかかからない。

Suffix Arrayは文字列のすべてのsuffixを辞書順にソートした配列であり、配列には、suffixそのものではなく、その開始位置を格納する。長さ$N$の文字列を$A=a_0\ a_1\cdots a_{N-1}$, $i$番目から始まる$A$のsuffixを$A_i$, suffixを辞書順にソートしたときの開始位置の配列を$\textit{POS}$, $\le$を辞書順の記号とすると、 $$ A_{\text{POS}[0]} \le \dots \le A_{\text{POS}[N-1]} $$ がなりたつ。ここで$\le_p$を長さ$p$のprefixでくらべた辞書順の関係とすると $$ A_{\text{POS}[0]} \le_p \dots \le_p A_{\text{POS}[N-1]} $$ も同時に成立する。ただし、長さが$u(<p)$のときは先頭$u$文字でくらべる。このとき、長さ$p$の文字列の$A$における全ての開始位置を二分探索で検索できる。

単純に長さ$n$の文字列$n$個をソートしてsuffix arrayをつくると、$\mathcal{O}(n^2\log n)$時間かかってしまう。論文の後半は、ダブリングによって$\mathcal{O}(n\log_2 n)$時間でソートする手法が説明されている。なお、suffix arrayを構築するアルゴリズムはいくつかあり、例えばSA-ISだと線形時間で構築することができる。

論文をこちらからダウンロードできます。
論文のほかにプログラミングコンテストチャレンジブック第二版を参考にしました。