Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -11,7 +12,7 @@ /** *

- * Implements a Deterministic Finite Automata (DFA) capable of random session - * generation. It is a special case of a first-order Markov model, where the - * transition probability is equally high for all following states. + * Implements a Deterministic Finite Automata (DFA) capable of random session generation. It is a + * special case of a first-order Markov model, where the transition probability is equally high for + * all following states. *

* @@ -21,60 +22,60 @@ public class DeterministicFiniteAutomaton extends FirstOrderMarkovModel { - /** - *

- * Id for object serialization. - *

- */ - private static final long serialVersionUID = 1L; + /** + *

+ * Id for object serialization. + *

+ */ + private static final long serialVersionUID = 1L; - /** - *

- * Constructor. Creates a new DeterministicFiniteAutomaton. - *

- * - * @param r - * random number generator used by probabilistic methods of the - * class - */ - public DeterministicFiniteAutomaton(Random r) { - super(r); - } + /** + *

+ * Constructor. Creates a new DeterministicFiniteAutomaton. + *

+ * + * @param r + * random number generator used by probabilistic methods of the class + */ + public DeterministicFiniteAutomaton(Random r) { + super(r); + } - /** - *

- * Calculates the proability of the next state. Each of the following states - * in the automaton is equally probable. - *

- * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, - * de.ugoe.cs.quest.eventcore.Event) - */ - @Override - public double getProbability(List context, - Event symbol) { - if( context==null ) { - throw new InvalidParameterException("context must not be null"); - } - if( symbol==null ) { - throw new InvalidParameterException("symbol must not be null"); - } - double result = 0.0d; + /** + *

+ * Calculates the proability of the next state. Each of the following states in the automaton is + * equally probable. + *

+ * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, + * de.ugoe.cs.quest.eventcore.Event) + */ + @Override + public double getProbability(List context, Event symbol) { + if (context == null) { + throw new InvalidParameterException("context must not be null"); + } + if (symbol == null) { + throw new InvalidParameterException("symbol must not be null"); + } + double result = 0.0d; - List contextCopy; - if (context.size() >= trieOrder) { - contextCopy = new LinkedList(context.subList( - context.size() - trieOrder + 1, context.size())); - } else { - contextCopy = new LinkedList(context); - } + List contextCopy; + if (context.size() >= trieOrder) { + contextCopy = + new LinkedList(context.subList(context.size() - trieOrder + 1, + context.size())); + } + else { + contextCopy = new LinkedList(context); + } - Collection followers = trie.getFollowingSymbols(contextCopy); + Collection followers = trie.getFollowingSymbols(contextCopy); - if (followers.size() != 0 && followers.contains(symbol)) { - result = 1.0d / followers.size(); - } + if (followers.size() != 0 && followers.contains(symbol)) { + result = 1.0d / followers.size(); + } - return result; - } + return result; + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -18,8 +19,7 @@ /** *

- * Implements first-order Markov models. The implementation is based on - * {@link HighOrderMarkovModel} and restricts the Markov order to 1. In - * comparison to {@link HighOrderMarkovModel}, more calculations are possible - * with first-order models, e.g., the calculation of the entropy ( + * Implements first-order Markov models. The implementation is based on {@link HighOrderMarkovModel} + * and restricts the Markov order to 1. In comparison to {@link HighOrderMarkovModel}, more + * calculations are possible with first-order models, e.g., the calculation of the entropy ( * {@link #calcEntropy()}). *

@@ -28,237 +28,229 @@ * @version 1.0 */ -public class FirstOrderMarkovModel extends HighOrderMarkovModel implements - IDotCompatible { - - /** - *

- * Id for object serialization. - *

- */ - private static final long serialVersionUID = 1L; - - /** - *

- * Maximum number of iterations when calculating the stationary distribution - * as the limit of multiplying the transmission matrix with itself. - *

- */ - final static int MAX_STATDIST_ITERATIONS = 1000; - - /** - *

- * Constructor. Creates a new FirstOrderMarkovModel. - *

- * - * @param r - * random number generator used by probabilistic methods of the - * class - */ - public FirstOrderMarkovModel(Random r) { - super(1, r); - } - - /** - *

- * Generates the transmission matrix of the Markov model. - *

- * - * @return transmission matrix - */ - private Matrix getTransmissionMatrix() { - List knownSymbols = new ArrayList( - trie.getKnownSymbols()); - int numStates = knownSymbols.size(); - Matrix transmissionMatrix = new Matrix(numStates, numStates); - - for (int i = 0; i < numStates; i++) { - Event currentSymbol = knownSymbols.get(i); - List context = new ArrayList(); - context.add(currentSymbol); - for (int j = 0; j < numStates; j++) { - Event follower = knownSymbols.get(j); - double prob = getProbability(context, follower); - transmissionMatrix.set(i, j, prob); - } - } - return transmissionMatrix; - } - - /** - *

- * Calculates the entropy of the model. To make it possible that the model - * is stationary, a transition from {@link Event#ENDEVENT} to - * {@link Event#STARTEVENT} is added. - *

- * - * @return entropy of the model or NaN if it could not be calculated - */ - public double calcEntropy() { - Matrix transmissionMatrix = getTransmissionMatrix(); - List knownSymbols = new ArrayList( - trie.getKnownSymbols()); - int numStates = knownSymbols.size(); - - List startIndexList = new LinkedList(); - List endIndexList = new LinkedList(); - for( int i=0 ; i 1) { - stationaryMatrix = stationaryMatrix.times(stationaryMatrix); - rank = stationaryMatrix.rank(); - iter++; - } - - if (rank != 1) { - Console.traceln("rank: " + rank); - Console.printerrln("Unable to calculate stationary distribution."); - return Double.NaN; - } - - double entropy = 0.0; - for (int i = 0; i < numStates; i++) { - for (int j = 0; j < numStates; j++) { - if (transmissionMatrix.get(i, j) != 0 && transmissionMatrix.get(i, j)!=1) { - double tmp = stationaryMatrix.get(0, i); - tmp *= transmissionMatrix.get(i, j); - tmp *= Math.log(transmissionMatrix.get(i, j)) / Math.log(2); - entropy -= tmp; - } - } - } - return entropy; - } - - /** - *

- * The dot represenation of {@link FirstOrderMarkovModel}s is its graph - * representation with the states as nodes and directed edges weighted with - * transition probabilities. - *

- * - * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() - */ - @Override - public String getDotRepresentation() { - StringBuilder stringBuilder = new StringBuilder(); - stringBuilder.append("digraph model {" + StringTools.ENDLINE); - - List knownSymbols = new ArrayList( - trie.getKnownSymbols()); - for (Event symbol : knownSymbols) { - final String thisSaneId = symbol.getId().replace("\"", "\\\"") - .replaceAll("[\r\n]", ""); - stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " [label=\"" - + thisSaneId + "\"];" + StringTools.ENDLINE); - List context = new ArrayList(); - context.add(symbol); - Collection followers = trie.getFollowingSymbols(context); - for (Event follower : followers) { - stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " -> " - + knownSymbols.indexOf(follower) + " "); - stringBuilder.append("[label=\"" - + getProbability(context, follower) + "\"];" - + StringTools.ENDLINE); - } - } - stringBuilder.append('}' + StringTools.ENDLINE); - return stringBuilder.toString(); - } - - /** - *

- * Returns a {@link Graph} representation of the model with the states as - * nodes and directed edges weighted with transition probabilities. - *

- * - * @return {@link Graph} of the model - */ - public Graph getGraph() { - Graph graph = new SparseMultigraph(); - - List knownSymbols = new ArrayList( - trie.getKnownSymbols()); - - for (Event symbol : knownSymbols) { - String from = symbol.getId(); - List context = new ArrayList(); - context.add(symbol); - - Collection followers = trie.getFollowingSymbols(context); - - for (Event follower : followers) { - String to = follower.getId(); - MarkovEdge prob = new MarkovEdge(getProbability(context, - follower)); - graph.addEdge(prob, from, to, EdgeType.DIRECTED); - } - } - return graph; - } - - /** - * Inner class used for the {@link Graph} representation of the model. - * - * @author Steffen Herbold - * @version 1.0 - */ - static public class MarkovEdge { - /** - *

- * Weight of the edge, i.e., its transition probability. - *

- */ - double weight; - - /** - *

- * Constructor. Creates a new MarkovEdge. - *

- * - * @param weight - * weight of the edge, i.e., its transition probability - */ - MarkovEdge(double weight) { - this.weight = weight; - } - - /** - *

- * The weight of the edge as {@link String}. - *

- */ - public String toString() { - return "" + weight; - } - } +public class FirstOrderMarkovModel extends HighOrderMarkovModel implements IDotCompatible { + + /** + *

+ * Id for object serialization. + *

+ */ + private static final long serialVersionUID = 1L; + + /** + *

+ * Maximum number of iterations when calculating the stationary distribution as the limit of + * multiplying the transmission matrix with itself. + *

+ */ + final static int MAX_STATDIST_ITERATIONS = 1000; + + /** + *

+ * Constructor. Creates a new FirstOrderMarkovModel. + *

+ * + * @param r + * random number generator used by probabilistic methods of the class + */ + public FirstOrderMarkovModel(Random r) { + super(1, r); + } + + /** + *

+ * Generates the transmission matrix of the Markov model. + *

+ * + * @return transmission matrix + */ + private Matrix getTransmissionMatrix() { + List knownSymbols = new ArrayList(trie.getKnownSymbols()); + int numStates = knownSymbols.size(); + Matrix transmissionMatrix = new Matrix(numStates, numStates); + + for (int i = 0; i < numStates; i++) { + Event currentSymbol = knownSymbols.get(i); + List context = new ArrayList(); + context.add(currentSymbol); + for (int j = 0; j < numStates; j++) { + Event follower = knownSymbols.get(j); + double prob = getProbability(context, follower); + transmissionMatrix.set(i, j, prob); + } + } + return transmissionMatrix; + } + + /** + *

+ * Calculates the entropy of the model. To make it possible that the model is stationary, a + * transition from {@link Event#ENDEVENT} to {@link Event#STARTEVENT} is added. + *

+ * + * @return entropy of the model or NaN if it could not be calculated + */ + public double calcEntropy() { + Matrix transmissionMatrix = getTransmissionMatrix(); + List knownSymbols = new ArrayList(trie.getKnownSymbols()); + int numStates = knownSymbols.size(); + + List startIndexList = new LinkedList(); + List endIndexList = new LinkedList(); + for (int i = 0; i < knownSymbols.size(); i++) { + String id = knownSymbols.get(i).getId(); + if (id.equals(Event.STARTEVENT.getId()) || + id.contains(Event.STARTEVENT.getId() + "-=-")) + { + startIndexList.add(i); + } + if (id.equals(Event.ENDEVENT.getId()) || id.contains("-=-" + Event.ENDEVENT.getId())) { + endIndexList.add(i); + } + } + + if (startIndexList.isEmpty()) { + Console + .printerrln("Error calculating entropy. Initial state of markov chain not found."); + return Double.NaN; + } + if (endIndexList.isEmpty()) { + Console.printerrln("Error calculating entropy. End state of markov chain not found."); + return Double.NaN; + } + for (Integer i : endIndexList) { + for (Integer j : startIndexList) { + transmissionMatrix.set(i, j, 1); + } + } + + // Calculate stationary distribution by raising the power of the + // transmission matrix. + // The rank of the matrix should fall to 1 and each two should be the + // vector of the stationory distribution. + int iter = 0; + int rank = transmissionMatrix.rank(); + Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone(); + while (iter < MAX_STATDIST_ITERATIONS && rank > 1) { + stationaryMatrix = stationaryMatrix.times(stationaryMatrix); + rank = stationaryMatrix.rank(); + iter++; + } + + if (rank != 1) { + Console.traceln("rank: " + rank); + Console.printerrln("Unable to calculate stationary distribution."); + return Double.NaN; + } + + double entropy = 0.0; + for (int i = 0; i < numStates; i++) { + for (int j = 0; j < numStates; j++) { + if (transmissionMatrix.get(i, j) != 0 && transmissionMatrix.get(i, j) != 1) { + double tmp = stationaryMatrix.get(0, i); + tmp *= transmissionMatrix.get(i, j); + tmp *= Math.log(transmissionMatrix.get(i, j)) / Math.log(2); + entropy -= tmp; + } + } + } + return entropy; + } + + /** + *

+ * The dot represenation of {@link FirstOrderMarkovModel}s is its graph representation with the + * states as nodes and directed edges weighted with transition probabilities. + *

+ * + * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() + */ + @Override + public String getDotRepresentation() { + StringBuilder stringBuilder = new StringBuilder(); + stringBuilder.append("digraph model {" + StringTools.ENDLINE); + + List knownSymbols = new ArrayList(trie.getKnownSymbols()); + for (Event symbol : knownSymbols) { + final String thisSaneId = symbol.getId().replace("\"", "\\\"").replaceAll("[\r\n]", ""); + stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " [label=\"" + thisSaneId + + "\"];" + StringTools.ENDLINE); + List context = new ArrayList(); + context.add(symbol); + Collection followers = trie.getFollowingSymbols(context); + for (Event follower : followers) { + stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " -> " + + knownSymbols.indexOf(follower) + " "); + stringBuilder.append("[label=\"" + getProbability(context, follower) + "\"];" + + StringTools.ENDLINE); + } + } + stringBuilder.append('}' + StringTools.ENDLINE); + return stringBuilder.toString(); + } + + /** + *

+ * Returns a {@link Graph} representation of the model with the states as nodes and directed + * edges weighted with transition probabilities. + *

+ * + * @return {@link Graph} of the model + */ + public Graph getGraph() { + Graph graph = new SparseMultigraph(); + + List knownSymbols = new ArrayList(trie.getKnownSymbols()); + + for (Event symbol : knownSymbols) { + String from = symbol.getId(); + List context = new ArrayList(); + context.add(symbol); + + Collection followers = trie.getFollowingSymbols(context); + + for (Event follower : followers) { + String to = follower.getId(); + MarkovEdge prob = new MarkovEdge(getProbability(context, follower)); + graph.addEdge(prob, from, to, EdgeType.DIRECTED); + } + } + return graph; + } + + /** + * Inner class used for the {@link Graph} representation of the model. + * + * @author Steffen Herbold + * @version 1.0 + */ + static public class MarkovEdge { + /** + *

+ * Weight of the edge, i.e., its transition probability. + *

+ */ + double weight; + + /** + *

+ * Constructor. Creates a new MarkovEdge. + *

+ * + * @param weight + * weight of the edge, i.e., its transition probability + */ + MarkovEdge(double weight) { + this.weight = weight; + } + + /** + *

+ * The weight of the edge as {@link String}. + *

+ */ + public String toString() { + return "" + weight; + } + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -19,69 +20,67 @@ public class HighOrderMarkovModel extends TrieBasedModel { - /** - *

- * Id for object serialization. - *

- */ - private static final long serialVersionUID = 1L; + /** + *

+ * Id for object serialization. + *

+ */ + private static final long serialVersionUID = 1L; - /** - *

- * Constructor. Creates a new HighOrderMarkovModel with a defined Markov - * order. - *

- * - * @param maxOrder - * Markov order of the model - * @param r - * random number generator used by probabilistic methods of the - * class - */ - public HighOrderMarkovModel(int maxOrder, Random r) { - super(maxOrder, r); - } + /** + *

+ * Constructor. Creates a new HighOrderMarkovModel with a defined Markov order. + *

+ * + * @param maxOrder + * Markov order of the model + * @param r + * random number generator used by probabilistic methods of the class + */ + public HighOrderMarkovModel(int maxOrder, Random r) { + super(maxOrder, r); + } - /** - *

- * Calculates the probability of the next Event being symbol based on the - * order of the Markov model. The order is defined in the constructor - * {@link #HighOrderMarkovModel(int, Random)}. - *

- * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, - * de.ugoe.cs.quest.eventcore.Event) - */ - @Override - public double getProbability(List context, - Event symbol) { - if (context == null) { - throw new InvalidParameterException("context must not be null"); - } - if (symbol == null) { - throw new InvalidParameterException("symbol must not be null"); - } - double result = 0.0d; + /** + *

+ * Calculates the probability of the next Event being symbol based on the order of the Markov + * model. The order is defined in the constructor {@link #HighOrderMarkovModel(int, Random)}. + *

+ * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, + * de.ugoe.cs.quest.eventcore.Event) + */ + @Override + public double getProbability(List context, Event symbol) { + if (context == null) { + throw new InvalidParameterException("context must not be null"); + } + if (symbol == null) { + throw new InvalidParameterException("symbol must not be null"); + } + double result = 0.0d; - List contextCopy; - if (context.size() >= trieOrder) { - contextCopy = new LinkedList(context.subList( - context.size() - trieOrder + 1, context.size())); - } else { - contextCopy = new LinkedList(context); - } + List contextCopy; + if (context.size() >= trieOrder) { + contextCopy = + new LinkedList(context.subList(context.size() - trieOrder + 1, + context.size())); + } + else { + contextCopy = new LinkedList(context); + } - Collection followers = trie.getFollowingSymbols(contextCopy); - int sumCountFollowers = 0; // N(s\sigma') - for (Event follower : followers) { - sumCountFollowers += trie.getCount(contextCopy, follower); - } + Collection followers = trie.getFollowingSymbols(contextCopy); + int sumCountFollowers = 0; // N(s\sigma') + for (Event follower : followers) { + sumCountFollowers += trie.getCount(contextCopy, follower); + } - int countSymbol = trie.getCount(contextCopy, symbol); - if (sumCountFollowers != 0) { - result = ((double) countSymbol / sumCountFollowers); - } + int countSymbol = trie.getCount(contextCopy, symbol); + if (sumCountFollowers != 0) { + result = ((double) countSymbol / sumCountFollowers); + } - return result; - } + return result; + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java (revision 559) @@ -1,8 +1,9 @@ + package de.ugoe.cs.quest.usageprofiles; /** *

- * Models implementing this interface provide a graph representation of - * themselves as a {@link String} with Dot syntax. + * Models implementing this interface provide a graph representation of themselves as a + * {@link String} with Dot syntax. *

* @@ -12,11 +13,11 @@ public interface IDotCompatible { - /** - *

- * Returns a Dot representation of the model. - *

- * - * @return string with Dot syntax that describes the model. - */ - public abstract String getDotRepresentation(); + /** + *

+ * Returns a Dot representation of the model. + *

+ * + * @return string with Dot syntax that describes the model. + */ + public abstract String getDotRepresentation(); } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -5,6 +6,6 @@ /** *

- * This interface defines basic functions for classes that implement a memory - * about the recent events of a sequences. + * This interface defines basic functions for classes that implement a memory about the recent + * events of a sequences. *

* @@ -17,24 +18,24 @@ public interface IMemory { - /** - * Adds an element to the end of the memory. - * - * @param element - * Element to be added. - */ - public void add(T element); + /** + * Adds an element to the end of the memory. + * + * @param element + * Element to be added. + */ + public void add(T element); - /** - *

- * Returns the last num memorized elements. If the history is - * shorter than num, the length of the returned - * {@link java.util.List} may be less than num. - *

- * - * @param num - * Number of states from the end of the memory to be returned. - * @return {@link java.util.List} of memorized elements. - */ - public List getLast(int num); + /** + *

+ * Returns the last num memorized elements. If the history is shorter than + * num, the length of the returned {@link java.util.List} may be less than + * num. + *

+ * + * @param num + * Number of states from the end of the memory to be returned. + * @return {@link java.util.List} of memorized elements. + */ + public List getLast(int num); } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -18,177 +19,163 @@ public interface IStochasticProcess extends Serializable { - /** - *

- * Returns the probability, that the next event is {@code symbol} given the - * last events are {@code context}. The last element of {@code context} is - * the most recent in the history, the first element is the oldest. - *

- * - * @param context - * recently observed symbols - * @param symbol - * event for which the probability is calculated - * @return probabilty the {@code symbol} is the next event, given the last - * events {@code context} - * @throws InvalidParameterException - * thrown if context or symbol is null - */ - double getProbability(List context, Event symbol); + /** + *

+ * Returns the probability, that the next event is {@code symbol} given the last events are + * {@code context}. The last element of {@code context} is the most recent in the history, the + * first element is the oldest. + *

+ * + * @param context + * recently observed symbols + * @param symbol + * event for which the probability is calculated + * @return probabilty the {@code symbol} is the next event, given the last events + * {@code context} + * @throws InvalidParameterException + * thrown if context or symbol is null + */ + double getProbability(List context, Event symbol); - /** - *

- * Returns the probabilitiy that a given sequence is generated by the - * stochastic process. - *

- * - * @param sequence - * sequences of which the probability is calculated - * @return probability of the sequences; 1.0 if sequence is empty or null - * @throws InvalidParameterException - * thrown if sequence is null - */ - double getProbability(List sequence); + /** + *

+ * Returns the probabilitiy that a given sequence is generated by the stochastic process. + *

+ * + * @param sequence + * sequences of which the probability is calculated + * @return probability of the sequences; 1.0 if sequence is empty or null + * @throws InvalidParameterException + * thrown if sequence is null + */ + double getProbability(List sequence); - /** - *

- * Generates a random sequence of events. The sequence starts with - * {@link Event#STARTEVENT} and finishes with {@link Event#ENDEVENT}. - *

- * - * @return randomly generated sequence - */ - public List randomSequence(); + /** + *

+ * Generates a random sequence of events. The sequence starts with {@link Event#STARTEVENT} and + * finishes with {@link Event#ENDEVENT}. + *

+ * + * @return randomly generated sequence + */ + public List randomSequence(); - /** - *

- * Generates a random sequence of events. The sequence starts with - * {@link Event#STARTEVENT} and finishes with - *

    - *
  • {@link Event#ENDEVENT} if validEnd==true.
    • - *
  • b) if a generated sequences reaches {@link Event#ENDEVENT} before - * maxLength, the sequence finishes and is shorter than maxLenght. - * Otherwise, the sequence finishes as soon as maxLength is reached and the - * final event of the sequence must not be {@link Event#ENDEVENT}.
    • - *
- *

- * - * @param maxLength - * maximum length of the generated sequence - * @param validEnd - * if true, only sequences that finish with - * {@link Event#ENDEVENT} are generated - * @return randomly generated sequence - * - */ - public List randomSequence(int maxLength, - boolean validEnd); + /** + *

+ * Generates a random sequence of events. The sequence starts with {@link Event#STARTEVENT} and + * finishes with + *

    + *
  • {@link Event#ENDEVENT} if validEnd==true.
    • + *
  • b) if a generated sequences reaches {@link Event#ENDEVENT} before maxLength, the sequence + * finishes and is shorter than maxLenght. Otherwise, the sequence finishes as soon as maxLength + * is reached and the final event of the sequence must not be {@link Event#ENDEVENT}.
    • + *
+ *

+ * + * @param maxLength + * maximum length of the generated sequence + * @param validEnd + * if true, only sequences that finish with {@link Event#ENDEVENT} are generated + * @return randomly generated sequence + * + */ + public List randomSequence(int maxLength, boolean validEnd); - /** - *

- * Generates all sequences of a given length are possible, i.e., have a - * positive probability.
- * All states are used as possible starting states. - *

- * - * @param length - * length of the generated sequences - * @return generated sequences - * @see #generateSequences(int, boolean) - * @throws InvalidParameterException - * thrown if length is less than or equal to 0 - */ - public Collection> generateSequences(int length); + /** + *

+ * Generates all sequences of a given length are possible, i.e., have a positive probability.
+ * All states are used as possible starting states. + *

+ * + * @param length + * length of the generated sequences + * @return generated sequences + * @see #generateSequences(int, boolean) + * @throws InvalidParameterException + * thrown if length is less than or equal to 0 + */ + public Collection> generateSequences(int length); - /** - *

- * Generates all sequences of given length that can are possible, i.e., have - * positive probability.
- * If {@code fromStart==true}, all generated sequences start in - * {@link Event#STARTEVENT}. Otherwise this method is the same as - * {@link #generateSequences(int)}. - *

- * - * @param length - * length of the generated sequences - * @param fromStart - * if true, all generated sequences start with - * {@link Event#STARTEVENT} - * @return generated sequences - * @throws InvalidParameterException - * thrown if length is less than or equal to 0 - */ - public Collection> generateSequences(int length, - boolean fromStart); + /** + *

+ * Generates all sequences of given length that can are possible, i.e., have positive + * probability.
+ * If {@code fromStart==true}, all generated sequences start in {@link Event#STARTEVENT}. + * Otherwise this method is the same as {@link #generateSequences(int)}. + *

+ * + * @param length + * length of the generated sequences + * @param fromStart + * if true, all generated sequences start with {@link Event#STARTEVENT} + * @return generated sequences + * @throws InvalidParameterException + * thrown if length is less than or equal to 0 + */ + public Collection> generateSequences(int length, boolean fromStart); - /** - *

- * Generates all sequences starting with {@link Event#STARTEVENT} and - * finishing with {@link Event#ENDEVENT} of a given length. It is possible - * that no such sequence exists with the defined length and the returned set - * is empty. If {@code length} is less than 2 the returned set is always - * empty. - *

- * - * @param length - * @return generated sequences - * @throws InvalidParameterException - * thrown if length is less than or equal to 0 - */ - public Collection> generateValidSequences( - int length); + /** + *

+ * Generates all sequences starting with {@link Event#STARTEVENT} and finishing with + * {@link Event#ENDEVENT} of a given length. It is possible that no such sequence exists with + * the defined length and the returned set is empty. If {@code length} is less than 2 the + * returned set is always empty. + *

+ * + * @param length + * @return generated sequences + * @throws InvalidParameterException + * thrown if length is less than or equal to 0 + */ + public Collection> generateValidSequences(int length); - /** - *

- * Returns the number of states known by the stochastic process, i.e., the - * size of its alphabet. - *

- * - * @return number of states - */ - public int getNumSymbols(); + /** + *

+ * Returns the number of states known by the stochastic process, i.e., the size of its alphabet. + *

+ * + * @return number of states + */ + public int getNumSymbols(); - /** - *

- * Returns a string representation of all known states. - *

- * - * @return string representation for all known states - */ - public String[] getSymbolStrings(); + /** + *

+ * Returns a string representation of all known states. + *

+ * + * @return string representation for all known states + */ + public String[] getSymbolStrings(); - /** - *

- * Returns the number of states the process would have if it would be - * flattened through state-splitting to a first-order Markov model. - *

- *

- * If it is not possible to flatten the model, -1 is returned. - *

- * - * @return number of states an equivalent FOM would have; -1 if not - * available - */ - public int getNumFOMStates(); + /** + *

+ * Returns the number of states the process would have if it would be flattened through + * state-splitting to a first-order Markov model. + *

+ *

+ * If it is not possible to flatten the model, -1 is returned. + *

+ * + * @return number of states an equivalent FOM would have; -1 if not available + */ + public int getNumFOMStates(); - /** - *

- * Returns the number of transitions the process would have if it would be - * flattened through state-splitting to a first-order Markov model. - *

- * - * @return number of transitions an equivalent FOM would have; -1 if not - * available - */ - public int getNumTransitions(); + /** + *

+ * Returns the number of transitions the process would have if it would be flattened through + * state-splitting to a first-order Markov model. + *

+ * + * @return number of transitions an equivalent FOM would have; -1 if not available + */ + public int getNumTransitions(); - /** - *

- * Returns all states known by the stochastic process, i.e., its - * {@link Event}s. - *

- * - * @return events known by the process - */ - public Collection getEvents(); + /** + *

+ * Returns all states known by the stochastic process, i.e., its {@link Event}s. + *

+ * + * @return events known by the process + */ + public Collection getEvents(); } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -7,7 +8,7 @@ /** *

- * Implements a round-trip buffered memory of a specified length that can be - * used to remember the recent history. Every event that happend longer ago than - * the length of the memory is forgotten, hence the memory is incomplete. + * Implements a round-trip buffered memory of a specified length that can be used to remember the + * recent history. Every event that happend longer ago than the length of the memory is forgotten, + * hence the memory is incomplete. *

* @@ -20,76 +21,75 @@ public class IncompleteMemory implements IMemory { - /** - *

- * Maximum length of the memory. - *

- */ - private int length; + /** + *

+ * Maximum length of the memory. + *

+ */ + private int length; - /** - *

- * Internal storage of the history. - *

- */ - private List history; + /** + *

+ * Internal storage of the history. + *

+ */ + private List history; - /** - *

- * Constructor. Creates a new IncompleteMemory. - *

- * - * @param length - * number of recent events that are remembered - * @throws InvalidParameterException - * This exception is thrown if the length is smaller than 1 - */ - public IncompleteMemory(int length) { - if (length < 1) { - throw new InvalidParameterException( - "Length of IncompleteMemory must be at least 1."); - } - this.length = length; - history = new LinkedList(); - } + /** + *

+ * Constructor. Creates a new IncompleteMemory. + *

+ * + * @param length + * number of recent events that are remembered + * @throws InvalidParameterException + * This exception is thrown if the length is smaller than 1 + */ + public IncompleteMemory(int length) { + if (length < 1) { + throw new InvalidParameterException("Length of IncompleteMemory must be at least 1."); + } + this.length = length; + history = new LinkedList(); + } - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IMemory#add(java.lang.Object) - */ - @Override - public void add(T state) { - if (history.size() == length) { - history.remove(0); - } - history.add(state); - } + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IMemory#add(java.lang.Object) + */ + @Override + public void add(T state) { + if (history.size() == length) { + history.remove(0); + } + history.add(state); + } - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IMemory#getLast(int) - */ - @Override - public List getLast(int num) { - if( num<1 ) { - return new LinkedList(); - } else { - return new LinkedList(history.subList( - Math.max(0, history.size() - num), - history.size())); // defensive copy - } - } + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IMemory#getLast(int) + */ + @Override + public List getLast(int num) { + if (num < 1) { + return new LinkedList(); + } + else { + return new LinkedList(history.subList(Math.max(0, history.size() - num), + history.size())); // defensive copy + } + } - /** - *

- * Returns the current length of the memory. This can be less than - * {@link #length}, if the overall history is less than {@link #length}. - *

- * - * @return length of the current memory - */ - public int getLength() { - return history.size(); - } + /** + *

+ * Returns the current length of the memory. This can be less than {@link #length}, if the + * overall history is less than {@link #length}. + *

+ * + * @return length of the current memory + */ + public int getLength() { + return history.size(); + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -10,12 +11,11 @@ /** *

- * This class provides functions to create flattened first-order Markov models - * from {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch} - * models through state splitting. + * This class provides functions to create flattened first-order Markov models from + * {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch} models through state + * splitting. *

*

- * If possible, the normal high-order markov model should be used, as the Events - * may be broken by the flattener, as, e.g., the information - * {@link ReplayableEvent}s contain is not preserved. + * If possible, the normal high-order markov model should be used, as the Events may be broken by + * the flattener, as, e.g., the information {@link ReplayableEvent}s contain is not preserved. *

* @@ -25,113 +25,108 @@ public class ModelFlattener { - private static final String EVENT_SEPARATOR = "-=-"; + private static final String EVENT_SEPARATOR = "-=-"; - Trie firstOrderTrie; + Trie firstOrderTrie; - /** - *

- * Takes a {@link HighOrderMarkovModel} and returns a - * {@link FirstOrderMarkovModel} that conserves the high-order memory - * through state splitting. - *

- * - * @param model - * model that is flattened - * @return flattened first-order Markov model - */ - public FirstOrderMarkovModel flattenHighOrderMarkovModel( - HighOrderMarkovModel model) { - int markovOrder = model.trieOrder - 1; - FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel( - new Random()); - firstOrderModel.trieOrder = 2; - if (markovOrder == 1) { - firstOrderModel.trie = new Trie(model.trie); - firstOrderModel.trieOrder = 2; - } else { - firstOrderTrie = new Trie(); - TrieNode rootNode = model.trie.find(null); - generateFirstOrderTrie(rootNode, new LinkedList(), markovOrder); - firstOrderTrie.updateKnownSymbols(); - firstOrderModel.trie = firstOrderTrie; - } + /** + *

+ * Takes a {@link HighOrderMarkovModel} and returns a {@link FirstOrderMarkovModel} that + * conserves the high-order memory through state splitting. + *

+ * + * @param model + * model that is flattened + * @return flattened first-order Markov model + */ + public FirstOrderMarkovModel flattenHighOrderMarkovModel(HighOrderMarkovModel model) { + int markovOrder = model.trieOrder - 1; + FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel(new Random()); + firstOrderModel.trieOrder = 2; + if (markovOrder == 1) { + firstOrderModel.trie = new Trie(model.trie); + firstOrderModel.trieOrder = 2; + } + else { + firstOrderTrie = new Trie(); + TrieNode rootNode = model.trie.find(null); + generateFirstOrderTrie(rootNode, new LinkedList(), markovOrder); + firstOrderTrie.updateKnownSymbols(); + firstOrderModel.trie = firstOrderTrie; + } - return firstOrderModel; - } + return firstOrderModel; + } - /** - *

- * This method is not available yet and always return null! - *

- *

- * Takes a {@link PredictionByPartialMatch} model and returns a - * {@link FirstOrderMarkovModel} that conserves the high-order memory - * through state splitting. - *

- * - * @param model - * model that is flattened - * @return flattened first-order Markov model - */ - public FirstOrderMarkovModel flattenPredictionByPartialMatch( - PredictionByPartialMatch model) { - // TODO implement method - return null; - } + /** + *

+ * This method is not available yet and always return null! + *

+ *

+ * Takes a {@link PredictionByPartialMatch} model and returns a {@link FirstOrderMarkovModel} + * that conserves the high-order memory through state splitting. + *

+ * + * @param model + * model that is flattened + * @return flattened first-order Markov model + */ + public FirstOrderMarkovModel flattenPredictionByPartialMatch(PredictionByPartialMatch model) { + // TODO implement method + return null; + } - /** - *

- * Converts all nodes of the given depth into first-order node through - * state-splitting. For each node at the given depth a new node is created - * and appropriate transitions will be added. - *

- *

- * This method traverses through the tree recursively. If the recursion - * reaches the desired depth in the tree, node are added. - *

- * - * @param currentNode - * node whose sub-trie is currently traversed - * @param parentIDs - * ID strings of the ancestors of the currentNode - * @param depth - * depth to go - NOT the current depth. - */ - private void generateFirstOrderTrie(TrieNode currentNode, - List parentIDs, int depth) { - for (TrieNode child : currentNode.getChildren()) { - String currentId = child.getSymbol().getId(); - if (depth > 1) { - List childParentIDs = new LinkedList(parentIDs); - childParentIDs.add(currentId); - generateFirstOrderTrie(child, childParentIDs, depth - 1); + /** + *

+ * Converts all nodes of the given depth into first-order node through state-splitting. For each + * node at the given depth a new node is created and appropriate transitions will be added. + *

+ *

+ * This method traverses through the tree recursively. If the recursion reaches the desired + * depth in the tree, node are added. + *

+ * + * @param currentNode + * node whose sub-trie is currently traversed + * @param parentIDs + * ID strings of the ancestors of the currentNode + * @param depth + * depth to go - NOT the current depth. + */ + private void generateFirstOrderTrie(TrieNode currentNode, + List parentIDs, + int depth) + { + for (TrieNode child : currentNode.getChildren()) { + String currentId = child.getSymbol().getId(); + if (depth > 1) { + List childParentIDs = new LinkedList(parentIDs); + childParentIDs.add(currentId); + generateFirstOrderTrie(child, childParentIDs, depth - 1); - } else { - StringBuilder firstOrderID = new StringBuilder(); - for (String parentID : parentIDs) { - firstOrderID.append(parentID + EVENT_SEPARATOR); - } - firstOrderID.append(currentId); - TrieNode firstOrderNode = firstOrderTrie - .getChildCreate(new Event(new StringEventType(firstOrderID - .toString()))); - firstOrderNode.setCount(child.getCount()); - for (TrieNode transitionChild : child.getChildren()) { - StringBuilder transitionID = new StringBuilder(); - for (String parentID : parentIDs.subList(1, - parentIDs.size())) { - transitionID.append(parentID + EVENT_SEPARATOR); - } - transitionID.append(currentId + EVENT_SEPARATOR); - transitionID.append(transitionChild.getSymbol() - .getId()); - TrieNode firstOrderTransitionChild = firstOrderNode - .getChildCreate(new Event(new StringEventType(transitionID - .toString()))); - firstOrderTransitionChild.setCount(transitionChild - .getCount()); - } - } - } - } + } + else { + StringBuilder firstOrderID = new StringBuilder(); + for (String parentID : parentIDs) { + firstOrderID.append(parentID + EVENT_SEPARATOR); + } + firstOrderID.append(currentId); + TrieNode firstOrderNode = + firstOrderTrie.getChildCreate(new Event(new StringEventType(firstOrderID + .toString()))); + firstOrderNode.setCount(child.getCount()); + for (TrieNode transitionChild : child.getChildren()) { + StringBuilder transitionID = new StringBuilder(); + for (String parentID : parentIDs.subList(1, parentIDs.size())) { + transitionID.append(parentID + EVENT_SEPARATOR); + } + transitionID.append(currentId + EVENT_SEPARATOR); + transitionID.append(transitionChild.getSymbol().getId()); + TrieNode firstOrderTransitionChild = + firstOrderNode.getChildCreate(new Event(new StringEventType(transitionID + .toString()))); + firstOrderTransitionChild.setCount(transitionChild.getCount()); + } + } + } + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -11,6 +12,6 @@ /** *

- * Implements Prediction by Partial Match (PPM) based on the following formula - * (LaTeX-style notation):
+ * Implements Prediction by Partial Match (PPM) based on the following formula (LaTeX-style + * notation):
* P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})
@@ -23,178 +24,177 @@ public class PredictionByPartialMatch extends TrieBasedModel { - /** - *

- * Id for object serialization. - *

- */ - private static final long serialVersionUID = 1L; - - /** - *

- * Minimum order of the Markov model. - *

- */ - protected int minOrder; - - /** - *

- * Probability to use a lower-order Markov model - *

- */ - protected double probEscape; - - /** - *

- * Constructor. Creates a new PredictionByPartialMatch model with a given - * Markov order and a default escape probability of 0.1. - *

- * - * @param markovOrder - * Markov order of the model - * @param r - * random number generator used by probabilistic methods of the - * class - */ - public PredictionByPartialMatch(int markovOrder, Random r) { - this(markovOrder, r, 0.1); - } - - /** - *

- * Creates a new PredictionByPartialMatch model with a given Markov order - * and escape probability. - *

- * - * @param markovOrder - * Markov order of the model - * @param r - * random number generator used by probabilistic methods of the - * class - * @param probEscape - * escape probability used by the model - */ - public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) { - this(markovOrder, 0, r, probEscape); - } - - /** - *

- * Creates a new PredictionByPartialMatch model with a given Markov order - * and escape probability. - *

- * - * @param markovOrder - * Markov order of the model - * @param minOrder - * minimum order of the model; if this order is reached, there is - * no escape - * @param r - * random number generator used by probabilistic methods of the - * class - * @param probEscape - * escape probability used by the model - * @throws InvalidParameterException thrown if minOrder is less than 0 or greater than markovOrder or probEscape is not in the interval (0,1) - */ - public PredictionByPartialMatch(int markovOrder, int minOrder, Random r, - double probEscape) { - super(markovOrder, r); - if( minOrder< 0 ) { - throw new InvalidParameterException("minOrder must be greather than or equal to 0"); - } - if( minOrder>markovOrder) { - throw new InvalidParameterException("minOrder must be less than or equal to markovOrder"); - } - if( probEscape<=0.0 || probEscape>=1.0) { - throw new InvalidParameterException("probEscape must be in the interval (0,1)"); - } - this.probEscape = probEscape; - this.minOrder = minOrder; - } - - /** - *

- * Sets the escape probability of the model. - *

- * - * @param probEscape - * new escape probability - */ - public void setProbEscape(double probEscape) { - this.probEscape = probEscape; - } - - /** - *

- * Returns the escape probability of the model. - *

- * - * @return escape probability of the model - */ - public double getProbEscape() { - return probEscape; - } - - /** - *

- * Calculates the probability of the next event based on the formula:
- * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} - * P_{MM^i}(X_n - * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... - * ,X_{n-min})
- * P_{MM^i} denotes the probability in an i-th order Markov model. - *

- * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, - * de.ugoe.cs.quest.eventcore.Event) - */ - @Override - public double getProbability(List context, - Event symbol) { - if (context == null) { - throw new InvalidParameterException("context must not be null"); - } - if (symbol == null) { - throw new InvalidParameterException("symbol must not be null"); - } - double result = 0.0d; - double resultCurrentContex = 0.0d; - double resultShorterContex = 0.0d; - - List contextCopy; - if (context.size() >= trieOrder) { - contextCopy = new LinkedList(context.subList( - context.size() - trieOrder + 1, context.size())); - } else { - contextCopy = new LinkedList(context); - } - - Collection followers = trie.getFollowingSymbols(contextCopy); // \Sigma' - int sumCountFollowers = 0; // N(s\sigma') - for (Event follower : followers) { - sumCountFollowers += trie.getCount(contextCopy, follower); - } - - int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) - if (sumCountFollowers == 0) { - resultCurrentContex = 0.0; - } else { - resultCurrentContex = (double) countSymbol / sumCountFollowers; - } - if (contextCopy.size() > minOrder) { - resultCurrentContex *= (1 - probEscape); - contextCopy.remove(0); - if (contextCopy.size() >= minOrder) { - double probSuffix = getProbability(contextCopy, symbol); - - if (followers.size() == 0) { - resultShorterContex = probSuffix; - } else { - resultShorterContex = probEscape * probSuffix; - } - } - } - result = resultCurrentContex + resultShorterContex; - - return result; - } + /** + *

+ * Id for object serialization. + *

+ */ + private static final long serialVersionUID = 1L; + + /** + *

+ * Minimum order of the Markov model. + *

+ */ + protected int minOrder; + + /** + *

+ * Probability to use a lower-order Markov model + *

+ */ + protected double probEscape; + + /** + *

+ * Constructor. Creates a new PredictionByPartialMatch model with a given Markov order and a + * default escape probability of 0.1. + *

+ * + * @param markovOrder + * Markov order of the model + * @param r + * random number generator used by probabilistic methods of the class + */ + public PredictionByPartialMatch(int markovOrder, Random r) { + this(markovOrder, r, 0.1); + } + + /** + *

+ * Creates a new PredictionByPartialMatch model with a given Markov order and escape + * probability. + *

+ * + * @param markovOrder + * Markov order of the model + * @param r + * random number generator used by probabilistic methods of the class + * @param probEscape + * escape probability used by the model + */ + public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) { + this(markovOrder, 0, r, probEscape); + } + + /** + *

+ * Creates a new PredictionByPartialMatch model with a given Markov order and escape + * probability. + *

+ * + * @param markovOrder + * Markov order of the model + * @param minOrder + * minimum order of the model; if this order is reached, there is no escape + * @param r + * random number generator used by probabilistic methods of the class + * @param probEscape + * escape probability used by the model + * @throws InvalidParameterException + * thrown if minOrder is less than 0 or greater than markovOrder or probEscape is + * not in the interval (0,1) + */ + public PredictionByPartialMatch(int markovOrder, int minOrder, Random r, double probEscape) { + super(markovOrder, r); + if (minOrder < 0) { + throw new InvalidParameterException("minOrder must be greather than or equal to 0"); + } + if (minOrder > markovOrder) { + throw new InvalidParameterException( + "minOrder must be less than or equal to markovOrder"); + } + if (probEscape <= 0.0 || probEscape >= 1.0) { + throw new InvalidParameterException("probEscape must be in the interval (0,1)"); + } + this.probEscape = probEscape; + this.minOrder = minOrder; + } + + /** + *

+ * Sets the escape probability of the model. + *

+ * + * @param probEscape + * new escape probability + */ + public void setProbEscape(double probEscape) { + this.probEscape = probEscape; + } + + /** + *

+ * Returns the escape probability of the model. + *

+ * + * @return escape probability of the model + */ + public double getProbEscape() { + return probEscape; + } + + /** + *

+ * Calculates the probability of the next event based on the formula:
+ * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n + * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})
+ * P_{MM^i} denotes the probability in an i-th order Markov model. + *

+ * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, + * de.ugoe.cs.quest.eventcore.Event) + */ + @Override + public double getProbability(List context, Event symbol) { + if (context == null) { + throw new InvalidParameterException("context must not be null"); + } + if (symbol == null) { + throw new InvalidParameterException("symbol must not be null"); + } + double result = 0.0d; + double resultCurrentContex = 0.0d; + double resultShorterContex = 0.0d; + + List contextCopy; + if (context.size() >= trieOrder) { + contextCopy = + new LinkedList(context.subList(context.size() - trieOrder + 1, + context.size())); + } + else { + contextCopy = new LinkedList(context); + } + + Collection followers = trie.getFollowingSymbols(contextCopy); // \Sigma' + int sumCountFollowers = 0; // N(s\sigma') + for (Event follower : followers) { + sumCountFollowers += trie.getCount(contextCopy, follower); + } + + int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) + if (sumCountFollowers == 0) { + resultCurrentContex = 0.0; + } + else { + resultCurrentContex = (double) countSymbol / sumCountFollowers; + } + if (contextCopy.size() > minOrder) { + resultCurrentContex *= (1 - probEscape); + contextCopy.remove(0); + if (contextCopy.size() >= minOrder) { + double probSuffix = getProbability(contextCopy, symbol); + + if (followers.size() == 0) { + resultShorterContex = probSuffix; + } + else { + resultShorterContex = probEscape * probSuffix; + } + } + } + result = resultCurrentContex + resultShorterContex; + + return result; + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -17,7 +18,6 @@ /** *

- * This class implements a trie, i.e., a tree of sequences that the - * occurence of subsequences up to a predefined length. This length is the trie - * order. + * This class implements a trie, i.e., a tree of sequences that the occurence of + * subsequences up to a predefined length. This length is the trie order. *

* @@ -31,442 +31,438 @@ public class Trie implements IDotCompatible, Serializable { - /** - *

- * Id for object serialization. - *

- */ - private static final long serialVersionUID = 1L; - - /** - *

- * Collection of all symbols occuring in the trie. - *

- */ - private Collection knownSymbols; - - /** - *

- * Reference to the root of the trie. - *

- */ - private final TrieNode rootNode; - - /** - *

- * Contructor. Creates a new Trie. - *

- */ - public Trie() { - rootNode = new TrieNode(); - knownSymbols = new LinkedHashSet(); - } - - /** - *

- * 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 other) { - if (other == null) { - throw new InvalidParameterException("other trie must not be null"); - } - rootNode = new TrieNode(other.rootNode); - knownSymbols = new LinkedHashSet(other.knownSymbols); - } - - /** - *

- * Returns a collection of all symbols occuring in the trie. - *

- * - * @return symbols occuring in the trie - */ - public Collection getKnownSymbols() { - return new LinkedHashSet(knownSymbols); - } - - /** - *

- * 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 sequence, int maxOrder) { - if (maxOrder < 1) { - return; - } - IncompleteMemory latestActions = new IncompleteMemory(maxOrder); - int i = 0; - for (T currentEvent : sequence) { - latestActions.add(currentEvent); - knownSymbols.add(currentEvent); - i++; - if (i >= maxOrder) { - add(latestActions.getLast(maxOrder)); - } - } - int sequenceLength = sequence.size(); - for (int j = maxOrder - 1; j > 0; j--) { - add(sequence.subList(sequenceLength - j, sequenceLength)); - } - } - - /** - *

- * 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 subsequence) { - if (subsequence != null && !subsequence.isEmpty()) { - knownSymbols.addAll(subsequence); - subsequence = new LinkedList(subsequence); // defensive copy! - T firstSymbol = subsequence.get(0); - TrieNode node = getChildCreate(firstSymbol); - node.add(subsequence); - } - } - - /** - *

- * 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 getChildCreate(T symbol) { - return rootNode.getChildCreate(symbol); - } - - /** - *

- * 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 getChild(T symbol) { - return rootNode.getChild(symbol); - } - - /** - *

- * 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 sequence) { - int count = 0; - TrieNode node = find(sequence); - if (node != null) { - count = node.getCount(); - } - return count; - } - - /** - *

- * Returns the number of occurences of the given prefix and a symbol that - * follows it.
- * Convenience function to simplify usage of {@link #getCount(List)}. - *

- * - * @param sequence - * prefix of the sequence - * @param follower - * suffix of the sequence - * @return number of occurences of the sequence - * @see #getCount(List) - */ - public int getCount(List sequence, T follower) { - List tmpSequence = new LinkedList(sequence); - tmpSequence.add(follower); - return getCount(tmpSequence); - - } - - /** - *

- * 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 find(List sequence) { - if (sequence == null || sequence.isEmpty()) { - return rootNode; - } - List sequenceCopy = new LinkedList(sequence); - TrieNode result = null; - TrieNode node = getChild(sequenceCopy.get(0)); - if (node != null) { - sequenceCopy.remove(0); - result = node.find(sequenceCopy); - } - return result; - } - - /** - *

- * 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 getFollowingSymbols(List sequence) { - Collection result = new LinkedList(); - TrieNode node = find(sequence); - if (node != null) { - result = node.getFollowingSymbols(); - } - return result; - } - - /** - *

- * 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 getContextSuffix(List context) { - List contextSuffix; - if (context != null) { - contextSuffix = new LinkedList(context); // defensive copy - } else { - contextSuffix = new LinkedList(); - } - boolean suffixFound = false; - - while (!suffixFound) { - if (contextSuffix.isEmpty()) { - suffixFound = true; // suffix is the empty word - } else { - TrieNode node = find(contextSuffix); - if (node != null) { - if (!node.getFollowingSymbols().isEmpty()) { - suffixFound = true; - } - } - if (!suffixFound) { - contextSuffix.remove(0); - } - } - } - - return contextSuffix; - } - - /** - *

- * 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 getGraph() { - DelegateTree graph = new DelegateTree(); - rootNode.getGraph(null, graph); - return graph; - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() - */ - public String getDotRepresentation() { - StringBuilder stringBuilder = new StringBuilder(); - stringBuilder.append("digraph model {" + StringTools.ENDLINE); - rootNode.appendDotRepresentation(stringBuilder); - stringBuilder.append('}' + StringTools.ENDLINE); - return stringBuilder.toString(); - } - - /** - *

- * 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> ancestors = new LinkedList>(); - rootNode.getLeafAncestors(ancestors); - return ancestors.size(); - } - - /** - *

- * Returns the number of trie nodes that are leafs. - *

- * - * @return number of leafs in the trie - */ - public int getNumLeafs() { - return rootNode.getNumLeafs(); - } - - /** - *

- * 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. - *

- */ - public void updateKnownSymbols() { - knownSymbols = new HashSet(); - for (TrieNode node : rootNode.getChildren()) { - knownSymbols.add(node.getSymbol()); - } - } - - /** - *

- * Two Tries are defined as equal, if their {@link #rootNode} are equal. - *

- * - * @see java.lang.Object#equals(java.lang.Object) - */ - @SuppressWarnings("rawtypes") - @Override - public boolean equals(Object other) { - if (other == this) { - return true; - } - if (other instanceof Trie) { - return rootNode.equals(((Trie) other).rootNode); - } - return false; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#hashCode() - */ - @Override - public int hashCode() { - int multiplier = 17; - int hash = 42; - if (rootNode != null) { - hash = multiplier * hash + rootNode.hashCode(); - } - return hash; - } + /** + *

+ * Id for object serialization. + *

+ */ + private static final long serialVersionUID = 1L; + + /** + *

+ * Collection of all symbols occuring in the trie. + *

+ */ + private Collection knownSymbols; + + /** + *

+ * Reference to the root of the trie. + *

+ */ + private final TrieNode rootNode; + + /** + *

+ * Contructor. Creates a new Trie. + *

+ */ + public Trie() { + rootNode = new TrieNode(); + knownSymbols = new LinkedHashSet(); + } + + /** + *

+ * 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 other) { + if (other == null) { + throw new InvalidParameterException("other trie must not be null"); + } + rootNode = new TrieNode(other.rootNode); + knownSymbols = new LinkedHashSet(other.knownSymbols); + } + + /** + *

+ * Returns a collection of all symbols occuring in the trie. + *

+ * + * @return symbols occuring in the trie + */ + public Collection getKnownSymbols() { + return new LinkedHashSet(knownSymbols); + } + + /** + *

+ * 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 sequence, int maxOrder) { + if (maxOrder < 1) { + return; + } + IncompleteMemory latestActions = new IncompleteMemory(maxOrder); + int i = 0; + for (T currentEvent : sequence) { + latestActions.add(currentEvent); + knownSymbols.add(currentEvent); + i++; + if (i >= maxOrder) { + add(latestActions.getLast(maxOrder)); + } + } + int sequenceLength = sequence.size(); + for (int j = maxOrder - 1; j > 0; j--) { + add(sequence.subList(sequenceLength - j, sequenceLength)); + } + } + + /** + *

+ * 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 subsequence) { + if (subsequence != null && !subsequence.isEmpty()) { + knownSymbols.addAll(subsequence); + subsequence = new LinkedList(subsequence); // defensive copy! + T firstSymbol = subsequence.get(0); + TrieNode node = getChildCreate(firstSymbol); + node.add(subsequence); + } + } + + /** + *

+ * 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 getChildCreate(T symbol) { + return rootNode.getChildCreate(symbol); + } + + /** + *

+ * 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 getChild(T symbol) { + return rootNode.getChild(symbol); + } + + /** + *

+ * 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 sequence) { + int count = 0; + TrieNode node = find(sequence); + if (node != null) { + count = node.getCount(); + } + return count; + } + + /** + *

+ * Returns the number of occurences of the given prefix and a symbol that follows it.
+ * Convenience function to simplify usage of {@link #getCount(List)}. + *

+ * + * @param sequence + * prefix of the sequence + * @param follower + * suffix of the sequence + * @return number of occurences of the sequence + * @see #getCount(List) + */ + public int getCount(List sequence, T follower) { + List tmpSequence = new LinkedList(sequence); + tmpSequence.add(follower); + return getCount(tmpSequence); + + } + + /** + *

+ * 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 find(List sequence) { + if (sequence == null || sequence.isEmpty()) { + return rootNode; + } + List sequenceCopy = new LinkedList(sequence); + TrieNode result = null; + TrieNode node = getChild(sequenceCopy.get(0)); + if (node != null) { + sequenceCopy.remove(0); + result = node.find(sequenceCopy); + } + return result; + } + + /** + *

+ * 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 getFollowingSymbols(List sequence) { + Collection result = new LinkedList(); + TrieNode node = find(sequence); + if (node != null) { + result = node.getFollowingSymbols(); + } + return result; + } + + /** + *

+ * 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 getContextSuffix(List context) { + List contextSuffix; + if (context != null) { + contextSuffix = new LinkedList(context); // defensive copy + } + else { + contextSuffix = new LinkedList(); + } + boolean suffixFound = false; + + while (!suffixFound) { + if (contextSuffix.isEmpty()) { + suffixFound = true; // suffix is the empty word + } + else { + TrieNode node = find(contextSuffix); + if (node != null) { + if (!node.getFollowingSymbols().isEmpty()) { + suffixFound = true; + } + } + if (!suffixFound) { + contextSuffix.remove(0); + } + } + } + + return contextSuffix; + } + + /** + *

+ * 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 getGraph() { + DelegateTree graph = new DelegateTree(); + rootNode.getGraph(null, graph); + return graph; + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() + */ + public String getDotRepresentation() { + StringBuilder stringBuilder = new StringBuilder(); + stringBuilder.append("digraph model {" + StringTools.ENDLINE); + rootNode.appendDotRepresentation(stringBuilder); + stringBuilder.append('}' + StringTools.ENDLINE); + return stringBuilder.toString(); + } + + /** + *

+ * 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> ancestors = new LinkedList>(); + rootNode.getLeafAncestors(ancestors); + return ancestors.size(); + } + + /** + *

+ * Returns the number of trie nodes that are leafs. + *

+ * + * @return number of leafs in the trie + */ + public int getNumLeafs() { + return rootNode.getNumLeafs(); + } + + /** + *

+ * 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. + *

+ */ + public void updateKnownSymbols() { + knownSymbols = new HashSet(); + for (TrieNode node : rootNode.getChildren()) { + knownSymbols.add(node.getSymbol()); + } + } + + /** + *

+ * Two Tries are defined as equal, if their {@link #rootNode} are equal. + *

+ * + * @see java.lang.Object#equals(java.lang.Object) + */ + @SuppressWarnings("rawtypes") + @Override + public boolean equals(Object other) { + if (other == this) { + return true; + } + if (other instanceof Trie) { + return rootNode.equals(((Trie) other).rootNode); + } + return false; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + int multiplier = 17; + int hash = 42; + if (rootNode != null) { + hash = multiplier * hash + rootNode.hashCode(); + } + return hash; + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -18,7 +19,6 @@ /** *

- * Implements a skeleton for stochastic processes that can calculate - * probabilities based on a trie. The skeleton provides all functionalities of - * {@link IStochasticProcess} except + * Implements a skeleton for stochastic processes that can calculate probabilities based on a trie. + * The skeleton provides all functionalities of {@link IStochasticProcess} except * {@link IStochasticProcess#getProbability(List, Event)}. *

@@ -29,388 +29,376 @@ public abstract class TrieBasedModel implements IStochasticProcess { - /** - *

- * Id for object serialization. - *

- */ - private static final long serialVersionUID = 1L; - - /** - *

- * The order of the trie, i.e., the maximum length of subsequences stored in - * the trie. - *

- */ - protected int trieOrder; - - /** - *

- * Trie on which the probability calculations are based. - *

- */ - protected Trie trie = null; - - /** - *

- * Random number generator used by probabilistic sequence generation - * methods. - *

- */ - protected final Random r; - - /** - *

- * Constructor. Creates a new TrieBasedModel that can be used for stochastic - * processes with a Markov order less than or equal to {@code markovOrder}. - *

- * - * @param markovOrder - * Markov order of the model - * @param r - * random number generator used by probabilistic methods of the - * class - * @throws InvalidParameterException - * thrown if markovOrder is less than 0 or the random number - * generator r is null - */ - public TrieBasedModel(int markovOrder, Random r) { - super(); - if (markovOrder < 0) { - throw new InvalidParameterException( - "markov order must not be less than 0"); - } - if (r == null) { - throw new InvalidParameterException( - "random number generator r must not be null"); - } - this.trieOrder = markovOrder + 1; - this.r = r; - } - - /** - *

- * Trains the model by generating a trie from which probabilities are - * calculated. The trie is newly generated based solely on the passed - * sequences. If an existing model should only be updated, use - * {@link #update(Collection)} instead. - *

- * - * @param sequences - * training data - * @throws InvalidParameterException - * thrown is sequences is null - */ - public void train(Collection> sequences) { - trie = null; - update(sequences); - } - - /** - *

- * Trains the model by updating the trie from which the probabilities are - * calculated. This function updates an existing trie. In case no trie - * exists yet, a new trie is generated and the function behaves like - * {@link #train(Collection)}. - *

- * - * @param sequences - * training data - * @throws InvalidParameterException - * thrown is sequences is null - */ - public void update(Collection> sequences) { - if (sequences == null) { - throw new InvalidParameterException("sequences must not be null"); - } - if (trie == null) { - trie = new Trie(); - } - for (List sequence : sequences) { - List currentSequence = new LinkedList(sequence); // defensive - // copy - currentSequence.add(0, Event.STARTEVENT); - currentSequence.add(Event.ENDEVENT); - - trie.train(currentSequence, trieOrder); - } - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#randomSequence() - */ - @Override - public List randomSequence() { - return randomSequence(Integer.MAX_VALUE, true); - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#randomSequence() - */ - @Override - public List randomSequence(int maxLength, - boolean validEnd) { - List sequence = new LinkedList(); - if (trie != null) { - boolean endFound = false; - while (!endFound) { // outer loop for length checking - sequence = new LinkedList(); - IncompleteMemory context = new IncompleteMemory( - trieOrder - 1); - context.add(Event.STARTEVENT); - - while (!endFound && sequence.size() <= maxLength) { - double randVal = r.nextDouble(); - double probSum = 0.0; - List currentContext = context.getLast(trieOrder); - for (Event symbol : trie.getKnownSymbols()) { - probSum += getProbability(currentContext, symbol); - if (probSum >= randVal) { - if (!(Event.STARTEVENT.equals(symbol) || Event.ENDEVENT - .equals(symbol))) { - // only add the symbol the sequence if it is not - // START or END - context.add(symbol); - sequence.add(symbol); - } - endFound = (Event.ENDEVENT.equals(symbol)) - || (!validEnd && sequence.size() == maxLength); - break; - } - } - } - } - } - return sequence; - } - - /** - *

- * Returns a Dot representation of the internal trie. - *

- * - * @return dot representation of the internal trie - */ - public String getTrieDotRepresentation() { - if (trie == null) { - return ""; - } else { - return trie.getDotRepresentation(); - } - } - - /** - *

- * Returns a {@link Tree} of the internal trie that can be used for - * visualization. - *

- * - * @return {@link Tree} depicting the internal trie - */ - public Tree getTrieGraph() { - if (trie == null) { - return null; - } else { - return trie.getGraph(); - } - } - - /** - *

- * The string representation of the model is {@link Trie#toString()} of - * {@link #trie}. - *

- * - * @see java.lang.Object#toString() - */ - @Override - public String toString() { - if (trie == null) { - return ""; - } else { - return trie.toString(); - } - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumStates() - */ - @Override - public int getNumSymbols() { - if (trie == null) { - return 0; - } else { - return trie.getNumSymbols(); - } - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getStateStrings() - */ - @Override - public String[] getSymbolStrings() { - if (trie == null) { - return new String[0]; - } - String[] stateStrings = new String[getNumSymbols()]; - int i = 0; - for (Event symbol : trie.getKnownSymbols()) { - if (symbol.toString() == null) { - stateStrings[i] = "null"; - } else { - stateStrings[i] = symbol.toString(); - } - i++; - } - return stateStrings; - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getEvents() - */ - @Override - public Collection getEvents() { - if (trie == null) { - return new HashSet(); - } else { - return trie.getKnownSymbols(); - } - } - - /* - * (non-Javadoc) - * - * @see - * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateSequences(int) - */ - @Override - public Collection> generateSequences(int length) { - return generateSequences(length, false); - } - - /* - * (non-Javadoc) - * - * @see - * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateSequences(int, - * boolean) - */ - @Override - public Set> generateSequences(int length, - boolean fromStart) { - Set> sequenceSet = new LinkedHashSet>(); - if (length < 1) { - throw new InvalidParameterException( - "Length of generated subsequences must be at least 1."); - } - if (length == 1) { - if (fromStart) { - List subSeq = new LinkedList(); - subSeq.add(Event.STARTEVENT); - sequenceSet.add(subSeq); - } else { - for (Event event : getEvents()) { - List subSeq = new LinkedList(); - subSeq.add(event); - sequenceSet.add(subSeq); - } - } - return sequenceSet; - } - Collection events = getEvents(); - Collection> seqsShorter = generateSequences( - length - 1, fromStart); - for (Event event : events) { - for (List seqShorter : seqsShorter) { - Event lastEvent = event; - if (getProbability(seqShorter, lastEvent) > 0.0) { - List subSeq = new ArrayList(seqShorter); - subSeq.add(lastEvent); - sequenceSet.add(subSeq); - } - } - } - return sequenceSet; - } - - /* - * (non-Javadoc) - * - * @see - * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateValidSequences - * (int) - */ - @Override - public Collection> generateValidSequences( - int length) { - // check for min-length implicitly done by generateSequences - Collection> allSequences = generateSequences( - length, true); - Collection> validSequences = new LinkedHashSet>(); - for (List sequence : allSequences) { - if (sequence.size() == length - && Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) { - validSequences.add(sequence); - } - } - return validSequences; - } - - /* - * (non-Javadoc) - * - * @see - * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util - * .List) - */ - @Override - public double getProbability(List sequence) { - if (sequence == null) { - throw new InvalidParameterException("sequence must not be null"); - } - double prob = 1.0; - List context = new LinkedList(); - for (Event event : sequence) { - prob *= getProbability(context, event); - context.add(event); - } - return prob; - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumFOMStates() - */ - @Override - public int getNumFOMStates() { - if (trie == null) { - return 0; - } else { - return trie.getNumLeafAncestors(); - } - } - - /* - * (non-Javadoc) - * - * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumTransitions() - */ - @Override - public int getNumTransitions() { - if (trie == null) { - return 0; - } else { - return trie.getNumLeafs(); - } - } + /** + *

+ * Id for object serialization. + *

+ */ + private static final long serialVersionUID = 1L; + + /** + *

+ * The order of the trie, i.e., the maximum length of subsequences stored in the trie. + *

+ */ + protected int trieOrder; + + /** + *

+ * Trie on which the probability calculations are based. + *

+ */ + protected Trie trie = null; + + /** + *

+ * Random number generator used by probabilistic sequence generation methods. + *

+ */ + protected final Random r; + + /** + *

+ * Constructor. Creates a new TrieBasedModel that can be used for stochastic processes with a + * Markov order less than or equal to {@code markovOrder}. + *

+ * + * @param markovOrder + * Markov order of the model + * @param r + * random number generator used by probabilistic methods of the class + * @throws InvalidParameterException + * thrown if markovOrder is less than 0 or the random number generator r is null + */ + public TrieBasedModel(int markovOrder, Random r) { + super(); + if (markovOrder < 0) { + throw new InvalidParameterException("markov order must not be less than 0"); + } + if (r == null) { + throw new InvalidParameterException("random number generator r must not be null"); + } + this.trieOrder = markovOrder + 1; + this.r = r; + } + + /** + *

+ * Trains the model by generating a trie from which probabilities are calculated. The trie is + * newly generated based solely on the passed sequences. If an existing model should only be + * updated, use {@link #update(Collection)} instead. + *

+ * + * @param sequences + * training data + * @throws InvalidParameterException + * thrown is sequences is null + */ + public void train(Collection> sequences) { + trie = null; + update(sequences); + } + + /** + *

+ * Trains the model by updating the trie from which the probabilities are calculated. This + * function updates an existing trie. In case no trie exists yet, a new trie is generated and + * the function behaves like {@link #train(Collection)}. + *

+ * + * @param sequences + * training data + * @throws InvalidParameterException + * thrown is sequences is null + */ + public void update(Collection> sequences) { + if (sequences == null) { + throw new InvalidParameterException("sequences must not be null"); + } + if (trie == null) { + trie = new Trie(); + } + for (List sequence : sequences) { + List currentSequence = new LinkedList(sequence); // defensive + // copy + currentSequence.add(0, Event.STARTEVENT); + currentSequence.add(Event.ENDEVENT); + + trie.train(currentSequence, trieOrder); + } + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#randomSequence() + */ + @Override + public List randomSequence() { + return randomSequence(Integer.MAX_VALUE, true); + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#randomSequence() + */ + @Override + public List randomSequence(int maxLength, boolean validEnd) { + List sequence = new LinkedList(); + if (trie != null) { + boolean endFound = false; + while (!endFound) { // outer loop for length checking + sequence = new LinkedList(); + IncompleteMemory context = new IncompleteMemory(trieOrder - 1); + context.add(Event.STARTEVENT); + + while (!endFound && sequence.size() <= maxLength) { + double randVal = r.nextDouble(); + double probSum = 0.0; + List currentContext = context.getLast(trieOrder); + for (Event symbol : trie.getKnownSymbols()) { + probSum += getProbability(currentContext, symbol); + if (probSum >= randVal) { + if (!(Event.STARTEVENT.equals(symbol) || Event.ENDEVENT.equals(symbol))) + { + // only add the symbol the sequence if it is not + // START or END + context.add(symbol); + sequence.add(symbol); + } + endFound = + (Event.ENDEVENT.equals(symbol)) || + (!validEnd && sequence.size() == maxLength); + break; + } + } + } + } + } + return sequence; + } + + /** + *

+ * Returns a Dot representation of the internal trie. + *

+ * + * @return dot representation of the internal trie + */ + public String getTrieDotRepresentation() { + if (trie == null) { + return ""; + } + else { + return trie.getDotRepresentation(); + } + } + + /** + *

+ * Returns a {@link Tree} of the internal trie that can be used for visualization. + *

+ * + * @return {@link Tree} depicting the internal trie + */ + public Tree getTrieGraph() { + if (trie == null) { + return null; + } + else { + return trie.getGraph(); + } + } + + /** + *

+ * The string representation of the model is {@link Trie#toString()} of {@link #trie}. + *

+ * + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + if (trie == null) { + return ""; + } + else { + return trie.toString(); + } + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumStates() + */ + @Override + public int getNumSymbols() { + if (trie == null) { + return 0; + } + else { + return trie.getNumSymbols(); + } + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getStateStrings() + */ + @Override + public String[] getSymbolStrings() { + if (trie == null) { + return new String[0]; + } + String[] stateStrings = new String[getNumSymbols()]; + int i = 0; + for (Event symbol : trie.getKnownSymbols()) { + if (symbol.toString() == null) { + stateStrings[i] = "null"; + } + else { + stateStrings[i] = symbol.toString(); + } + i++; + } + return stateStrings; + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getEvents() + */ + @Override + public Collection getEvents() { + if (trie == null) { + return new HashSet(); + } + else { + return trie.getKnownSymbols(); + } + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateSequences(int) + */ + @Override + public Collection> generateSequences(int length) { + return generateSequences(length, false); + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateSequences(int, boolean) + */ + @Override + public Set> generateSequences(int length, boolean fromStart) { + Set> sequenceSet = new LinkedHashSet>(); + if (length < 1) { + throw new InvalidParameterException( + "Length of generated subsequences must be at least 1."); + } + if (length == 1) { + if (fromStart) { + List subSeq = new LinkedList(); + subSeq.add(Event.STARTEVENT); + sequenceSet.add(subSeq); + } + else { + for (Event event : getEvents()) { + List subSeq = new LinkedList(); + subSeq.add(event); + sequenceSet.add(subSeq); + } + } + return sequenceSet; + } + Collection events = getEvents(); + Collection> seqsShorter = generateSequences(length - 1, fromStart); + for (Event event : events) { + for (List seqShorter : seqsShorter) { + Event lastEvent = event; + if (getProbability(seqShorter, lastEvent) > 0.0) { + List subSeq = new ArrayList(seqShorter); + subSeq.add(lastEvent); + sequenceSet.add(subSeq); + } + } + } + return sequenceSet; + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateValidSequences (int) + */ + @Override + public Collection> generateValidSequences(int length) { + // check for min-length implicitly done by generateSequences + Collection> allSequences = generateSequences(length, true); + Collection> validSequences = new LinkedHashSet>(); + for (List sequence : allSequences) { + if (sequence.size() == length && + Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) + { + validSequences.add(sequence); + } + } + return validSequences; + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util .List) + */ + @Override + public double getProbability(List sequence) { + if (sequence == null) { + throw new InvalidParameterException("sequence must not be null"); + } + double prob = 1.0; + List context = new LinkedList(); + for (Event event : sequence) { + prob *= getProbability(context, event); + context.add(event); + } + return prob; + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumFOMStates() + */ + @Override + public int getNumFOMStates() { + if (trie == null) { + return 0; + } + else { + return trie.getNumLeafAncestors(); + } + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumTransitions() + */ + @Override + public int getNumTransitions() { + if (trie == null) { + return 0; + } + else { + return trie.getNumLeafs(); + } + } } Index: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java =================================================================== --- trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java (revision 553) +++ trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java (revision 559) @@ -1,2 +1,3 @@ + package de.ugoe.cs.quest.usageprofiles; @@ -15,7 +16,7 @@ /** *

- * This class implements a node of a trie. Each node is associated with a symbol - * and has a counter. The counter marks the number of occurences of the sequence - * defined by the path from the root of the trie to this node. + * This class implements a node of a trie. Each node is associated with a symbol and has a counter. + * The counter marks the number of occurences of the sequence defined by the path from the root of + * the trie to this node. *

* @@ -28,416 +29,412 @@ class TrieNode implements Serializable { - /** - *

- * Id for object serialization. - *

- */ - private static final long serialVersionUID = 1L; - - /** - *

- * Counter for the number of occurences of the sequence. - *

- */ - private int count; - - /** - *

- * Symbol associated with the node. - *

- */ - private final T symbol; - - /** - *

- * Child nodes of this node. If the node is a leaf this collection is empty. - *

- */ - private Collection> children; - - /** - *

- * Constructor. Creates a new TrieNode without a symbol associated.
- * This constructor should only be used to create the root node of the - * trie! - *

- */ - TrieNode() { - this.symbol = null; - count = 0; - children = new LinkedList>(); - } - - /** - *

- * Constructor. Creates a new TrieNode. The symbol must not be null. - *

- * - * @param symbol - * symbol associated with the trie node - */ - TrieNode(T symbol) { - if (symbol == null) { - throw new InvalidParameterException( - "symbol must not be null. null is reserved for root node!"); - } - this.symbol = symbol; - count = 0; - children = new LinkedList>(); - } - - /** - *

- * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not - * be null. - *

- * - * @param other - */ - TrieNode(TrieNode other) { - if (other == null) { - throw new InvalidParameterException("other must not be null"); - } - symbol = other.symbol; - count = other.count; - children = new LinkedList>(); - for (TrieNode child : other.children) { - children.add(new TrieNode(child)); - } - } - - /** - *

- * Adds a given subsequence to the trie and increases the counters - * accordingly. - *

- * - * @param subsequence - * subsequence whose counters are increased - * @see Trie#add(List) - */ - public void add(List subsequence) { - if (!subsequence.isEmpty()) { - if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by - // the - // recursion/TrieRoot! - throw new AssertionError("Invalid trie operation!"); - } - count++; - subsequence.remove(0); - if (!subsequence.isEmpty()) { - T nextSymbol = subsequence.get(0); - getChildCreate(nextSymbol).add(subsequence); - } - } - } - - /** - *

- * Returns the symbol associated with the node. - *

- * - * @return symbol associated with the node - */ - public T getSymbol() { - return symbol; - } - - /** - *

- * Returns the number of occurences of the sequence represented by the node. - *

- * - * @return number of occurences of the sequence represented by the node - */ - public int getCount() { - return count; - } - - /** - *

- * Returns the child of the 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 Trie#getChildCreate(Object) - */ - protected TrieNode getChildCreate(T symbol) { - TrieNode node = getChild(symbol); - if (node == null) { - node = new TrieNode(symbol); - children.add(node); - } - return node; - } - - /** - *

- * Returns the child of the 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 Trie#getChild(Object) - */ - protected TrieNode getChild(T symbol) { - for (TrieNode child : children) { - if (child.getSymbol().equals(symbol)) { - return child; - } - } - return null; - } - - /** - *

- * Returns all children of this node. - *

- * - * @return children of this node - */ - protected Collection> getChildren() { - return children; - } - - /** - *

- * Searches the sub-trie of this trie node 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 Trie#find(List) - */ - public TrieNode find(List subsequence) { - TrieNode result = null; - if (subsequence.isEmpty()) { - result = this; - } else { - TrieNode node = getChild(subsequence.get(0)); - if (node != null) { - subsequence.remove(0); - result = node.find(subsequence); - } - } - return result; - } - - /** - *

- * Returns a collection of all symbols that follow a this node, i.e., the - * symbols associated with the children of this node. - *

- * - * @return symbols follow this node - * @see TrieNode#getFollowingSymbols() - */ - public Collection getFollowingSymbols() { - Collection followingSymbols = new LinkedList(); - for (TrieNode child : children) { - followingSymbols.add(child.getSymbol()); - } - return followingSymbols; - } - - /** - *

- * The string representation of a node is {@code symbol.toString()#count} - *

- * - * @see java.lang.Object#toString() - */ - @Override - public String toString() { - String str = symbol.toString() + " #" + count; - if (!children.isEmpty()) { - str += StringTools.ENDLINE + children.toString(); - } - return str; - } - - /** - *

- * Generates a {@link Tree} represenation of the trie. - *

- * - * @param parent - * parent vertex in the generated tree - * @param graph - * complete tree - */ - void getGraph(TrieVertex parent, DelegateTree graph) { - TrieVertex currentVertex; - if (isRoot()) { - currentVertex = new TrieVertex("root"); - graph.addVertex(currentVertex); - } else { - currentVertex = new TrieVertex(getSymbol().toString() + "#" - + getCount()); - graph.addChild(new Edge(), parent, currentVertex); - } - for (TrieNode node : children) { - node.getGraph(currentVertex, graph); - } - } - - /** - *

- * Appends the current node to the dot representation of the trie. - *

- * - * @param stringBuilder - * {@link StringBuilder} to which the dot representation is - * appended - */ - void appendDotRepresentation(StringBuilder stringBuilder) { - String thisSaneId; - if (isRoot()) { - thisSaneId = "root"; - } else { - thisSaneId = symbol.toString().replace("\"", "\\\"") - .replaceAll("[\r\n]", "") - + "#" + count; - } - stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId - + "\"];" + StringTools.ENDLINE); - for (TrieNode childNode : children) { - stringBuilder.append(" " + hashCode() + " -> " - + childNode.hashCode() + ";" + StringTools.ENDLINE); - } - for (TrieNode childNode : children) { - childNode.appendDotRepresentation(stringBuilder); - } - } - - /** - *

- * Checks if the node is a leaf. - *

- * - * @return true if the node is a leaf, false otherwise. - */ - protected boolean isLeaf() { - return children.isEmpty(); - } - - /** - *

- * Checks if the node is the root. - *

- * - * @return true if the node is the root of the trie, false otherwise - */ - protected boolean isRoot() { - return symbol == null; - } - - /** - *

- * Recursive methods that collects all nodes that are ancestors of leafs and - * stores them in the set. - *

- * - * @param ancestors - * set of all ancestors of leafs - */ - protected void getLeafAncestors(List> ancestors) { - boolean isAncestor = false; - for (TrieNode child : children) { - child.getLeafAncestors(ancestors); - isAncestor |= child.isLeaf(); - } - if (isAncestor) { - ancestors.add(this); - } - } - - /** - *

- * Returns the number of descendants of this node that are leafs. This does - * not only include direct children of this node, but all leafs in the - * sub-trie with this node as root. - *

- * - * @return number of leafs in this sub-trie - */ - protected int getNumLeafs() { - int numLeafs = 0; - for (TrieNode child : children) { - if (child.isLeaf()) { - numLeafs++; - } else { - numLeafs += child.getNumLeafs(); - } - } - return numLeafs; - } - - /** - *

- * Sets the {@link #count} of this node. - *

- *

- * This function should only be used sparingly and very carefully! The count - * is usually maintained automatically by the training procedures. - *

- * - * @param count - * new count - */ - protected void setCount(int count) { - this.count = count; - } - - /** - *

- * Two TrieNodes are defined as equal, if their {@link #count}, - * {@link #symbol}, and {@link #children} are equal. - *

- * - * @see java.lang.Object#equals(java.lang.Object) - */ - @SuppressWarnings("rawtypes") - @Override - public boolean equals(Object other) { - if (other == this) { - return true; - } - if (other instanceof TrieNode) { - TrieNode otherNode = (TrieNode) other; - if (symbol == null) { - return count == otherNode.count && otherNode.symbol == null - && children.equals(otherNode.children); - } else { - return count == otherNode.count - && symbol.equals(((TrieNode) other).symbol) - && children.equals(((TrieNode) other).children); - } - } - return false; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#hashCode() - */ - @Override - public int hashCode() { - int multiplier = 17; - int hash = 42; - if (symbol != null) { - hash = multiplier * hash + symbol.hashCode(); - } - hash = multiplier * hash + count; - hash = multiplier * hash + children.hashCode(); - return hash; - } + /** + *

+ * Id for object serialization. + *

+ */ + private static final long serialVersionUID = 1L; + + /** + *

+ * Counter for the number of occurences of the sequence. + *

+ */ + private int count; + + /** + *

+ * Symbol associated with the node. + *

+ */ + private final T symbol; + + /** + *

+ * Child nodes of this node. If the node is a leaf this collection is empty. + *

+ */ + private Collection> children; + + /** + *

+ * Constructor. Creates a new TrieNode without a symbol associated.
+ * This constructor should only be used to create the root node of the trie! + *

+ */ + TrieNode() { + this.symbol = null; + count = 0; + children = new LinkedList>(); + } + + /** + *

+ * Constructor. Creates a new TrieNode. The symbol must not be null. + *

+ * + * @param symbol + * symbol associated with the trie node + */ + TrieNode(T symbol) { + if (symbol == null) { + throw new InvalidParameterException( + "symbol must not be null. null is reserved for root node!"); + } + this.symbol = symbol; + count = 0; + children = new LinkedList>(); + } + + /** + *

+ * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not be null. + *

+ * + * @param other + */ + TrieNode(TrieNode other) { + if (other == null) { + throw new InvalidParameterException("other must not be null"); + } + symbol = other.symbol; + count = other.count; + children = new LinkedList>(); + for (TrieNode child : other.children) { + children.add(new TrieNode(child)); + } + } + + /** + *

+ * Adds a given subsequence to the trie and increases the counters accordingly. + *

+ * + * @param subsequence + * subsequence whose counters are increased + * @see Trie#add(List) + */ + public void add(List subsequence) { + if (!subsequence.isEmpty()) { + if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by + // the + // recursion/TrieRoot! + throw new AssertionError("Invalid trie operation!"); + } + count++; + subsequence.remove(0); + if (!subsequence.isEmpty()) { + T nextSymbol = subsequence.get(0); + getChildCreate(nextSymbol).add(subsequence); + } + } + } + + /** + *

+ * Returns the symbol associated with the node. + *

+ * + * @return symbol associated with the node + */ + public T getSymbol() { + return symbol; + } + + /** + *

+ * Returns the number of occurences of the sequence represented by the node. + *

+ * + * @return number of occurences of the sequence represented by the node + */ + public int getCount() { + return count; + } + + /** + *

+ * Returns the child of the 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 Trie#getChildCreate(Object) + */ + protected TrieNode getChildCreate(T symbol) { + TrieNode node = getChild(symbol); + if (node == null) { + node = new TrieNode(symbol); + children.add(node); + } + return node; + } + + /** + *

+ * Returns the child of the 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 Trie#getChild(Object) + */ + protected TrieNode getChild(T symbol) { + for (TrieNode child : children) { + if (child.getSymbol().equals(symbol)) { + return child; + } + } + return null; + } + + /** + *

+ * Returns all children of this node. + *

+ * + * @return children of this node + */ + protected Collection> getChildren() { + return children; + } + + /** + *

+ * Searches the sub-trie of this trie node 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 Trie#find(List) + */ + public TrieNode find(List subsequence) { + TrieNode result = null; + if (subsequence.isEmpty()) { + result = this; + } + else { + TrieNode node = getChild(subsequence.get(0)); + if (node != null) { + subsequence.remove(0); + result = node.find(subsequence); + } + } + return result; + } + + /** + *

+ * Returns a collection of all symbols that follow a this node, i.e., the symbols associated + * with the children of this node. + *

+ * + * @return symbols follow this node + * @see TrieNode#getFollowingSymbols() + */ + public Collection getFollowingSymbols() { + Collection followingSymbols = new LinkedList(); + for (TrieNode child : children) { + followingSymbols.add(child.getSymbol()); + } + return followingSymbols; + } + + /** + *

+ * The string representation of a node is {@code symbol.toString()#count} + *

+ * + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + String str = symbol.toString() + " #" + count; + if (!children.isEmpty()) { + str += StringTools.ENDLINE + children.toString(); + } + return str; + } + + /** + *

+ * Generates a {@link Tree} represenation of the trie. + *

+ * + * @param parent + * parent vertex in the generated tree + * @param graph + * complete tree + */ + void getGraph(TrieVertex parent, DelegateTree graph) { + TrieVertex currentVertex; + if (isRoot()) { + currentVertex = new TrieVertex("root"); + graph.addVertex(currentVertex); + } + else { + currentVertex = new TrieVertex(getSymbol().toString() + "#" + getCount()); + graph.addChild(new Edge(), parent, currentVertex); + } + for (TrieNode node : children) { + node.getGraph(currentVertex, graph); + } + } + + /** + *

+ * Appends the current node to the dot representation of the trie. + *

+ * + * @param stringBuilder + * {@link StringBuilder} to which the dot representation is appended + */ + void appendDotRepresentation(StringBuilder stringBuilder) { + String thisSaneId; + if (isRoot()) { + thisSaneId = "root"; + } + else { + thisSaneId = + symbol.toString().replace("\"", "\\\"").replaceAll("[\r\n]", "") + "#" + count; + } + stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId + "\"];" + + StringTools.ENDLINE); + for (TrieNode childNode : children) { + stringBuilder.append(" " + hashCode() + " -> " + childNode.hashCode() + ";" + + StringTools.ENDLINE); + } + for (TrieNode childNode : children) { + childNode.appendDotRepresentation(stringBuilder); + } + } + + /** + *

+ * Checks if the node is a leaf. + *

+ * + * @return true if the node is a leaf, false otherwise. + */ + protected boolean isLeaf() { + return children.isEmpty(); + } + + /** + *

+ * Checks if the node is the root. + *

+ * + * @return true if the node is the root of the trie, false otherwise + */ + protected boolean isRoot() { + return symbol == null; + } + + /** + *

+ * Recursive methods that collects all nodes that are ancestors of leafs and stores them in the + * set. + *

+ * + * @param ancestors + * set of all ancestors of leafs + */ + protected void getLeafAncestors(List> ancestors) { + boolean isAncestor = false; + for (TrieNode child : children) { + child.getLeafAncestors(ancestors); + isAncestor |= child.isLeaf(); + } + if (isAncestor) { + ancestors.add(this); + } + } + + /** + *

+ * Returns the number of descendants of this node that are leafs. This does not only include + * direct children of this node, but all leafs in the sub-trie with this node as root. + *

+ * + * @return number of leafs in this sub-trie + */ + protected int getNumLeafs() { + int numLeafs = 0; + for (TrieNode child : children) { + if (child.isLeaf()) { + numLeafs++; + } + else { + numLeafs += child.getNumLeafs(); + } + } + return numLeafs; + } + + /** + *

+ * Sets the {@link #count} of this node. + *

+ *

+ * This function should only be used sparingly and very carefully! The count is usually + * maintained automatically by the training procedures. + *

+ * + * @param count + * new count + */ + protected void setCount(int count) { + this.count = count; + } + + /** + *

+ * Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and + * {@link #children} are equal. + *

+ * + * @see java.lang.Object#equals(java.lang.Object) + */ + @SuppressWarnings("rawtypes") + @Override + public boolean equals(Object other) { + if (other == this) { + return true; + } + if (other instanceof TrieNode) { + TrieNode otherNode = (TrieNode) other; + if (symbol == null) { + return count == otherNode.count && otherNode.symbol == null && + children.equals(otherNode.children); + } + else { + return count == otherNode.count && symbol.equals(((TrieNode) other).symbol) && + children.equals(((TrieNode) other).children); + } + } + return false; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + int multiplier = 17; + int hash = 42; + if (symbol != null) { + hash = multiplier * hash + symbol.hashCode(); + } + hash = multiplier * hash + count; + hash = multiplier * hash + children.hashCode(); + return hash; + } }