まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。
(この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
概要
列 $S$ の先頭から $0$ 個以上の要素を取り除いてできる列を、列 $S$ のSuffix (接尾辞) と呼びます。$S$ の Suffix は空列を含めて $|S| + 1$ 種類存在します。
$S$ の Suffix を全て格納した Trie 木を $S$ の Suffix Trie と呼びます。以下は $S = \mathrm{nknnknnnk}$ の Suffix Trie です。
Suffix Trie には長さ $O(|S|)$ の列が $S+1$ 個格納されるので、単にメモリだけでも $O(|S|^{2})$ のサイズが必要となってしまいます。
そこで Suffix Trie に存在する無駄な 頂点/辺 の削減を試みます。具体的には出次数が $1$ である頂点と、そこから出る辺を削減します。なお、ここでは一旦終端ノードのことを忘れておきます。
Suffix Trie の無駄な頂点と辺を削除し、上記のような木を得ました。ただし Suffix Trie の辺に割り当てられていた要素はそのまま連結して辺ラベルとして持たせてあります。
このように得た木のことを Suffix Tree と呼びます。
Suffix Tree の説明に入る前に、準備段階として事前情報をまとめておきます。
- Suffix Tree の頂点数は $O(N)$ 個です。
-
Suffix Tree 上の地点であり、根からその地点までの経路上の要素を連結して列 $P$ が得られるような地点を単に地点 $P$ と呼ぶことにします。
- 地点 $P$ を表現するとき、$(r,n,p) = $ (どの頂点から , どの頂点へ , どれだけ進んだ地点か) を持ちます。
- 例えば $P = \mathrm{nnkn}$ は $(r,n,p) = (9,4,2) $ です。
- そのようなデータの持ち方が複数存在する場合、$p$ が最も小さい場合を採用します。($P = \mathrm{nknn}$ は $(r,n,p) = (5,\phi,0) $ )
さて上記の Suffix Tree ですが、現在 $S$ の Suffix 全てを明示的に保持しているため、まだ $O(|S|^2)$ サイズのままです。そこで、各辺に割り振られた列が $S$ の連続部分列であることに注目し、Suffix Tree の辺には列 $S$ のどの区間を参照するかを表す $2$ つの整数を割り振ることにします。
なお、割り振る区間は 0-index の半開区間です。これで空間計算量は $O(|S|)$ に抑えることができました。
Suffix Tree の嬉しさ
「列 $S$ の Suffix Tree 上の地点」と「列 $S$ の連続部分列」が１対１対応しています。つまり、Suffix Tree を構築することは列 $S$ の連続部分列を全て明示的に列挙することと等しいです。これはとても良いことです。
おいどんは連続部分列の問題が出たらとりあえず Suffix Tree を考えてます。それぐらい強いです。例えば $S$ の連続部分列 $S[l,r)$ のローリングハッシュは以下の様にして Suffix Tree で完全に代替できます
- Suffix Tree の頂点に対して、ダブリングの要領で $2^k$ 個上の祖先を答えるテーブルを用意する。
- $S$ の $l$ 文字目から始まる接尾辞に対応する頂点を $P$ とする。
- 1 で用意したテーブルを使って、$P$ の祖先であり、対応する列の長さが $r-l$ 以下の頂点のうち最も近いものを二分探索する。
- 3 で求めた頂点から、$S[l,r)$ に対応する地点を計算する ($O(1)$ 時間で可能)。
簡単なアルゴリズム
Suffix Tree をはじめから構築することを考えます。$i$ 番目に格納する Suffix を $F_i$ と表記することにします。
各 Suffix を格納する際の基本的な操作は Trie 木に格納する場合とほとんど同様です。つまり、すでに構築されている木に含まれる部分を共有して、それ以降は枝分かれさせて新しい葉ノードを作成します。以下は Suffix を長い順に格納していく様子です (頂点には生成された順に $0$ から番号を割り振っています)。
しかしこの方法では $F_i$ を格納するのに $O(|F_i|)$ 時間かかるため、ダメです。
さて、突飛ですが $S$ の Suffix Array と LCP Array が与えられているものとします(いずれも $O(|S|)$ 時間で求まります)。LCP Array とは、Suffix Array で隣接する 2 つの Suffix に共通する最長の接頭辞の長さを並べたものです。
Suffix の格納順を長さ順ではなく、Suffix Array における登場順として格納していきましょう。なお、$F_i$ を Suffix Tree に格納する処理は、格納する場所さえわかれば $O(1)$ 時間で処理できます。
こうして並べることで、ある連続する $2$ つの Suffix : $F_i,F_{i+1}$ の Suffix Tree 上での共有部分がわかり、毎回 Suffix を格納するたびに格納場所を根から探索する手間を省略できます。
具体的には、$F_i$ と $F_{i+1}$ の LCP の長さを $x$ とすると、$F_i$ を格納した地点から、長さ (地点までの要素数) が $x$ 以下の祖先までバックトラックします。ここで、バックトラックする時には辺に書かれた要素を $1$ つずつ見る必要はありません。現在いる頂点から親頂点にジャンプして OK です。
バックトラックで到達した頂点から $F_{i+1}$ を格納するために進むべき辺を再計算します。LCP が $x$ であることがわかっているので、その辺の上の地点で長さがちょうど $x$ になる地点が、$F_{i+1}$ を格納するときの共有部分です。これは辺の情報などから $O(1)$ 時間で割り出すことができます。
辺の上に新たに頂点を作成したり、新たに辺を作成する操作も定数時間で行うことができます。この操作を全ての接尾辞に対して行うと、Suffix Tree が完成します。
計算量について
果たしてこれで本当に線形時間になるのでしょうか。もう一度構築の様子を見てみましょう。以下は $F_4 = \mathrm{nk}$ を格納するためにバックトラックしている様子です。
これをみて何かお気づきではないですか？そうです、これは木上で辞書順優先で DFS を行う手順と同じです。
$F_i$ の格納は、格納する場所がわかれば $O(1)$ 時間で処理可能で、辺/頂点 の追加も $O(1)$ 時間で可能なので、バックトラックの計算量を DFS の計算量で抑えることができました。
次回予告
冒頭で示した Suffix Tree と、簡単なアルゴリズムで作った Suffix Tree を見比べると、何か違いがありませんか？
結論から言うと、今作った Suffix Tree の方が強い形をしています。と言うのも、$S$ の全ての接尾辞に対して、対応する頂点が Suffix Tree 上に存在するからです。これらの頂点は、冒頭の Suffix Trie に存在した終端ノードに対応しており、これが存在することで Suffix Tree 上でのさまざまな処理を行うことができます。
ではなぜ左側のような弱い形の Suffix Tree が存在するのでしょうか。左側の Suffix Tree については、次の機会に説明しますので、乞うご期待です。