string - suffix tree 구현




평범한 영어로 된 Ukkonen의 접미사 트리 알고리즘 (4)

jogojapan의 답변에서 접미사 트리를 구현하려고 시도했지만 규칙에 사용 된 문구로 인해 일부 경우 작동하지 않았습니다. 또한이 방법을 사용하여 절대적으로 올바른 접미어 트리를 구현 한 관리자는 아무도 없습니다. 아래에서는 jogojapan의 답변에 대한 개요를 작성하여 규칙을 일부 수정합니다. 중요한 접미사 링크를 만드는 것을 잊어 버린 경우에 대해서도 설명 할 것입니다.

사용 된 추가 변수

  1. active point - 트리플 (active_node; active_edge; active_length). 새 접미어 삽입 위치부터 표시해야합니다.
  2. remainder - 명시 적으로 추가해야하는 접미사 수를 표시합니다. 예를 들어, 우리의 단어가 'abcaabca'이고 remainder = 3 인 경우 마지막 접미사 3 개 ( bca , caa)를 처리해야 함을 의미합니다.

내부 노드 의 개념을 사용합시다 - 루트를 제외한 모든 노드와 리프내부 노드 입니다.

관측 1

삽입 할 필요가있는 최종 접미사가 이미 트리에 존재할 때 트리 자체는 전혀 변경되지 않습니다 (우리는 active pointremainder 만 업데이트합니다).

관측 2

어느 시점에서 active_length 가 현재 에지의 길이 ( edge_length )보다 크거나 같으면 edge_lengthactive_length 보다 엄격하게 커질 때까지 active point 이동시킵니다.

이제 규칙을 다시 정의 해 보겠습니다.

규칙 1

액티브 노드 = 루트 에서 삽입 한 후 활성 길이 가 0보다 큰 경우 다음을 수행합니다.

  1. 활성 노드 는 변경되지 않습니다.
  2. 활성 길이 가 감소합니다.
  3. 활성 에지 가 오른쪽으로 이동합니다 (삽입해야하는 다음 접미사의 첫 번째 문자까지).

규칙 2

우리가 새로운 내부 노드를 만들거나 내부 노드 로부터 삽입기를 만들면 이것은 현재 단계에서 첫 번째 SUCH 내부 노드 가 아니며 접미사 링크를 통해 이전 SUCH 노드를 노드와 연결 합니다.

Rule 2 정의는 jogojapan와는 다르다. 새로 생성 된 내부 노드뿐만 아니라 삽입하는 내부 노드도 고려해야한다.

규칙 3

루트 노드가 아닌 활성 노드 에서 삽입 한 후 접미어 링크를 따라 이동하여 활성 노드 를 가리키는 노드 로 설정해야합니다. 접미사 링크가 없으면 활성 노드루트 노드로 설정합니다. 어느 쪽이든, 활성 에지활성 길이 는 변경되지 않습니다.

Rule 3 의이 정의에서 우리는 또한 잎 노드 (분할 노드뿐만 아니라)의 삽입을 고려한다.

그리고 마지막으로 관찰 3 :

트리에 추가하고자하는 심볼이 이미 가장자리에있을 때 Observation 1 에 따르면 우리는 트리를 변경하지 않고 active pointremainder 만 업데이트합니다. 그러나 접미어 링크가 필요한 것으로 표시된 내부 노드 가있는 경우 접미사 링크 를 통해 해당 노드를 현재 active node 와 연결해야합니다.

이런 경우 접미사 링크를 추가하고 cdbdcdc 접미어 트리가 없는 경우 cdddcdc 의 접미어 트리 예제를 살펴 보겠습니다.

  1. 접미사 링크를 통해 노드를 연결 하지 않으면 :

    • 마지막 문자를 추가하기 전에 c :

    • 마지막 문자 c를 추가 한 후 :

  2. 접미사 링크를 통해 노드를 연결하는 경우 :

    • 마지막 문자를 추가하기 전에 c :

    • 마지막 문자 c를 추가 한 후 :

두 번째 경우에는 두 가지 더 많은 접미사 링크가 있습니다. 그러나 이러한 접미사 링크는 정확 하며 파란색 노드에서 빨간색 노드에 이르는 중 하나는 활성 포인트를 사용하는 접근 방식에서 매우 중요 합니다 . 문제는 여기에 접미사 링크를 추가하지 않으면 나중에 트리에 새 문자를 추가 할 때 Rule 3 때문에 일부 노드를 트리에 추가하지 않을 수도 있다는 것입니다. 접미어 링크가 active_node 를 루트에 active_node 합니다.

우리가 마지막 문자를 트리에 추가 할 때, 파란색 노드 (삽입 된 'c' )에서 삽입하기 전에 빨간색 노드가 이미 존재했습니다 . 파란색 노드에서 삽입이 있었기 때문에 접미사 링크가 필요하다고 표시합니다. 그런 다음 활성 지점 접근 방식에 따라 active node 가 빨간색 노드로 설정되었습니다. 그러나 문자 'c' 가 이미 가장자리에 있으므로 빨간색 노드에서 삽입하지 않습니다. 파란색 노드가 접미사 링크없이 남겨 져야 함을 의미합니까? 아니요, 파란색 노드는 접미어 링크를 통해 빨간색 노드와 연결해야합니다. 왜 그게 맞습니까? 능동적 인 접근법을 통해 올바른 위치, 즉 짧은 접미어 삽입을 처리해야하는 다음 장소로 이동할 수 있습니다.

마지막으로 Suffix Tree를 구현 한 내용은 다음과 같습니다.

  1. Java
  2. C++

JogoJapan의 상세한 답변과 결합 된이 "개요"가 누군가 자신의 Suffix Tree를 구현하는 데 도움이되기를 바랍니다.

나는이 시점에서 조금 두껍게 느낀다. 나는 서 픽스 트리 구조에 대해 머리를 감싸려고 하루를 보냈지 만, 수학적 배경이 없기 때문에 수학 기호를 과도하게 사용하기 시작하면서 많은 설명이 나를 피합니다. 내가 찾은 좋은 설명에 가장 근접한 것은 Suffix Trees를 가진 Fast String Searching 이지만, 다양한 점에 대해 글을 쓰고 있으며 알고리즘의 일부 측면은 불명확하다.

스택 오버플로에 대한이 알고리즘에 대한 단계별 설명은 나 외에 많은 다른 사람들에게 매우 중요합니다.

참고로 Ukkonen의 알고리즘에 대한 논문은 다음과 같다. http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

내 기본 이해, 지금까지 :

  • 주어진 문자열 T의 각 접두사 P를 반복 할 필요가있다.
  • 접두사 P의 각 접미사 S를 반복하여 트리에 추가해야합니다.
  • 트리에 접미어 S를 추가하려면 S에서 각 문자를 반복해야합니다. 반복을 반복 할 때 S에서 동일한 문자 집합 C로 시작하는 기존 분기를 걷거나 잠재적으로 하위 노드로 가장자리를 분할합니다. 접미어의 다른 문자에 도달하거나, 일치하는 가장자리가없는 경우. C에 대해 일치하는 가장자리가 발견되지 않으면 C에 대해 새 잎 가장자리가 만들어집니다.

대부분의 설명에서 지적한 것처럼 기본 알고리즘은 O (n 2 ) 인 것처럼 보입니다. 모든 접두사를 단계별로 처리해야하므로 각 접두사에 대한 각 접미사를 단계별로 따라야합니다. Ukkonen의 알고리즘은 그가 사용하는 접미사 포인터 기술 때문에 분명히 독특합니다.하지만 내가 이해하는 데 문제가 있다고 생각 합니다 .

나는 또한 이해하는 데 어려움을 겪고있다.

  • "액티브 포인트"가 언제, 어떻게 사용되고 할당되고 변경되는지
  • 알고리즘의 표준화 측면에서 어떤 일이 일어나고 있는지
  • 왜 내가 본 구현은 사용하고있는 경계 변수를 "고칠 필요가있다"

다음은 완성 된 C # 소스 코드입니다. 그것은 올바르게 작동 할뿐만 아니라 자동 canonization을 지원하고 출력물의보다 멋진 텍스트 그래프를 렌더링합니다. 소스 코드 및 샘플 출력은 다음 위치에 있습니다.

https://gist.github.com/2373868

업데이트 2017-11-04

수년 후에 나는 접미어 트리에 대한 새로운 사용법을 발견하고 JavaScript로 알고리즘을 구현했습니다. 요지가 아래에 있습니다. 버그가 없어야합니다. js 파일에 덤프하고, npm install chalk 은 같은 위치에서 npm install chalknpm install chalk 한 다음 node.js로 실행하여 화려한 출력을 볼 수 있습니다. 디버깅 코드가없는 동일한 GIST에는 버려진 버전이 있습니다.

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


내 직관은 다음과 같습니다.

메인 루프의 k 번 반복 후에는 첫 번째 k 문자로 시작하는 전체 문자열의 모든 접미사를 포함하는 접미어 트리를 구성했습니다.

처음에는 접미사 트리에 전체 문자열을 나타내는 단일 루트 노드가 있음을 의미합니다 (이 접미사는 0에서 시작하는 유일한 접미어 임).

len (문자열) 반복 후에는 모든 접미어가 포함 된 접미어 트리가 있습니다.

루프 동안 키는 활성 포인트입니다. 내 생각에 이것은 문자열의 첫 번째 k 문자의 적절한 접미사에 해당하는 접미어 트리의 가장 깊은 지점을 나타냅니다. (적절한 것은 접미사가 전체 문자열이 될 수 없다는 의미입니다.)

예를 들어 'abcabc'문자를 본 적이 있다고 가정합니다. 활성 점은 접미어 'abc'에 해당하는 트리의 지점을 나타냅니다.

활성 점은 (origin, first, last)로 표시됩니다. 즉, 노드 원점에서 시작하여 문자열 [첫 번째 : 마지막]에있는 문자를 입력하여 현재 트리의 한 지점에 있음을 의미합니다.

새 문자를 추가 할 때 활성 점이 기존 트리에 있는지 여부를 확인합니다. 그럴 경우 당신은 끝났습니다. 그렇지 않으면 활성 노드의 접미어 트리에 새 노드를 추가하고 가장 짧은 다음 일치 항목으로 폴백 한 다음 다시 확인해야합니다.

참고 1 : 접미어 포인터는 각 노드에 대한 다음 가장 짧은 일치에 대한 링크를 제공합니다.

참고 2 : 새 노드를 추가하고 폴백하면 새 노드에 대한 새 접미사 포인터가 추가됩니다. 이 접미사 포인터의 대상은 단축 된 활성 지점의 노드가됩니다. 이 노드는 이미 있거나이 대체 루프의 다음 반복에서 만들어집니다.

참고 3 : 정규화 부분은 활성 지점을 확인하는 데 시간을 절약합니다. 예를 들어 항상 origin = 0을 사용하고 처음과 마지막으로 변경했다고 가정합니다. 활성 지점을 확인하려면 매번 모든 중간 노드를 따라 접미어 트리를 따라야합니다. 마지막 노드로부터의 거리 만 기록하여이 경로를 따르는 결과를 캐시하는 것이 좋습니다.

바운딩 변수를 "수정"한다는 의미의 코드 예제를 줄 수 있습니까?

건강 경고 : 나는 또한이 알고리즘이 특히 이해하기 어렵다는 것을 알았으므로이 직감이 모든 중요한 세부 사항에서 틀릴 것 같다는 것을 알아 주시기 바랍니다 ...


@jogojapan의 튜토리얼을 잘 주셔서 감사합니다. 파이썬으로 알고리즘을 구현했습니다.

@ jogojapan에 언급 된 몇 가지 사소한 문제는 내가 예상 한 것보다 더 정교 해졌으며 매우주의 깊게 다루어 져야합니다. 내 구현을 충분히 견고하게 하려면 며칠이 걸렸습니다 (필자는 생각합니다). 문제 및 해결 방법은 다음과 같습니다.

  1. End with Remainder > 0 이 상황은 전체 알고리즘 의 끝뿐 아니라 펼치기 단계 에서도 발생할 수 있습니다. 이런 일이 생기면 우리는 나머지, actnode, actedge 및 actlength를 변경하지 않고 현재 펼쳐진 단계를 끝내고 원래 문자열의 다음 문자가 현재 경로에 있는지에 따라 접히거나 펼쳐서 다른 단계를 시작하거나 아니.

  2. Leap Over Nodes : 접미사 링크를 따라 가면 활성 지점을 업데이트 한 다음 active_length 구성 요소가 새 active_node와 잘 작동하지 않는다는 사실을 알게됩니다. 우리는 흩어 지거나 잎을 넣을 올바른 곳 으로 나아가 야 합니다. 이 과정은 움직이는 동안 길이와 행동이 계속 변하기 때문에 루트 노드 로 돌아 가야 할 때 행동행동 길이잘못되었을 수 있기 때문에이 과정은 간단하지 않을 수 있습니다. 해당 정보를 유지하려면 추가 변수가 필요합니다.

다른 두 문제는 @managonov에 의해 어떻게 든 지적되었습니다

  1. Split Could Degenerate 가장자리를 분할하려 할 때 때때로 분할 작업이 노드에서 올바르다는 것을 알게됩니다. 이 경우 우리는 노드에 새 잎을 추가하기 만하면됩니다. 표준 가장자리 분할 작업으로 가져와야합니다. 접미어 링크가 있으면 해당 링크를 유지해야합니다.

  2. 숨겨진 접미사 링크 문제 1문제 2에서 발생하는 특별한 경우가 있습니다. 때로는 분할을 위해 올바른 지점으로 여러 노드를 건너 뛰고, 나머지 문자열과 경로 레이블을 비교하여 이동하면 올바른 지점을 능가 할 수 있습니다. 이 경우 접미어 링크는 실수로 무시되어야합니다. 이것은 앞으로 나아갈 때 올바른 시점기억 함으로써 피할 수 있습니다. 분할 노드가 이미 존재하거나 접히는 단계에서 문제 1이 발생하더라도 접미사 링크는 유지되어야합니다.

마지막으로 파이썬 에서의 구현은 다음과 같습니다.

팁 : 위의 코드에는 간단한 트리 인쇄 기능이 포함되어 있으며 디버깅하는 동안 매우 중요 합니다. 그것은 나에게 많은 시간을 절약하고 특별한 경우를 찾는 데 편리합니다.


@ jogojapan 당신은 멋진 설명과 시각화를 가져 왔습니다. 그러나 @makagonov가 언급했듯이 접미사 링크 설정에 관한 몇 가지 규칙이 빠져 있습니다. http://brenden.github.io/ukkonen-animation/ 에서 'aabaaabb'라는 단어를 통해 단계별로 단계별로 나갈 때 잘 보입니다. 10 단계에서 11 단계로 이동하면 노드 5에서 노드 2까지의 접미사 링크가 없지만 활성 점이 갑자기 이동합니다.

@ makagonov는 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