Ukkonen’s algorithm とは

コンピュータ科学では、Ukkonenのアルゴリズムは1995年にEsko Ukkonenによって提案された接尾辞木を構築するための線形時間のオンラインアルゴリズムです。
アルゴリズムは、文字列の最初の文字を含む暗黙の接尾辞ツリーで始まります。次に、ツリーが完成するまで連続する文字を追加する文字列をステップします。この注文文字の追加は、Ukkonenのアルゴリズムに「オンライン」プロパティを与えます。ピーター・ワイナーが提示した元のアルゴリズムは、最後の文字から最短のものから最長のものまでの最初のものに向かって進んだ。より簡単なアルゴリズムがEdward M. McCreightによって発見され、最長の接尾辞から最短の接尾辞に向かいました。
次のサフィックスツリーを生成するための素朴な実装では、大きなO表記でO(n2)またはO(n3)時間の複雑さが必要です。ここで、nは文字列の長さです。 Ukkonenは、多くのアルゴリズム技術を利用することで、これを従来の2つのアルゴリズムの実行時のパフォーマンスに合わせて、O(n)(線形)時間、一定サイズのアルファベット、O(n log n)