org.sonar.duplications.detector.suffixtree
Class SuffixTree
java.lang.Object
org.sonar.duplications.detector.suffixtree.SuffixTree
public final class SuffixTree
- extends Object
Provides algorithm to construct suffix tree.
Suffix tree for the string S of length n is defined as a tree such that:
- the paths from the root to the leaves have a one-to-one relationship with the suffixes of S,
- edges spell non-empty strings,
- and all internal nodes (except perhaps the root) have at least two children.
Since such a tree does not exist for all strings, S is padded with a terminal symbol not seen in the string (usually denoted $).
This ensures that no suffix is a prefix of another, and that there will be n leaf nodes, one for each of the n suffixes of S.
Since all internal non-root nodes are branching, there can be at most n − 1 such nodes, and n + (n − 1) + 1 = 2n nodes in total.
All internal nodes and leaves have incoming edge, so number of edges equal to number of leaves plus number of inner nodes,
thus at most 2n - 1.
Construction takes O(n) time.
This implementation was adapted from Java-port of
Mark Nelson's C++ implementation of Ukkonen's algorithm.
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
create
public static SuffixTree create(Text text)
symbolAt
public Object symbolAt(int index)
getRootNode
public Node getRootNode()
Copyright © 2009-2012 SonarSource. All Rights Reserved.