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

コンピュータサイエンスにおいて、ウッコネンアルゴリズムは、 1995 年にEsko Ukkonenによって提案された、接尾辞木を構築するための線形時間オンラインアルゴリズムです。 ^[¹^]このアルゴリズムは、文字列の最初の文字を含む暗黙の接尾辞木から始まります。次に、文字列を順にたどり、木が完成するまで連続する文字を追加します。この文字の順序付けにより、ウッコネンアルゴリズムは「オンライン」特性を持ちます。1973年にPeter Weinerによって発表された元のアルゴリズムは、最短の接尾辞から最長の接尾辞まで、最後の文字から最初の文字まで逆方向に進みました。^[²^] 1976 年にEdward M. McCreightによって、最長の接尾辞から最短の接尾辞まで進む、より単純なアルゴリズムが発見されました。 ^[³^]

暗黙の接尾辞ツリー

ウッコネンアルゴリズムを用いて接尾辞木を生成する際、文字列Sに含まれる文字に応じて、中間段階で暗黙の接尾辞木が生成されます。暗黙の接尾辞木では、$（またはその他の終端文字）ラベルの付いたエッジは存在せず、また、1つのエッジしか出ていない内部ノードも存在しません。

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

ウッコネンアルゴリズムは、文字列S（長さn）の各接頭辞S[1...i]に対して、暗黙の接尾辞木T _iを構築します。まず1^{番目の文字を使用してT}₁を構築し、次に2^{番目の文字を使用してT}_2を構築し、次に3^{番目の文字を使用してT}_3を構築し、...、n^{番目の文字を使用してT}_nを構築します。ウッコネンアルゴリズムを使用する接尾辞木には、次の特徴が見られます。

暗黙の接尾辞木 T _{i+1は、暗黙の接尾辞木 T}_iの上に構築されます。
ウッコネンのアルゴリズムは、どの時点においても、これまでに見た文字の接尾辞木を構築するため、オンライン特性を持ち、アルゴリズムの実行時間をO(n)にすることができます。
ウッコネンのアルゴリズムはn個のフェーズに分かれている（長さnの文字列の各文字に対して1つのフェーズ）。
各フェーズ i+1 はさらに i+1 個の拡張に分割され、それぞれが S[1...i+1] の i+1 個の接尾辞に対応します。

接尾辞拡張とは、これまでに構築された接尾辞ツリーに次の文字を追加することです。フェーズ i+1 の拡張 j では、アルゴリズムは S[j...i] の末尾 (前のフェーズ i により既にツリー内に存在する) を見つけ、S[j...i] を拡張して、接尾辞 S[j...i+1] がツリー内に存在することを確認します。拡張ルールは 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つだけ存在するという点に注意が必要です。同じ文字から始まるエッジが、どのノードからも複数存在することはありません。

実行時間

今後接尾辞木を生成するための単純な実装では、ビッグオー記法で O(n²) または O(n³) の時間計算量が必要となります。 $ここ$ で nは $文字列の長$ さ $です。ウッコネンは、$ いくつ $か$ のアルゴリズム的手法を活用することで、これを定数サイズのアルファベットの場合は $O$ $($ $n$ $) (線形) 時間、一般的には$ $O$ $($ $n$ $log$ $n$ $)$ に短縮し、以前の 2 つのアルゴリズムの実行時パフォーマンスに匹敵させました。