string 配列 Ukkonenのサフィックスツリーアルゴリズム




接頭辞木 (5)

私はこの時点でちょっと厚く感じます。 私はサフィックスツリー構築の周りに頭を抱かせようと数日間過ごしましたが、数学的な背景がないので、数学的シンボルを過度に使うようになるにつれて、多くの説明がわかりません。 私が見つけた良い説明に最も近いのは、 サフィックスツリーを使ったファーストストリングの検索ですが、彼はさまざまな点について言及し、アルゴリズムのいくつかの側面は不明です。

スタックオーバーフローに関するこのアルゴリズムのステップバイステップの説明は、私以外の多くの人にとって非常に貴重です。

参考までに、ここでUkkonenのアルゴリズムに関する論文があります: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf : http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

私の基本的な理解は、これまでのところ:

  • 私は与えられた文字列Tの各接頭辞Pを繰り返し処理する必要があります
  • 接頭辞Pの各接尾辞Sを繰り返してツリーに追加する必要があります
  • サフィックスSをツリーに追加するには、Sの各文字を繰り返し処理する必要があります。反復は、Sの同じ文字セットCから始まり、潜在的に子孫ノードにエッジを分割する既存のブランチを歩くか接尾辞の異なる文字に到達するか、または一致するエッジがなくなるかどうかを判定します。 Cのために一致するエッジがない場合、Cの新しいリーフエッジが作成されます。

ほとんどの説明で指摘されているように、基本的なアルゴリズムはO(n 2 )のように見えますが、すべての接頭辞を辿る必要があるため、各接頭辞の各接尾辞を踏む必要があります。 Ukkonenのアルゴリズムは、彼が使用している接尾辞ポインタ技術のために、明らかにユニークですが、私はそれが私が問題を理解していると思っいます。

私はまた、理解に問題があります:

  • 「アクティブポイント」が割り当てられ、使用され、変更された正確な時期と方法
  • アルゴリズムの正準化の側面で何が起こっているか
  • 私が見た実装が、使用している境界変数を「修正」する必要があるのはなぜですか

ここに完成したC#ソースコードがあります。 それは正しく動作するだけでなく、自動カノニゼーションをサポートし、出力のより美しいテキストグラフをレンダリングします。 ソースコードとサンプル出力は次の場所にあります:

https://gist.github.com/2373868

アップデート2017-11-04

長年にわたり、私はサフィックスツリーの新しい用途を見出し、 JavaScriptでアルゴリズムを実装しました。 Gistは以下の通りです。 バグがないはずです。 jsファイルにダンプし、 npm install chalkは同じ場所からnpm install chalknpm install chalkから、node.jsを実行してカラフルな出力を表示します。 同じGistには、デバッグコードがなくなり、削除されたバージョンがあります。

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6


以下は、Ukkonenアルゴリズムを、文字列が単純な場合(繰り返し文字が含まれていない場合)に何を行うかを示し、それを完全なアルゴリズムに拡張して説明する試みです。

まず、いくつかの予備的な声明。

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

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

基本的な原則

私は最初に、特に単純な文字列、繰り返し文字のない文字列の接尾辞ツリーを作成する方法をデモンストレーションしたいと思います。

abc

このアルゴリズムは、左から右へステップごとに機能します文字列のすべての文字に対して1つのステップがあります 。 各ステップには複数の個別操作が含まれる場合がありますが、操作の総数がO(n)であることが最終的な観察結果でわかります。

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

だから私たちには初期ツリーがあります。

そしてそれが意味することはこれです:

今度は位置2に進みます( b直後)。 各ステップでの目標は、 すべての接尾辞を現在の位置まで挿入することです。 我々はこれを行う

  • 既存a aedgeをab拡張する
  • bに対して1つの新しい辺を挿入する

私たちの表現では、このように見えます

そしてそれが意味することは:

我々は 2つのことを観察する

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

次に、位置を再度インクリメントし、既存のすべてのエッジにcを追加し、新しい接尾辞c 1つの新しいエッジを挿入して、ツリーを更新します。

私たちの表現では、このように見えます

そしてそれが意味することは:

我々は観察する:

  • ツリーは、各ステップの後に現在の位置までの正しい接尾辞ツリーです
  • テキストには文字があるだけ多くのステップがあります
  • 既存のすべての辺が#をインクリメントして自動的に更新され、最後の文字の新しい辺を挿入するのはO(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)トリプル(active_node,active_edge,active_length)
  • remainderは、挿入する必要がある新しいサフィックスの数を示す整数です

これらの2つの正確な意味はすぐに明らかになりますが、今はちょうど言ってみましょう:

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

今これは変更される予定です。 現在の最終文字aをルートに挿入するとaから始まる発信エッジが存在することがabcaます。具体的にaabcaです。 このような場合に私たちがすることは次のとおりです。

  • ルートノードに新しいエッジ[4,#]を挿入しません 。 代わりに、接尾辞aがすでにツリーにaことに気付くだけです。 それは長いエッジの真ん中で終わりますが、私たちはそれに悩まされません。 私たちは物事を彼らのままにしておきます。
  • アクティブポイント(root,'a',1)ます。 つまり、アクティブポイントは、ルートノードの発信エッジの途中にあります。ルートノードの開始位置は、そのエッジ上の位置1の後ろです。 エッジは最初の文字aによって単に指定されていることがわかります。 これは、特定の文字から始まるエッジが1つしかないためです(説明全体を読んだ後にこれが正しいことを確認してください)。
  • remainderも増やすので、次のステップの開始時には2になります。

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

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

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

  • 前のステップの接尾辞が正しく挿入されたことはありません。 それで、それは残っており、私たちは一歩進んだので、今からaに成長しましa
  • 新しい最終エッジを挿入する必要があります。

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

だから、私たちは木を変更しません。 我々は単純に:

  • アクティブな点を(root,'a',2)更新します(root,'a',2)前と同じノードとエッジですが、ここではb後ろを指しています)
  • 前のステップからの最後のエッジがまだ正しく挿入されていないためremainderを3に増やし、現在の最終エッジも挿入しません。

明らかにするには、現在のステップでabbを挿入する必要がありましたが、 abがすでに見つかりましたので、アクティブポイントを更新し、 bを挿入しようとしませんでした。 どうして? もしabが木の中にあれば、それのすべての接尾辞bも含む)が木になければならないからです。 多分暗黙的にしかそうではありませんが、これまでそこにツリーを構築してきたためにそこに存在しなければなりません。

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

remainderは3 abxabxbxxを挿入する必要があります。 アクティブポイントはabがどこで終了するかを示しているので、そこにジャンプしてxを挿入するだけです。 実際には、 xはまだ存在しないので、 abcabx端を分割して内部ノードを挿入します。

エッジ表現はまだテキストへのポインタなので、内部ノードを分割して挿入することはO(1)の時間に行うことができます。

したがって、 abxを処理し、 remainderを2に減らしました。次に、次の残りの接尾辞bxを挿入する必要があります。 しかし、それを行う前に、アクティブポイントを更新する必要があります。 これを行うためのルールは、分割してエッジを挿入した後、 ルール1と呼ばれ、 active_nodeがルートである場合は常に適用されます(ルール3は、以下でさらに詳しく説明します)。 ここにルール1があります:

ルートからの挿入後、

  • active_nodeはrootのままです
  • active_edgeは、挿入する必要がある新しい接尾辞の最初の文字に設定されます。つまり、 b
  • active_lengthが1減らされます。

したがって、新しいアクティブポイントトリプル(root,'b',1)は、次の挿入がbcabxエッジで、1文字の後、すなわちb後に行われなければならないことを示します。 O(1)時間内に挿入点を特定し、 xがすでに存在するかどうかを確認することができます。 それが存在していれば、現在のステップを終了し、すべてのままにします。 しかし、 xは存在しないので、エッジを分割して挿入します。

この場合も、O(1)時間がかかっており、ルール1が示すように(root,'x',0) remainderを1に更新し、アクティブポイントを(root,'x',0)に更新します。

しかしもう一つ必要なことがあります。 このルール2と呼ぶ

エッジを分割して新しいノードを挿入し、それが現在のステップで作成された最初のノードでない場合は、以前に挿入されたノードと新しいノードを特別なポインタ、 サフィックスリンクで接続します。 私たちは後でそれがなぜ有用であるかを見るでしょう。 ここに私達が得たものがあります。接尾辞のリンクは点線で表されています:

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

わかるように、現在のステップでは残りの挿入がすべて行われました。

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

ステップ8の # = 8では、 bを追加します。これは以前のように、アクティブポイントを(root,'a',2)に更新し、 bが既に存在するため、何もせずにremainderを増やすことを意味します。 しかし、 (O(1)の時点で)アクティブポイントが現在エッジの終わりにあることがわかります。 これを(node1,'\0x',0)再設定して反映します。 ここでは、ノード1を使用して、 abエッジが終わる内部ノードを参照します。

次に、 ステップ# 9で「c」を挿入する必要があり、これが最終的なトリックを理解するのに役立ちます。

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

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

今度はステップ# = 10remainder is 4なので、まずアクティブポイントにdを挿入してabcd (3ステップ前から残る)を挿入する必要があります。

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

分割が開始されたactive_node 、上記の赤でマークされています。 最後のルール、 ルール3があります。

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

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

abcdの挿入が完了しているので、 remainderを3に減らして、現在のステップの次の残りの接尾辞bcdます。 ルール3はアクティブポイントをちょうど正しいノードとエッジに設定しているので、 bcdを挿入するには最後の文字dをアクティブポイントに挿入するだけです。

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

サフィックスリンクを使用すると、アクティブポイントをリセットすることができ、次の残りの挿入をO(1)の作業で行うことができます。 上記のグラフを見て、ラベルabのノードがb (その接尾辞)のノードにリンクされ、 abcのノードがbcリンクされていることを確認します。

現在の手順はまだ完了していません。 remainderが2になり、ルール3を実行してアクティブポイントを再度リセットする必要があります。 現在のactive_node (上の赤色)には接尾辞のリンクがないので、rootにリセットします。 アクティブポイントは現在(root,'c',1)です。

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

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

(私はGraphviz Dotを使ってこれらの小さなグラフを作成しています。新しいサフィックスリンクでドットが既存のエッジを再配置するようになったので、上に挿入された唯一のものが新しいサフィックスリンクであることを確認してください。

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

それが最終ステップであり、私たちは完了です。 しかし、 最終的な観察の数があります:

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

  • しかし、それはa)前のステップから残っている接尾辞と、b)現在のステップの最後の1つのキャラクターとを扱わない。

  • remainderは、追加のインサートをいくつ作る必要があるかを示します。 これらの挿入は、現在の位置#で終わる文字列の最後の接尾辞に1対1で対応します。 我々は次々と考え、挿入物を作る。 重要:各インサートはO(1)時間で実行されます。これは、アクティブポイントがどこに行くかを正確に示しているため、アクティブポイントに1文字だけ追加する必要があるためです。 どうして? 他の文字は暗黙的に含まれているため(そうでなければ、アクティブな点は存在しない)。

  • このような挿入のたびに、 remainderを減らし、接尾辞があればそれに従います。 そうでなければ、私たちは根本的に行きます(ルール3)。 すでにルートにいる場合は、ルール1を使用してアクティブポイントを変更します。いずれの場合も、O(1)時間しかかかりません。

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

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

  • だからアルゴリズム全体の複雑さは? テキストの長さがn文字の場合、明らかにn個のステップがあります(ドル記号を追加するとn + 1)。 各ステップでは、変数を更新する以外には何もしないか、それぞれO(1)時間かかるremainder挿入を行います。 remainderは前のステップで何度も何度も何度も何度も何度も行ったことを示しており、現在行っているすべての挿入に対してデクリメントされているので、何かを行う回数は正確にn(またはn + 1)です。 したがって、総複雑度はO(n)である。

  • しかし、私が正しく説明していない小さなものが1つあります。サフィックスリンクに従ってアクティブポイントを更新し、そのactive_lengthコンポーネントが新しいactive_nodeうまく動作しないことがあります。 たとえば、次のような状況を考えてみましょう。

破線はツリーの残りを示し、点線は接尾辞リンクです。

さて、アクティブポイントを(red,'d',3)にして、 defg端にあるf後ろの場所をdefgます。 ここで、必要な更新を行い、ルール3に従ってアクティブポイントを更新するためにサフィックスリンクに従ったとします。新しいアクティブポイントは(green,'d',3)です。 ただし、緑色のノードから出て行くd edgeはde 。したがって、2文字しかありません。 正しいアクティブ点を見つけるためには、明らかに、青いノードにそのエッジをたどり、 (blue,'f',1)リセットする必要があります。

特に悪いケースでは、 active_lengthはnと同じくらい大きい可能性があります。 正しいアクティブポイントを見つけるためには、1つの内部ノードにジャンプするだけでなく、最悪の場合には多くの場合n個までジャンプする必要があります。 つまり、各ステップのremainderは一般的にO(n)であり、サフィックスリンクをたどった後のアクティブノードの事後調整はO(n)なので、アルゴリズムは隠れたO(n 2 )の複雑さを有するのだろうか?

なぜなら、実際にアクティブポイント(例えば上記のように緑色から青色)を調整しなければならない場合、独自の接尾辞リンクを持つ新しいノードになり、 active_lengthが減少するからです。 サフィックスリンクのチェーンをたどって残りのインサートをactive_lengthすると、 active_lengthは減少するだけで、途中で実行できるアクティブポイント調整の数は、任意の時点でactive_lengthより大きくすることはできません。 active_lengthは決してremainderよりも大きくなることはありません。 remainderはすべての単一ステップでO(n)だけでなく、プロセス全体でremainderインクリメントの合計もO(n)であるため、能動点調整もまたO(n)によって制限される。


@jogojapanあなたは素晴らしい説明と視覚化をもたらしました。しかし@makagonovが述べたように、接尾辞リンクの設定に関するいくつかのルールが欠落しています。http://brenden.github.io/ukkonen-animation/「aabaaabb」という単語を使って一歩一歩進んでみるといいですね。ステップ10からステップ11に進むと、ノード5からノード2への接尾辞リンクはありませんが、アクティブポイントは突然そこに移動します。

私はJavaの世界に住んでいるので、@マカゴノフ私はまた、あなたの実装をSTのワークフローを把握するために従ってみたが、それは私にとっては難しかった:

  • ノードとノードを結合する
  • 参照の代わりにインデックスポインタを使う
  • 文を壊す。
  • 継続陳述書;

だから私は、Javaでそのような実装を完成させました。これは、すべてのステップを明確に反映し、他のJavaユーザーの学習時間を短縮することを望みます。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}

jogojapanの答えに示された接尾辞ツリーを実装しようとしましたが、ルールに使用されている言葉のためにうまくいかない場合がありました。 さらに、私は、誰もこのアプローチを使用して絶対に正しい接尾辞ツリーを実装することはできないと述べました。 以下では、ルールに対するいくつかの変更を加えて、jogojapanの回答の概要を書きます。 重要なサフィックスリンクを作成することを忘れた場合についても説明します。

使用された追加変数

  1. アクティブポイント - トリプル(active_node;アクティブ_エッジ;アクティブ_長さ)で、新しいサフィックスの挿入を開始する必要がある場所を示します。
  2. remainder - 明示的に追加する必要がある接尾辞の数を示します。 たとえば、単語が「abcaabca」で、remainder = 3の場合は、最後の3つの接尾辞: bcacaおよびaを処理する必要があります。

内部ノードの概念を使用しましょう。 ルートリーフを除くすべてのノードは内部ノードです。

観測1

挿入する必要がある最後のサフィックスがすでにツリーに存在する場合、ツリー自体は変更されません( active pointremainderのみを更新します)。

観測2

active_lengthが現在のエッジの長さ( edge_length )より大きいか等しい場合、 active_lengthactive_lengthより厳密に大きくなるまでactive point下げます。

さて、ルールを再定義しましょう:

ルール1

アクティブノード = rootから挿入した後、 アクティブな長さが0より大きい場合は、次のようになります。

  1. アクティブノードは変更されません
  2. アクティブな長さがデクリメントされる
  3. アクティブな辺が右にシフトされます(次の接尾辞の最初の文字に挿入する必要があります)

ルール2

新しい内部ノードを作成するか、 内部ノードからインサータを作成し、現在のステップで最初のSUCH 内部ノードでない場合は、前のSUCHノードをサフィックスリンクを介してこのノードとリンクします。

このRule 2定義は、JogoJapanとは異なります。ここでは、 新しく作成された内部ノードだけでなく、内部ノードも考慮に入れます。

ルール3

ルート ノードではないアクティブノードから挿入した後、サフィックスリンクをたどって、それが指すノードアクティブノードを設定する必要があります。 サフィックスリンクがない場合は、 アクティブノードルートノードに設定します。 どちらの方法でも、 有効エッジアクティブ長は変更されません。

Rule 3この定義では、葉ノード(​​分割ノードだけでなく)の挿入も考慮する。

最後に、観測3:

Observation 1によれば、ツリーに追加したいシンボルがすでにエッジにある場合、ツリーを変更せずにactive pointremainderのみを更新します。 しかし必要なサフィックスリンクとしてマークされた内部ノードがある場合は、そのノードをサフィックスリンクを介して現在のactive node接続する必要があります。

このような場合にサフィックスリンクを追加し、 そうでない場合は、 cdddcdcのサフィックスツリーの例を見てみましょう:

  1. 接尾辞リンクを使用してノードを接続しない場合:

    • 最後の文字cを追加する前に:

    • 最後の文字を追加した後c

  2. 接尾辞リンクを使用してノードを接続する場合:

    • 最後の文字cを追加する前に:

    • 最後の文字を追加した後c

重要な違いはないようです:第2のケースでは、さらに2つの接尾辞リンクがあります。 しかし、これらの接尾辞リンクは正しいですし、青いノードから赤いノードへのリンクの1つは、 アクティブポイントを使用したアプローチにとって非常に重要です。 問題は、ここに接尾辞リンクを置かないと、後でツリーに新しい文字を追加するときに、 Rule 3ためにツリーにいくつかのノードを追加することを省略することができるということです。接尾辞のリンクがない場合は、 active_nodeをルートに配置する必要があります。

最後の文字をツリーに追加するとき、青いノードから挿入する前にすでに赤いノードが存在しいました (エッジに'c'が付いています)。 青いノードからの挿入があるので、それは接尾辞リンク必要とするものとしてマークします。 次に、 アクティブポイントアプローチに依拠して、 active nodeが赤ノードに設定されました。 しかし、文字'c'が既に端にあるので、赤いノードから挿入することはありません。 青いノードを接尾辞リンクなしで残す必要があることを意味しますか? いいえ、サフィックスリンクを使って青のノードと赤のノードを接続する必要があります。 それはなぜ正しいですか? アクティブ・ポイント・アプローチは、適切な場所、つまり短い接尾辞の挿入を処理しなければならない次の場所に到達することを保証するためです。

最後に、サフィックスツリーの実装を以下に示します。

  1. Java
  2. C++

この「概要」とjogojapanの詳細な解答が、自分自身のサフィックスツリーを実装するのに役立つことを願っています。


私の直感は次のとおりです:

メインループのk回の反復の後、最初のk文字で始まる完全な文字列のすべての接尾辞を含む接尾辞ツリーを構築しました。

最初は、接尾辞ツリーに文字列全体を表す単一のルートノードが含まれていることを意味します(これは0から始まる唯一の接尾辞です)。

len(文字列)反復の後に、すべての接尾辞を含む接尾辞ツリーがあります。

ループ中、キーはアクティブポイントです。 私の推測では、これは、文字列の最初のk文字の適切な接尾辞に対応する接尾辞ツリーの最も深いポイントを表しているということです。 (私は正しいとは、接尾辞が文字列全体ではないことを意味します)。

たとえば、文字 'abcabc'を見たとします。 アクティブポイントは、ツリー内の接尾辞 'abc'に対応するポイントを表します。

アクティブポイントは(origin、first、last)で表されます。 これは、ノードの起点で始まり、文字列[最初から最後まで]の文字を入力することによって、現在あなたが到達したツリー内のポイントにいることを意味します。

新しい文字を追加すると、アクティブな点が既存のツリーにまだ残っているかどうかがわかります。そうであれば、あなたは完了です。それ以外の場合は、新しいノードをアクティブポイントのサフィックスツリーに追加し、次に一致するものにフォールバックして、もう一度チェックする必要があります。

注1:接尾辞ポインタは、各ノードの次の最短一致へのリンクを提供します。

注2:新しいノードとフォールバックを追加するときは、新しいノードに新しい接尾辞ポインタを追加します。このサフィックスポインタの宛先は、短縮されたアクティブポイントのノードになります。このノードはすでに存在するか、このフォールバックループの次の反復で作成されます。

注3:キャノン化部分は、アクティブな点のチェックに時間を節約するだけです。たとえば、常にorigin = 0を使用し、最初と最後に変更したとします。アクティブな点を確認するには、すべての中間ノードに沿って毎回接尾辞ツリーに従わなければなりません。最後のノードからの距離だけを記録することで、このパスに従った結果をキャッシュするのが理にかなっています。

境界変数を「修正する」という意味のコード例を挙げられますか?

健康に関する警告:私はこのアルゴリズムが特に理解しにくいことも発見したので、この直感はすべての重要な詳細で間違っている可能性があることに気づいてください...


@jogojapanのチュートリアルのおかげで、私はPythonでアルゴリズムを実装しました。

@ jogojapanで言及された小さな問題のいくつかは、私が予想していたより洗練されていることが分かり、非常に注意深く扱われる必要があります。 私の実装を十分に堅牢にするには、数日間のコストがかかります(私はそう思います)。 問題と解決策を以下に示します。

  1. Remainder > 0終わるRemainder > 0この状況は、アルゴリズム全体の終わりだけでなく展開の段階でも起こり得ることが分かります。 これが起こると、残りの行為、actnode、actedge、actlengthは変更せずに、現在の展開ステップを終了し、元の文字列の次の文字が現在のパスにあるかどうかによって折り畳んだり展開したりするか、ない。

  2. Leap Over Nodes:サフィックスリンクをたどってアクティブポイントを更新し、active_lengthコンポーネントが新しいactive_nodeでうまく動作しないことがわかります。 私たちは分割したり、葉を挿入するのに適した場所に前進しなければなりません。 この過程は単純はないかもしれません。なぜなら、移動長さと行動はすべて変化し続けます。 ルートノードに戻る必要がある場合、その移動のために行動長さ間違っている可能性があります。 その情報を保持するには追加の変数が必要です。

他の2つの問題は何とか@managonovによって指摘されています

  1. Split Could Degenerateエッジを分割しようとすると、ノード上で分割操作が正しいことがわかります。 その場合、そのノードに新しいリーフを追加するだけで済みます。標準的なエッジ分割操作です。サフィックスリンクがあればそれに対応して保持する必要があります。

  2. 非表示のサフィックスリンク 問題1問題2によって発生する別の特殊なケースがあります。 時には分割のためにいくつかのノードを適切なポイントにホップする必要がある場合もあります。残りの文字列とパスラベルを比較して移動すると、正しいポイントを超える可能性があります。 その場合、サフィックスのリンクは意図せずに無視されます。 これは前進するときの正しい点を思い出すことによって避けることができます。 スプリットノードがすでに存在する場合、または展開中に問題1が発生した場合でも、サフィックスリンクを維持する必要があります。

最後に、私のPythonでの実装は次のとおりです:

ヒント: これは、上記のコードでは、デバッグ中に非常に重要な素朴なツリーの印刷機能が含まれています 。 それは私に多くの時間を節約し、特別なケースを探すのに便利です。







suffix-tree