スマートフォン用の表示で見る

suffix array

コンピュータ

Suffix Array

さふぃっくすあれい

文字列 T[0..n] に対する部分文字列 P[0..m] の探索を O(m lg n) で可能とするデータ構造。

文字列 T[0..n] における全部分文字列の出現位置を配列 SA[0..n] に保持し、SA を T に対して辞書式順にソートした配列 (接尾辞配列 = Suffix Array) を利用する。

例として "abracadabra" という文字列を考える。abracadabra の部分文字列の出現位置を列挙すると

0  => abracadabra
1  => bracadabra
2  => racadabra
3  => acadabra
4  => cadabra
5  => adabra
6  => dabra
7  => abra
8  => bra
9  => ra
10 => a

となる。この出現位置を、辞書式順にソートする

10 => a
7  => abra
0  => abracadabra
3  => acadabra
5  => adabra
8  => bra
1  => bracadabra
4  => cadabra
6  => dabra
9  => ra
2  => racadabra

ソートの結果得られた [ 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 ] という配列が SA である。"abracadabra" に対する部分文字列検索は、SA と元テキストを使った二分探索により実装できる。

Suffix Array を利用すると部分文字列を高速に検索することができるが

  • 大規模なデータから Suffix Array を構築するには、その大規模なデータにおける部分文字列をすべて保持する必要がある (空間コスト)
  • 大規模データから Suffix Array を構築するには大規模なソートを行う必要がある (時間コスト)

という二点の課題がある。この課題を解決するための方法はこれまで様々なものが提案されており、前者に対しては Suffix Array に特化したソートアルゴリズム、後者に対しては圧縮全文索引などを利用するなどの手法が提案されている。