string - 配列 - 接頭辞木




Ukkonenのサフィックスツリーアルゴリズム (4)

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の詳細な解答が、自分自身のサフィックスツリーを実装するのに役立つことを願っています。

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

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

参考までに、ここで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


@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での実装は次のとおりです:

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


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

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

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

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

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

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

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

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

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

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

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

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

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


@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);
        }
    });
  }
}






suffix-tree