Download code

Jump to: navigation, search

Back to Suffix_tree_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

SuffixTree.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Suffix_tree_(Java)?oldid=18684
 14 */
 15 
 16 
 17 import java.util.ArrayList;
 18 import java.util.Collection;
 19 import java.util.List;
 20 import org.junit.Test;
 21 
 22 public class SuffixTree {
 23 	@Test
 24 	public void sampleUsage() {
 25 		
 26 		CompactSuffixTree tree = new CompactSuffixTree(new SimpleSuffixTree("bananas"));
 27 		String properties = "rankdir=LR; node[shape=box fillcolor=gray95 style=filled]\n";
 28 		System.out.println("digraph {\n" + properties + tree.root + "}");
 29 
 30 	}
 31 }
 32 abstract class AbstractSuffixTree {
 33 	    
 34 	String text = null;
 35 	SuffixTreeNode root = null;
 36 	int inputAlphabetSize = -1;
 37 	
 38 	AbstractSuffixTree(String text) {
 39 	    if (text.length() > 0 && text.charAt(text.length() - 1) == '$') {
 40 	        this.text = text;
 41 	    } else {
 42 	        this.text = text + "$";
 43 	    }
 44 	}
 45 }
 46 class SimpleSuffixTree extends AbstractSuffixTree {
 47 	   
 48 	public SimpleSuffixTree(String text) {
 49 		super(text);
 50 		constructTree();
 51 	}
 52 	
 53 	private void constructTree() {
 54 	    super.root = new SuffixTreeNode();
 55 	    char[] s = super.text.toCharArray();
 56 	    for (int i = 0; i < s.length; i++) {
 57 	        List<String> suffixList = new ArrayList<String>();
 58 	        for (int k = i; k < s.length; k++) {
 59 	            suffixList.add(s[k] + "");
 60 	        }
 61 	        super.root.addSuffix(suffixList, i+1);
 62 	    }
 63 	}
 64 }
 65 class CompactSuffixTree extends AbstractSuffixTree {
 66 	
 67 	public CompactSuffixTree(SimpleSuffixTree simpleSuffixTree) {
 68 	    super(simpleSuffixTree.text);
 69 	    super.root = compactNodes(simpleSuffixTree.root, 0);
 70 	}
 71 	
 72 	private SuffixTreeNode compactNodes(SuffixTreeNode node, int nodeDepth) {
 73 	    node.nodeDepth = nodeDepth;
 74 	    for (SuffixTreeNode child : node.children) {
 75 	        while (child.children.size() == 1) {
 76 	            SuffixTreeNode grandchild = child.children.iterator().next();
 77 	            child.incomingEdge.label += ", " + grandchild.incomingEdge.label;
 78 	            child.stringDepth += grandchild.incomingEdge.label.length();
 79 	            child.children = grandchild.children;
 80 	            for (SuffixTreeNode grandchild : child.children)
 81 	                grandchild.parent = node;
 82 	        }
 83 	        child = compactNodes(child, nodeDepth + 1);
 84 	    }
 85 	    return node;
 86 	}
 87 }
 88 class SuffixTreeNode {
 89 	
 90 	SuffixTreeEdge incomingEdge = null;
 91 	int nodeDepth = -1;
 92 	int label = -1;
 93 	Collection<SuffixTreeNode> children = null;
 94 	SuffixTreeNode parent = null;
 95 	int stringDepth;
 96 	int id = 0;
 97 	public static int c;
 98 	    
 99 	public SuffixTreeNode(SuffixTreeNode parent, String incomingLabel,
100 	        int depth, int label, int id) {
101 	    children = new ArrayList<SuffixTreeNode>();
102 	    incomingEdge = new SuffixTreeEdge(incomingLabel, label);
103 	    nodeDepth = depth;
104 	    this.label = label;
105 	    this.parent = parent;
106 	    stringDepth = parent.stringDepth + incomingLabel.length();
107 	    this.id = id;
108 	}
109 	public SuffixTreeNode() {
110 	    children = new ArrayList<SuffixTreeNode>();
111 	    nodeDepth = 0;
112 	    label = 0;
113 	}
114 	
115 	public void addSuffix(List<String> suffix, int pathIndex) {
116 	    SuffixTreeNode insertAt = this;
117 	    insertAt = search(this, suffix);
118 	    insert(insertAt, suffix, pathIndex);
119 	}
120 	   
121 	private SuffixTreeNode search(SuffixTreeNode startNode, List<String> suffix) {
122 	    if (suffix.isEmpty()) {
123 	        throw new IllegalArgumentException(
124 	                "Empty suffix. Probably no valid simple suffix tree exists for the input.");
125 	    }
126 	    Collection<SuffixTreeNode> children = startNode.children;
127 	    for (SuffixTreeNode child : children) {
128 	        if (child.incomingEdge.label.equals(suffix.get(0))) {
129 	            suffix.remove(0);
130 	            if (suffix.isEmpty()) {
131 	                return child;
132 	            }
133 	            return search(child, suffix);
134 	        }
135 	    }
136 	    return startNode;
137 	}
138 	
139 	private void insert(SuffixTreeNode insertAt, List<String> suffix,
140 	        int pathIndex) {
141 	    for (String x : suffix) {
142 	        SuffixTreeNode child = new SuffixTreeNode(insertAt, x,
143 	            insertAt.nodeDepth + 1, pathIndex, id);
144 	        insertAt.children.add(child);
145 	        insertAt = child;
146 	    }
147 	}
148 	
149 	public String toString() {
150 	    StringBuilder result = new StringBuilder();
151 	    String incomingLabel = this.isRoot() ? "" : this.incomingEdge.label;
152 	    for (int i = 1; i <= this.nodeDepth; i++)
153 	        result.append("\t");
154 	    if (this.isRoot()) {
155 	        c = 1;
156 	        this.id = 1;
157 	    } else {
158 	        this.id = c;
159 	        result.append(this.parent.id + " -> ");
160 	        result.append(this.id + "[label=\"" + incomingLabel + "\"];\n");
161 	    }
162 	    for (SuffixTreeNode child : children) {
163 	        c++;
164 	        child.id = c;
165 	        result.append(child.toString());
166 	    }
167 	    return result.toString();
168 	}
169 
170 	
171 	public boolean isRoot() {
172 	    return this.parent == null;
173 	}
174 	public boolean isLeaf() {
175 	    return children.size() == 0;
176 	}
177 }
178 class SuffixTreeEdge {
179 	
180 	String label = null;
181 	@SuppressWarnings("unused")
182 	private int branchIndex = -1;
183 
184 	public SuffixTreeEdge(String label, int branchIndex) {
185 	    this.label = label;
186 	    this.branchIndex = branchIndex;
187 	}
188 }


hijacker
hijacker
hijacker
hijacker