public class UkkonenSuffixTree
extends java.lang.Object
Constructor and Description |
---|
UkkonenSuffixTree(int encodingLength,
java.lang.String sequence) |
Modifier and Type | Method and Description |
---|---|
void |
findLeftDiverseNodes()
Assess the left diversity (property) of nodes
A node v is called left diverse if at least two leaves in v's subtree
have different left symbols; So, check for the leftSymbolSet to be of at
least size 2; If the node qualifies to be leftDiverse, then set all its
ancestors also as leftDiverse;
|
java.util.HashMap<java.util.TreeSet<java.lang.String>,java.util.TreeSet<java.lang.String>> |
getComplexAlphabetTandemRepeatMap() |
java.util.HashSet<java.lang.String> |
getComplexTandemRepeats() |
java.util.HashSet<java.lang.String> |
getFilteredMaximalRepeats() |
java.util.HashSet<java.lang.String> |
getFilteredNearSuperMaximalRepeats() |
java.util.HashSet<java.lang.String> |
getFilteredSuperMaximalRepeats() |
java.util.ArrayList<org.processmining.plugins.tracealignment.util.SuffixNode> |
getLeaves(org.processmining.plugins.tracealignment.util.SuffixNode node) |
java.util.ArrayList<org.processmining.plugins.tracealignment.util.SuffixNode> |
getLeftDiverseNodes(org.processmining.plugins.tracealignment.util.SuffixNode node) |
int[] |
getMatches(java.lang.String searchString) |
java.util.HashSet<java.lang.String> |
getMaximalRepeats()
Get the maximal repeat strings (not necessarily tandem) in the input
string for which the suffix tree is constructed
The algorithm is of Gusfield's;
Determine the maximal repeats; A string alpha labeling a path to a node v
of T is a maximal repeat iff v is leftDiverse Retrieve all
leftDiverseNodes and print the paths leading to that node from the root
The path information is stored in the class attributes pathPosition and
edgeLabelEnd;
Returns a HashSet of maximal Repeats;
Assumes that the parent method calling this would have invoked
findLeftDiverseNodes();
|
java.util.HashSet<java.lang.String> |
getNearSuperMaximalRepeats()
Find NearSuperMaximal Repeats; A left diverse internal node v represents
a near super maximal repeat alpha if and only if one of v's children is a
leaf and its left character is the left character of no other leaf below
v
Assumes that the parent method calling this would have already invoked
findLeftDiverseNodes();
|
java.util.HashMap<java.util.TreeSet<java.lang.String>,java.util.TreeSet<java.lang.String>> |
getPrimitiveTandemRepeats()
Simple Cases
|
java.util.HashSet<java.lang.String> |
getSuperMaximalRepeats()
Find SuperMaximal Repeats; A left diverse internal node v represents a
super maximal repeat alpha if and only if all of v's children are leaves,
and each has a distinct left character
Assumes that the parent method calling this would have already invoked
findLeftDiverseNodes();
|
java.util.TreeSet<java.lang.String> |
getTandemRepeats() |
void |
LZDecomposition() |
static void |
main(java.lang.String[] args) |
int |
noMatches(java.lang.String searchString) |
<T> void |
printArray(T[] arrayT) |
void |
printTree() |
void |
singleStringTest() |
public UkkonenSuffixTree(int encodingLength, java.lang.String sequence)
public void printTree()
public java.util.ArrayList<org.processmining.plugins.tracealignment.util.SuffixNode> getLeaves(org.processmining.plugins.tracealignment.util.SuffixNode node) throws java.lang.StackOverflowError
java.lang.StackOverflowError
public int noMatches(java.lang.String searchString) throws java.lang.StackOverflowError
java.lang.StackOverflowError
public int[] getMatches(java.lang.String searchString)
public void findLeftDiverseNodes()
public java.util.ArrayList<org.processmining.plugins.tracealignment.util.SuffixNode> getLeftDiverseNodes(org.processmining.plugins.tracealignment.util.SuffixNode node)
public java.util.HashSet<java.lang.String> getMaximalRepeats()
public java.util.HashSet<java.lang.String> getFilteredMaximalRepeats()
public java.util.HashSet<java.lang.String> getSuperMaximalRepeats()
public java.util.HashSet<java.lang.String> getFilteredSuperMaximalRepeats()
public java.util.HashSet<java.lang.String> getNearSuperMaximalRepeats()
public java.util.HashSet<java.lang.String> getFilteredNearSuperMaximalRepeats()
public void LZDecomposition()
public java.util.TreeSet<java.lang.String> getTandemRepeats()
public java.util.HashMap<java.util.TreeSet<java.lang.String>,java.util.TreeSet<java.lang.String>> getPrimitiveTandemRepeats()
public java.util.HashSet<java.lang.String> getComplexTandemRepeats()
public java.util.HashMap<java.util.TreeSet<java.lang.String>,java.util.TreeSet<java.lang.String>> getComplexAlphabetTandemRepeatMap()
public static void main(java.lang.String[] args)
public void singleStringTest()
public <T> void printArray(T[] arrayT)