ウッコネンの接尾辞木アルゴリズムを平易な英語で説明する 質問する

以下は、まず文字列が単純な場合（つまり、重複する文字が含まれていない場合）に Ukkonen アルゴリズムが何を行うかを示し、次にそれを完全なアルゴリズムに拡張することによって、Ukkonen アルゴリズムを説明する試みです。

まず、いくつか予備的な説明をします。

1. 私たちが構築しているのは、基本的に検索トライのようなものです。つまり、ルートノードがあり、そこから新しいノードにつながるエッジがあり、そこからさらにエッジが出て、というように続きます。

2. ただし、検索トライとは異なり、エッジ ラベルは単一の文字ではありません。代わりに、各エッジは 1 組の整数を使用してラベル付けされます[from,to]。これらはテキストへのポインタです。この意味で、各エッジは任意の長さの文字列ラベルを保持しますが、必要なスペースは O(1) (2 つのポインタ) だけです。

基本的な原則

まず、特に単純な文字列、つまり重複文字のない文字列の接尾辞ツリーを作成する方法を説明します。

abc

アルゴリズムは、左から右へと段階的に動作します。文字列の各文字に対して 1 つのステップがあります。各ステップには複数の個別の操作が含まれる場合がありますが、操作の合計数は O(n) であることがわかります (最後の観察を参照)。

そこで、左から始めて、最初にaルート ノード (左側) からリーフへのエッジを作成し、 というラベルを付けることで、単一の文字のみを挿入します[0,#]。これは、エッジが位置 0 から始まり、現在の終了で終わる部分文字列を表すことを意味します。記号は、位置 1 ( の直後) にある現在の終了 を#表すために使用します。a

したがって、初期ツリーは次のようになります。

そして、それは次のことを意味します:

次に位置2（ の直後b）に進みます。各ステップの目標は、現在の位置までのすべての接尾辞を挿入することです。これは次のように行います。

• 既存のa-edgeを拡張してab
• 新しいエッジを1つ挿入するb

私たちの表現では、これは次のようになります

そして、それが意味するのは次の通りです。

私たちは2つのことを観察します:

• のエッジ表現は、初期ツリーで使用されていたものと同じabです: 。現在の位置を1 から 2 に更新したため、その意味は自動的に変更されました。[0,#]#
• 各エッジは、それが表す文字数に関係なく、テキストへの 2 つのポインターのみで構成されるため、O(1) のスペースを消費します。

次に、位置を再度増分し、c既存のすべてのエッジに を追加し、新しいサフィックス の新しいエッジを 1 つ挿入してツリーを更新しますc。

私たちの表現では、これは次のようになります

そして、それが意味するのは次の通りです。

私たちは次のことを観察します:

• ツリーは各ステップの後の現在の位置までの正しい接尾辞ツリーである。
• テキスト内の文字数と同じ数のステップがあります
• 各ステップの作業量は O(1) です。これは、既存のエッジはすべて を増分することによって自動的に更新され#、最後の文字に対する 1 つの新しいエッジの挿入は O(1) 時間で実行できるためです。したがって、長さ n の文字列の場合、必要な時間は O(n) 時間だけです。

最初の拡張: 単純な繰り返し

もちろん、これがうまく機能するのは、文字列に繰り返しが含まれていないからです。次に、より現実的な文字列を見てみましょう。

abcabxabcd

abc前の例と同様に から始まり、abが繰り返され、 が続きx、 がabc繰り返され、 が続きますd。

ステップ 1 から 3:最初の 3 つのステップの後、前の例のツリーが得られます。

ステップ 4:#位置 4 に移動します。これにより、既存のすべてのエッジが次のように暗黙的に更新されます。

そして、現在のステップの最後の接尾辞 をaルートに挿入する必要があります。

これを実行する前に、に加えてさらに 2 つの変数を導入します#。もちろん、これらの変数はこれまでずっと存在していましたが、これまで使用していませんでした。

• アクティブポイントは、トリプル(active_node,active_edge,active_length)
• はremainder、挿入する必要がある新しい接尾辞の数を示す整数である。

これら 2 つの意味はすぐに明らかになりますが、今のところは次のように言っておきましょう。

• 単純なabc例では、アクティブ ポイントは常に(root,'\0x',0)、つまりactive_nodeルート ノードであり、active_edgeヌル文字 として指定され'\0x'、active_lengthはゼロでした。この結果、各ステップで挿入した 1 つの新しいエッジが、ルート ノードに新しく作成されたエッジとして挿入されました。この情報を表すためにトリプルが必要な理由はすぐにわかります。
• 各ステップの開始時には常に 1 に設定されていましremainderた。これは、各ステップの終了時にアクティブに挿入する必要のあるサフィックスの数が 1 (常に最後の文字のみ) であることを意味します。

これから状況が変わります。現在の最後の文字をaルートに挿入すると、 で始まる出力エッジがすでに存在していることがわかりますa。具体的には、abcaです。このような場合、次のようにします。

• ルート ノードに新しいエッジを挿入しません[4,#]。代わりに、サフィックスがaすでにツリー内にあることに気付きます。サフィックスは長いエッジの途中で終わりますが、気にしません。そのままにしておきます。
• アクティブ ポイントを に設定します(root,'a',1)。つまり、アクティブ ポイントは、 で始まるルート ノードの出力エッジの中央a、具体的にはそのエッジの位置 1 の後になります。エッジは、単に最初の文字 で指定されていることがわかります。特定の文字で始まるエッジは1 つしかa存在しないため、これで十分です(説明全体を読んだ後で、これが正しいことを確認してください)。
• も増分するremainderので、次のステップの開始時には 2 になります。

観察:挿入する必要のある最後のサフィックスがツリーにすでに存在することが判明した場合、ツリー自体はまったく変更されません(アクティブ ポイントと のみを更新しますremainder)。ツリーは現在の位置までのサフィックス ツリーの正確な表現ではなくなりますが、すべてのサフィックスが含まれます(最後のサフィックスは暗黙的にa含まれているため)。したがって、変数を更新すること (すべて固定長であるため、これは O(1) です) 以外に、このステップでは作業は行われませんでした。

ステップ 5:現在の位置を#5 に更新します。これにより、ツリーは次のように自動的に更新されます。

そしては 2 なので、remainderab現在の位置の最後の 2 つの接尾辞、およびを挿入する必要がありますb。これは基本的に次の理由によるものです。

• 前のステップの接尾a辞は適切に挿入されていません。そのため、 のままであり、 1 ステップ進んだため、接尾辞は から に増加しましaたab。
• そして、新しい最終エッジを挿入する必要がありますb。

実際には、これはアクティブ ポイント (a現在はエッジの後ろを指すabcab) に移動して、現在の最終文字 を挿入することを意味しますb。ただし、ここでも、 は同じエッジにすでに存在していることがわかりますb。

したがって、ここでもツリーは変更しません。単に次の操作を行います。

• アクティブポイントを(root,'a',2)（以前と同じノードとエッジですが、今度は の後ろを指しますb）に更新します。
• remainder前のステップからの最終エッジがまだ適切に挿入されていないため、現在の最終エッジも挿入されないため、を 3 に増やします。

明確に言うと、現在のステップでabと を挿入する必要がありましたが、がすでに見つかっているため、アクティブ ポイントを更新し、 を挿入しようとさえしませんでした。なぜでしょうか。がツリー内にある場合、のすべての接尾辞( を含む) もツリー内にある必要があるためです。 おそらく暗黙的にのみ ですが、これまでのツリーの構築方法により、 はそこになければなりません。babbabb

を増分してステップ 6に進みます#。ツリーは自動的に次のように更新されます。

はremainder3 なのでabx、 、bx、を挿入する必要がありますx。アクティブ ポイントは のab終点を示しているので、そこにジャンプして を挿入するだけですx。実際、xはまだそこにないので、abcabxエッジを分割して内部ノードを挿入します。

エッジ表現は依然としてテキストへのポインターであるため、内部ノードの分割と挿入は O(1) 時間で実行できます。

これで、 とを 2 にabx減分する処理ができましたremainder。次に、残りの次の接尾辞 を挿入する必要がありますbx。ただし、その前にアクティブ ポイントを更新する必要があります。分割してエッジを挿入した後のこのルールは、以下ではルール 1と呼ばれ、 がルートである場合に適用されますactive_node(他のケースについては、以下でルール 3 を学習します)。ルール 1 は次のとおりです。

ルートからの挿入後、

• active_nodeルートのまま
• active_edge挿入する必要がある新しいサフィックスの最初の文字に設定されます。つまり、b
• active_length1減少

したがって、新しいアクティブポイントトリプルは、次の挿入がエッジの 1 文字後ろ、つまり の後ろ(root,'b',1)で行われる必要があることを示しています。挿入ポイントを O(1) 時間で識別し、 がすでに存在するかどうかを確認できます。 が存在する場合は、現在のステップを終了し、すべてをそのままにします。 しかしは存在しないため、エッジを分割して挿入します。bcabxbxx

これも O(1) 時間がかかり、ルール 1 で述べたようremainderに 1 とアクティブ ポイントに更新されます。(root,'x',0)

しかし、もう 1 つやらなければならないことがあります。これをルール 2 と呼びます。

エッジを分割して新しいノードを挿入し、それが現在のステップで作成された最初のノードでない場合は、特別なポインタであるサフィックス リンクを介して、以前に挿入したノードと新しいノードを接続します。これがなぜ便利なのかは後で説明します。以下は、サフィックス リンクが点線のエッジとして表される結果です。

現在のステップの最後のサフィックス を挿入する必要がありますx。アクティブ ノードのコンポーネントが 0 になったためactive_length、最後の挿入はルートに直接行われます。 で始まるルート ノードには出力エッジがないためx、新しいエッジを挿入します。

ご覧のとおり、現在のステップでは残りの挿入がすべて作成されました。

=7を設定してステップ 7に進みます#。これにより、いつものように、次の文字 がaすべてのリーフ エッジに自動的に追加されます。次に、新しい最後の文字をアクティブ ポイント (ルート) に挿入しようとしますが、すでに存在していることがわかります。そのため、何も挿入せずに現在のステップを終了し、アクティブ ポイントを に更新します(root,'a',1)。

ステップ 8で=8となり#、 を追加しますb。前述のように、はすでに存在しているため、これはアクティブ ポイントを に更新し(root,'a',2)て増分するだけで、他には何も行いません。ただし、 (O(1) 時間で) アクティブ ポイントがエッジの終端にあることがわかります。これを反映するために、 を に再設定します。ここで、 はエッジが終了する内部ノードを指します。remainderb(node1,'\0x',0)node1ab

次に、ステップ#=9で'c' を挿入する必要があります。これにより、最後のトリックを理解するのに役立ちます。

2番目の拡張: サフィックスリンクの使用

いつものように、#更新はリーフ エッジに自動的に追加されc、アクティブ ポイントに移動して 'c' を挿入できるかどうかを確認します。 'c' は既にそのエッジに存在することが判明したため、アクティブ ポイントを に設定し(node1,'c',1)、増分しremainderて他には何も行いません。

現在、ステップ#=10ではremainder4 なので、最初にアクティブ ポイントに挿入abcdして (3 ステップ前から残っているもの)を挿入する必要があります。d

dアクティブポイントに挿入しようとすると、 O(1)時間でエッジ分割が発生します。

active_node分割が開始された は、上記で赤くマークされています。最終ルールであるルール 3 は次のとおりです。

ルート ノードではないからエッジを分割した後active_node、そのノードから出ているサフィックス リンクがあればそれをたどり、 をそれが指すノードにリセットします。サフィックス リンクがない場合は、 をルートにactive_node設定します。変更されません。active_nodeactive_edgeactive_length

したがって、アクティブ ポイントは現在 であり(node2,'c',1)、node2以下のように赤でマークされています。

の挿入がabcd完了したので、 をremainder3 に減分し、現在のステップの次の残りのサフィックスを検討します。ルール 3 では、アクティブ ポイントが適切なノードとエッジに設定されているので、アクティブ ポイントに最後の文字を挿入するだけでbcd挿入をbcd実行できます。d

これを行うと、別のエッジ分割が発生し、ルール 2 により、以前に挿入されたノードから新しいノードへのサフィックス リンクを作成する必要があります。

次のことがわかります:サフィックス リンクを使用すると、アクティブ ポイントをリセットして、次の残りの挿入をabO(1) の労力で行うことができます。上のグラフを見て、ラベルのノードが (そのサフィックス)のノードにリンクされb、 のノードが にリンクされていることを確認しabcてくださいbc。

現在のステップはまだ終了していません。remainderは現在 2 であり、アクティブ ポイントを再度リセットするにはルール 3 に従う必要があります。 現在のactive_node(上記の赤) にはサフィックス リンクがないため、ルートにリセットします。 アクティブ ポイントは現在 です(root,'c',1)。

cしたがって、次の挿入は、ラベルが:で始まるルート ノードの 1 つの出力エッジでcabxabcd、最初の文字の後ろ、つまり の後ろで発生しますc。これにより、別の分割が発生します。

また、これには新しい内部ノードの作成が含まれるため、ルール 2 に従って、以前に作成した内部ノードから新しいサフィックス リンクを設定します。

（使っていますグラフビズドットこれらの小さなグラフの場合。新しい接尾辞リンクにより、dot は既存のエッジを再配置するため、上に挿入されたものが新しい接尾辞リンクだけであることを慎重に確認してください。

これにより、remainderを 1 に設定でき、 がactive_nodeルートであるため、ルール 1 を使用してアクティブ ポイントを に更新します(root,'d',0)。つまり、現在のステップの最後の挿入は、dルートに 1 つの を挿入することです。

これが最後のステップで、これで完了です。ただし、最終的な観察事項がいくつかあります。

• 各ステップで#1 ポジションずつ前進します。これにより、すべてのリーフ ノードが O(1) 時間で自動的に更新されます。

• しかし、a) 前のステップから残っている接尾辞、および b) 現在のステップの最後の 1 つの文字は処理されません。

• remainderは、追加で挿入する必要がある回数を示します。これらの挿入は、現在の位置で終わる文字列の最後のサフィックスに 1 対 1 で対応します#。1 つずつ検討して挿入を行います。重要:アクティブ ポイントによって挿入先が正確に示され、アクティブ ポイントに追加する必要があるのは 1 つの文字だけなので、各挿入は O(1) 時間で実行されます。なぜでしょうか。他の文字は暗黙的に含まれているためです(そうでなければ、アクティブ ポイントは現在の場所にありません)。

• このような挿入のたびに、デクリメントしてremainder、サフィックスリンクがある場合はそれに従います。サフィックスリンクがない場合は、ルートに移動します (ルール 3)。すでにルートにいる場合は、ルール 1 を使用してアクティブポイントを変更します。いずれの場合も、O(1) 時間しかかかりません。

• これらの挿入のいずれかの途中で、挿入したい文字がすでに存在することが判明した場合、remainder>0 であっても何も行わずに現在のステップを終了します。その理由は、残っている挿入はすべて、作成しようとした文字の接尾辞となるためです。したがって、それらはすべて現在のツリーに暗黙的remainderに存在します。 >0 であるという事実により、残りの接尾辞を後で処理することが確実になります。

• アルゴリズムの最後がremainder>0 の場合はどうなるでしょうか。これは、テキストの末尾が以前のどこかで発生した部分文字列である場合に常に当てはまります。その場合、文字列の末尾に、以前に発生したことのない 1 つの文字を追加する必要があります。文献では、通常、ドル記号が$その記号として使用されます。なぜそれが重要なのでしょうか。 --> 後で完成したサフィックス ツリーを使用してサフィックスを検索する場合、一致がリーフで終了する場合にのみ受け入れる必要があります。そうでない場合、ツリーに暗黙的に含まれている文字列の多くがメイン文字列の実際のサフィックスではないため、多くの誤った一致が発生します。最後に 0 を強制することは、基本的に、すべてのサフィックスがリーフ ノードで終了することを保証する方法です。ただし、ツリーを使用してメイン文字列のサフィックスだけでなく一般的な部分文字列を検索する場合は、以下の OP のコメントで示唆されているように、この最終ステップは実際には必要ありません。remainder

• では、アルゴリズム全体の複雑さはどの程度でしょうか。テキストの長さが n 文字の場合、明らかに n ステップ (ドル記号を追加すると n+1) になります。各ステップでは、何もしない (変数の更新以外) か、remainder挿入を行います。挿入にはそれぞれ O(1) の時間がかかります。はremainder、前のステップで何もしなかった回数を示し、挿入を行うたびに減算されるため、何かを行う合計回数はちょうど n (または n+1) です。したがって、合計の複雑さは O(n) です。

• しかし、私がきちんと説明していなかった小さなことが 1 つあります。それは、サフィックス リンクをたどり、アクティブ ポイントを更新した後、そのactive_lengthコンポーネントが新しい でうまく機能しないことが判明する可能性があるというactive_nodeことです。たとえば、次のような状況を考えてみましょう。

(破線はツリーの残りの部分を示します。点線はサフィックス リンクです。)

ここで、アクティブ ポイントを とします。これは、エッジ上(red,'d',3)の の後ろの場所を指します。ここで、必要な更新を行ったと仮定し、接尾辞リンクをたどって、ルール 3 に従ってアクティブ ポイントを更新します。新しいアクティブ ポイントは です。ただし、緑のノードから出ている -エッジは であるため、文字数は 2 のみです。正しいアクティブ ポイントを見つけるには、当然、そのエッジを青のノードまでたどり、 にリセットする必要があります。fdefg(green,'d',3)dde(blue,'f',1)

特に悪いケースでは、active_lengthは まで大きくなりremainder、これは n まで大きくなる可能性があります。また、正しいアクティブ ポイントを見つけるために、内部ノードを 1 つだけ飛ばすのではなく、最悪の場合には n まで飛ばす必要があることも考えられます。これは、各ステップが一般に O(n) であり、サフィックス リンクをたどった後のアクティブ ノードへの事後調整も O(n) になる可能性があるため、アルゴリズムに隠れた O(n ² ) の複雑性がremainderあることを意味しますか?

いいえ。その理由は、実際にアクティブ ポイントを調整する必要がある場合 (たとえば、上記のように緑から青へ)、独自の接尾辞リンクを持つ新しいノードに到達し、 がactive_length削減されるからです。接尾辞リンクのチェーンをたどって残りの挿入を行うと、 はactive_length減少することしかできず、途中で実行できるアクティブ ポイントの調整回数は、active_lengthどの時点においても を超えることactive_lengthはできません。 は を超えることはなくremainder、remainderは各ステップで O(n) であるだけでなく、remainderプロセス全体で に対して行われた増分の合計も O(n) であるため、アクティブ ポイントの調整回数も O(n) によって制限されます。