package de.ugoe.cs.autoquest.usageprofiles; import java.io.Serializable; import java.util.Collection; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.List; import de.ugoe.cs.util.StringTools; import edu.uci.ics.jung.graph.DelegateTree; import edu.uci.ics.jung.graph.Graph; import edu.uci.ics.jung.graph.Tree; /** *
* This class implements a
* Id for object serialization. *
*/ private static final long serialVersionUID = 1L; /** ** Collection of all symbols occuring in the trie. *
*/ private Collection* Reference to the root of the trie. *
*/ private final TrieNode* Contructor. Creates a new Trie. *
*/ public Trie() { rootNode = new TrieNode* Copy-Constructor. Creates a new Trie as the copy of other. The other trie must noch be null. *
* * @param other * Trie that is copied */ public Trie(Trie* Returns a collection of all symbols occuring in the trie. *
* * @return symbols occuring in the trie */ public Collection* Trains the current trie using the given sequence and adds all subsequence of length * {@code maxOrder}. *
* * @param sequence * sequence whose subsequences are added to the trie * @param maxOrder * maximum length of the subsequences added to the trie */ public void train(List* Adds a given subsequence to the trie and increases the counters accordingly. *
* * @param subsequence * subsequence whose counters are increased * @see TrieNode#add(List) */ protected void add(List* Returns the child of the root node associated with the given symbol or creates it if it does * not exist yet. *
* * @param symbol * symbol whose node is required * @return node associated with the symbol * @see TrieNode#getChildCreate(Object) */ protected TrieNode* Returns the child of the root node associated with the given symbol or null if it does not * exist. *
* * @param symbol * symbol whose node is required * @return node associated with the symbol; null if no such node exists * @see TrieNode#getChild(Object) */ protected TrieNode* Returns the number of occurences of the given sequence. *
* * @param sequence * sequence whose number of occurences is required * @return number of occurences of the sequence */ public int getCount(List
* Returns the number of occurences of the given prefix and a symbol that follows it.
* Convenience function to simplify usage of {@link #getCount(List)}.
*
* Searches the trie for a given sequence and returns the node associated with the sequence or * null if no such node is found. *
* * @param sequence * sequence that is searched for * @return node associated with the sequence * @see TrieNode#find(List) */ public TrieNode* Returns a collection of all symbols that follow a given sequence in the trie. In case the * sequence is not found or no symbols follow the sequence the result will be empty. *
* * @param sequence * sequence whose followers are returned * @return symbols following the given sequence * @see TrieNode#getFollowingSymbols() */ public Collection* Returns the longest suffix of the given context that is contained in the tree and whose * children are leaves. *
* * @param context * context whose suffix is searched for * @return longest suffix of the context */ public List* Helper class for graph visualization of a trie. *
* * @author Steffen Herbold * @version 1.0 */ static public class Edge {} /** ** Helper class for graph visualization of a trie. *
* * @author Steffen Herbold * @version 1.0 */ static public class TrieVertex { /** ** Id of the vertex. *
*/ private String id; /** ** Contructor. Creates a new TrieVertex. *
* * @param id * id of the vertex */ protected TrieVertex(String id) { this.id = id; } /** ** Returns the id of the vertex. *
* * @see java.lang.Object#toString() */ @Override public String toString() { return id; } } /** ** Returns a {@link Graph} representation of the trie. *
* * @return {@link Graph} representation of the trie */ protected Tree* Returns the string representation of the root node. *
* * @see TrieNode#toString() * @see java.lang.Object#toString() */ @Override public String toString() { return rootNode.toString(); } /** ** Returns the number of symbols contained in the trie. *
* * @return number of symbols contained in the trie */ public int getNumSymbols() { return knownSymbols.size(); } /** ** Returns the number of trie nodes that are ancestors of a leaf. This is the equivalent to the * number of states a first-order markov model would have. *
*
* @return number of trie nodes that are ancestors of leafs.
*/
public int getNumLeafAncestors() {
List
* Returns the number of trie nodes that are leafs.
*
* Updates the list of known symbols by replacing it with all symbols that are found in the
* child nodes of the root node. This should be the same as all symbols that are contained in
* the trie.
*
* Two Tries are defined as equal, if their {@link #rootNode} are equal.
*