ウッコネンのアルゴリズム

コンピュータサイエンスにおいて、ウッコネンのアルゴリズムは、 1995年にエスコ・ウッコネンによって提案された、線形時間のオンラインサフィックスツリー構築アルゴリズムです。 ^[¹^]このアルゴリズムは、文字列の最初の文字を含む暗黙のサフィックスツリーから開始されます。次に、文字列を1つずつ順に処理し、ツリーが完成するまで文字を順次追加していきます。この順序どおりの文字追加により、ウッコネンのアルゴリズムは「オンライン」という特性を持っています。 1973年にピーター・ワイナーによって提案されたオリジナルのアルゴリズムは、最後の文字から最初の文字へと、最短サフィックスから最長サフィックスへと逆方向に処理を進めていました。^[²^] 1976年にはエドワード・M・マクリートによって、最長サフィックスから最短サフィックスへと進む、より単純なアルゴリズムが発見されました。 ^[³^]

暗黙の接尾辞木

Ukkonen のアルゴリズムを使用してサフィックスツリーを生成する際に、文字列 S の文字に応じて中間ステップで暗黙的なサフィックスツリーが表示されます。暗黙的なサフィックスツリーでは、$ (またはその他の終了文字) ラベルを持つエッジはなく、そこから 1 つのエッジのみが出る内部ノードはありません。

ウコネンのアルゴリズムの概要

Ukkonenのアルゴリズムは、S（長さnの文字列）の各プレフィックスS[1...i]に対して、暗黙的なサフィックスツリーT _iを構築します。まず、 1^{番目の文字を使ってT}₁を構築し、次に2^{番目の文字を使ってT}_{2 を}構築し、3^{番目の文字を使ってT}₃を構築し、…、n^{番目の文字を使ってT}_{n を}構築します。Ukkonenのアルゴリズムを用いたサフィックスツリーには、以下の特徴があります。

暗黙的なサフィックスツリー T _{i+1は暗黙的なサフィックスツリー T}_iの上に構築されます。
ウッコネンのアルゴリズムは、任意の時点で、これまでに見た文字の接尾辞ツリーを構築するため、オンライン特性を持ち、アルゴリズムの実行時間をO(n) にすることができます。
Ukkonen のアルゴリズムは n フェーズに分かれています (長さ n の文字列の各文字ごとに 1 フェーズ)。
各フェーズ i+1 はさらに i+1 個の拡張に分割され、S[1...i+1] の i+1 個の接尾辞ごとに 1 つずつあります。

サフィックス拡張とは、それまでに構築されたサフィックスツリーに次の文字を追加することです。フェーズi+1の拡張jにおいて、アルゴリズムはS[j...i]（前のフェーズiによって既にツリーに含まれている）の終端を見つけ、サフィックスS[j...i+1]がツリーに含まれるようにS[j...i]を拡張します。拡張ルールは3つあります。

S[j...i]というラベルが付いたルートからのパスがリーフエッジで終了する場合（つまり、S[i]がリーフエッジの最後の文字である場合）、文字S[i+1]はそのリーフエッジのラベルの末尾に追加されます。
S[j...i]というラベルのルートからのパスが非リーフエッジで終了している場合（つまり、パス上でS[i]の後に文字がさらに存在する場合）、次の文字がS[i+1]でない場合、文字S[i+1]から始まるラベルS[i+1]と番号jを持つ新しいリーフエッジが作成されます。S[1...i]が非リーフエッジの内側（中間）で終了している場合も、新しい内部ノードが作成されます。
S[j..i]というラベルが付いたルートからのパスが非リーフエッジで終了し（つまり、パス上でS[i]の後にさらに文字がある）、次の文字がS[i+1]（すでにツリー内にある）である場合は、何も行いません。

重要な点として、特定のノード（ルートノードまたは内部ノード）からは、1つの文字から始まるエッジは1つだけ存在します。同じ文字から始まるエッジが1つ以上存在することはありません。

実行時間

今後、接尾辞木を生成するための単純な実装では、 big O 記法で $O (n 2)$ 、あるいは $O (n 3)の時間計算量が必要となる$ $（n$ は文字列の長さ）。Ukkonenは、様々なアルゴリズム手法を駆使することで、定数サイズのアルファベットではこれを $O$ $($ $n$ $) （線形）時間、一般的には$ $O$ $($ $n$ $log$ $n$ $)$ にまで短縮し、前述の2つのアルゴリズムの実行時性能と同等の性能を実現した。

ウッコネンのアルゴリズムの例

Ukkonen のアルゴリズムを使用してサフィックスツリーがどのように構築されるかをわかりやすく説明するために、文字列を考えてみましょうS = xabxac。

空のルートノードから開始します。
文字列の最初の文字を追加してfor を構築します。ルール2が適用され、新しいリーフノードが作成されます。 $T_{1}$ S[1]
(と)の接尾辞を追加してfor を構築します。ルール1が適用され、既存のリーフエッジのパスラベルが拡張されます。ルール2が適用され、新しいリーフノードが作成されます。 $T_{2}$ S[1..2]xaxaa
( 、および)の接尾辞を追加してを構築します。ルール1が適用され、既存のリーフエッジのパスラベルが拡張されます。ルール2が適用され、新しいリーフノードが作成されます。 $T_{3}$ S[1..3]xabxababb
接尾辞( 、、 )を追加してfor を構築します。ルール1が適用され、既存のリーフエッジのパスラベルが拡張されます。ルール3が適用され、何も行われません。 $T_{4}$ S[1..4]xabxxabxabxbxx
接尾辞（、、、）を追加してを構築します。ルール1が適用され、既存のリーフエッジのパスラベルが拡張されます。ルール3が適用され、何も行われません。 $T_{5}$ S[1..5]xabxaxabxaabxabxaxaa
の接尾辞（、、、、）を追加してを構築します。ルール1が適用され、既存のリーフエッジのパスラベルが拡張されます。ルール2が適用され、新しいリーフノードが作成されます（この場合、3つの新しいリーフエッジと2つの新しい内部ノードが作成されます）。 $T_{6}$ S[1..6]xabxacxabxacabxacbxacxacacc