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

May 16, 2021

接尾辞配列 Suffix Arraysは、長さ\(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_0a_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だと線形時間で構築することができる。