("START");
+
+ /**
+ *
+ * Global end event that can be used to indicate the end of a sequence.
+ */
+ public static final Event ENDEVENT = new Event("END");
+
+ /**
+ *
+ * Type of the event.
+ *
+ */
+ protected String type;
+
+ /**
+ *
Target of the event.
+ */
+ protected String target = null;
+
+ /**
+ *
+ * Short description of the event target.
+ *
+ */
+ protected String targetShort = null;
+
+ /**
+ * Further information about the event that shall be included in its Id.
+ */
+ protected String idInfo = "";
+
+ /**
+ *
+ * Constructor. Creates a new Event with a given type.
+ *
+ *
+ * @param type
+ * type of the event
+ */
+ public Event(String type) {
+ if (type == null) {
+ throw new InvalidParameterException("Event type must not be null");
+ }
+ this.type = type;
+ }
+
+ /**
+ *
+ * Two events are equal, if their {@link #type} and {@link #target} are
+ * equal.
+ *
+ *
+ * See {@link Object#equals(Object)} for further information.
+ *
+ *
+ * @param other
+ * Event that is compared to this
+ * @return true, if events are equal, false otherwise
+ */
+ @Override
+ public boolean equals(Object other) {
+ if (this == other) {
+ return true;
+ }
+ if (other instanceof Event) {
+ Event otherEvent = (Event) other;
+ if (otherEvent.canEqual(this)) {
+ if (type != null) {
+ return targetEquals(otherEvent.target)
+ && type.equals(otherEvent.type);
+ } else {
+ return targetEquals(otherEvent.target)
+ && otherEvent.type == null;
+ }
+ } else {
+ return false;
+ }
+ } else {
+ return false;
+ }
+ }
+
+ public boolean canEqual(Object other) {
+ return (other instanceof Event);
+ }
+
+ /**
+ *
+ * Returns {@link #getStandardId()} as String representation of the event.
+ *
+ *
+ * @return String represenation of the event
+ */
+ @Override
+ public String toString() {
+ return getStandardId();
+ }
+
+ /**
+ * Informations about the event important for its Id that is neither target
+ * nor type.
+ *
+ * @return {@link #idInfo} of the event
+ */
+ public String getIdInfo() {
+ return idInfo;
+ }
+
+ /**
+ *
+ * If {@link #targetShort} is set, a shortend version of the Id is returned
+ * of the form {@link #targetShort}.{@link #type}.{@link #idInfo} is
+ * returned. Otherwise the standard Id is returned (see
+ * {@link #getStandardId()}).
+ *
+ *
+ * @return if available, shortend Id string; {@link #getStandardId()}
+ * otherwise
+ */
+ public String getShortId() {
+ String shortId = null;
+ if (targetShort != null) {
+ shortId = targetShort + "." + getType();
+ if (!"".equals(idInfo)) {
+ shortId += "." + idInfo;
+ }
+ } else {
+ shortId = getStandardId();
+ }
+ return shortId;
+ }
+
+ /**
+ *
+ * Returns the Id string of the event. It has the form {@link #target}.
+ * {@link #type}.{@link #idInfo};
+ *
+ *
+ * @return Id string of the event
+ */
+ public String getStandardId() {
+ String id = "";
+ if (target != null) {
+ id += target + ".";
+ }
+ id += getType();
+ if (!"".equals(idInfo)) {
+ id += "." + idInfo;
+ }
+ return id;
+ }
+
+ /**
+ *
+ * Returns the {@link #target} of the event.
+ *
+ *
+ * @return {@link #target} of the event
+ */
+ public String getTarget() {
+ return target;
+ }
+
+ /**
+ *
+ * Returns the {@link #targetShort} of the event.
+ *
+ *
+ * @return {@link #targetShort} of the event
+ */
+ protected String getTargetShort() {
+ return targetShort;
+ }
+
+ /**
+ *
+ * Returns the {@link #type} of the event.
+ *
+ *
+ * @return {@link #type} of the event
+ */
+ public String getType() {
+ return type;
+ }
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see java.lang.Object#hashCode()
+ */
+ @Override
+ public int hashCode() {
+ int multiplier = 17;
+ int hash = 42;
+ if (type != null) {
+ hash = multiplier * hash + type.hashCode();
+ }
+ hash = multiplier * hash + targetHashCode();
+
+ return hash;
+ }
+
+ /**
+ *
+ * Sets the {@link #idInfo} of the event. The idInfo is optional and
+ * contains information important for the event's Id that is neither target
+ * nor type.
+ *
+ *
+ * @param info
+ * {@link #idInfo} of the event
+ */
+ public void setIdInfo(String info) {
+ idInfo = info;
+ }
+
+ /**
+ *
+ * Sets the target of the event. Once set, the target cannot be changed.
+ *
+ *
+ * @param target
+ * target of the event
+ * @return true, if target was changed, false otherwise
+ */
+ public boolean setTarget(String target) {
+ if (this.target != null) {
+ return false;
+ }
+ this.target = target;
+ return true;
+ }
+
+ /**
+ *
+ * Sets the short description of the event target. Once set, the target
+ * cannot be changed.
+ *
+ *
+ * @param targetShort
+ * short target description
+ * @return true, if target was changed, false otherwise
+ */
+ public boolean setTargetShort(String targetShort) {
+ if (this.targetShort != null) {
+ return false;
+ }
+ this.targetShort = targetShort;
+ return true;
+ }
+
+ /**
+ *
+ * This function is used by {@link #equals(Object)} to determine if the
+ * targets of both events are equal. The standard implementation provided by
+ * this class performs a String comparison between the target strings.
+ *
+ *
+ * Subclasses can override this method to implemented more sophisticated
+ * means for the target comparison, e.g., to account for changes in the
+ * title of a widget.
+ *
+ *
+ * @param otherTarget
+ * other target string to which the target if this event is
+ * compared to
+ * @return true if the targets are equals; false otherwise
+ */
+ protected boolean targetEquals(String otherTarget) {
+ boolean retVal;
+ if (target != null) {
+ retVal = target.equals(otherTarget);
+ } else {
+ retVal = (otherTarget == null);
+ }
+ return retVal;
+ }
+
+ /**
+ *
+ * This function is used by {@link #hashCode()} to determine how the hash of
+ * the {@link #target}. It has to be overridden by subclasses that implement
+ * {@link #targetEquals(String)}, to ensure that the equals/hashCode
+ * contract remains valid.
+ *
+ *
+ * @return hash of the target
+ */
+ protected int targetHashCode() {
+ if (target != null) {
+ return target.hashCode();
+ } else {
+ return 0;
+ }
+ }
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/eventcore/IReplayable.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/eventcore/IReplayable.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/eventcore/IReplayable.java (revision 480)
@@ -0,0 +1,35 @@
+package de.ugoe.cs.quest.eventcore;
+
+import java.io.Serializable;
+
+/**
+ *
+ * This interface is used by {@link ReplayableEvent}to describe how events can
+ * be replayed. It can be used to define a sequence of fine-grained platform
+ * events that make up an abstract event.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public interface IReplayable extends Serializable {
+
+ /**
+ *
+ * Returns a string to be written to the replay script that describes the
+ * replayable platform event.
+ *
+ *
+ * @return string for the replay script
+ */
+ String getReplay();
+
+ /**
+ *
+ * Returns the target of the replayable.
+ *
+ *
+ * @return target of the replayable
+ */
+ String getTarget();
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/eventcore/ReplayableEvent.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/eventcore/ReplayableEvent.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/eventcore/ReplayableEvent.java (revision 480)
@@ -0,0 +1,167 @@
+package de.ugoe.cs.quest.eventcore;
+
+import java.security.InvalidParameterException;
+import java.util.LinkedList;
+import java.util.List;
+
+import de.ugoe.cs.quest.IReplayDecorator;
+
+/**
+ *
+ * Subclass of {@link Event} for events that contain all informations required
+ * for replaying them, i.e., generating scripts that can used for automated
+ * software execution.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ *
+ * @param
+ * Allows only types that extend {@link IReplayable} and is used to
+ * define a list of replayables that describe the replay of the
+ * event.
+ */
+public class ReplayableEvent extends Event {
+
+ /**
+ * Id for object serialization.
+ */
+ private static final long serialVersionUID = 1L;
+
+ /**
+ *
+ * List of {@link IReplayable}s of type T that describes the replay of an
+ * event. The {@link IReplayable}s can be interpreted as sub-events
+ * on the platform level that make up the abstract event.
+ *
+ */
+ protected List replayEvents = new LinkedList();;
+
+ /**
+ *
+ * Defines whether the replay is valid or invalid. It may be invalid, e.g.,
+ * due to errors during the generation of the event or lack of vital
+ * information.
+ *
+ */
+ protected boolean replayValid = true;
+
+ /**
+ *
+ * {@link IReplayDecorator} used when replays of this type are written.
+ *
+ */
+ protected IReplayDecorator decorator = null;
+
+ /**
+ *
+ * Constructor. Creates a new event with the given type.
+ *
+ *
+ * @param type
+ * type of the event
+ * @see Event#Event(String)
+ */
+ public ReplayableEvent(String type) {
+ super(type);
+ }
+
+ /**
+ *
+ * Adds a new {@link IReplayable} of type T to the replay sequence.
+ *
+ *
+ * @param replayable
+ * element that is added to the sequence
+ * @throws InvalidParameterException
+ * thrown is replayable is null
+ */
+ public void addReplayEvent(T replayable) {
+ if (replayable == null) {
+ throw new InvalidParameterException("replayble must not be null");
+ }
+ replayEvents.add(replayable);
+ }
+
+ /**
+ *
+ * Adds a {@link List}ist of {@link IReplayable} to the replay sequence.
+ *
+ *
+ * @param generatedReplaySeq
+ * {@link List} that is added to the sequence
+ * @throws InvalidParameterException
+ * thrown if generatedReplaySeq is null
+ */
+ public void addReplaySequence(List generatedReplaySeq) {
+ if (generatedReplaySeq == null) {
+ throw new InvalidParameterException(
+ "generatedReplaySeq must not be null");
+ }
+ replayEvents.addAll(generatedReplaySeq);
+ }
+
+ /**
+ *
+ * Returns the {@link IReplayDecorator} of the event.
+ *
+ *
+ * @return {@link IReplayDecorator} of the event; null if no decorator has
+ * been set
+ */
+ public IReplayDecorator getReplayDecorator() {
+ return decorator;
+ }
+
+ /**
+ *
+ * Returns a the list of replay events.
+ *
+ *
+ * The return value is a copy of the list used internally!
+ *
+ *
+ * @return list of replay events.
+ */
+ public List getReplayMessages() {
+ return new LinkedList(replayEvents);
+ }
+
+ /**
+ *
+ * Returns whether the replay is valid or not.
+ *
+ *
+ * @return true, if replay is valid; false otherwise.
+ */
+ public boolean hasValidReplay() {
+ return replayValid;
+ }
+
+ /**
+ *
+ * Marks the replay as invalid. Once marked as invalid, it remains so and
+ * cannot be changed back to valid.
+ *
+ */
+ public void invalidateReplay() {
+ replayValid = false;
+ }
+
+ /**
+ *
+ * Sets the {@link IReplayDecorator} associated with the event.
+ *
+ *
+ * @param decorator
+ * decorator associated with the event
+ */
+ public void setDecorator(IReplayDecorator decorator) {
+ this.decorator = decorator;
+ }
+
+ @Override
+ public boolean canEqual(Object other) {
+ return (other instanceof ReplayableEvent);
+ }
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java (revision 480)
@@ -0,0 +1,80 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ *
+ * 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.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class DeterministicFiniteAutomaton extends FirstOrderMarkovModel {
+
+ /**
+ *
+ * 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);
+ }
+
+ /**
+ *
+ * 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);
+ }
+
+ Collection> followers = trie.getFollowingSymbols(contextCopy);
+
+ if (followers.size() != 0 && followers.contains(symbol)) {
+ result = 1.0d / followers.size();
+ }
+
+ return result;
+ }
+
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java (revision 480)
@@ -0,0 +1,264 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.util.StringTools;
+import de.ugoe.cs.util.console.Console;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.SparseMultigraph;
+import edu.uci.ics.jung.graph.util.EdgeType;
+
+import Jama.Matrix;
+
+/**
+ *
+ * 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()}).
+ *
+ *
+ * @author Steffen Herbold
+ * @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.getShortId().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.getShortId();
+ List> context = new ArrayList>();
+ context.add(symbol);
+
+ Collection> followers = trie.getFollowingSymbols(context);
+
+ for (Event follower : followers) {
+ String to = follower.getShortId();
+ 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-events/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java (revision 480)
@@ -0,0 +1,87 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ *
+ * Implements high-order Markov models.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class HighOrderMarkovModel extends TrieBasedModel {
+
+ /**
+ *
+ * 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);
+ }
+
+ /**
+ *
+ * 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);
+ }
+
+ 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);
+ }
+
+ return result;
+ }
+
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java (revision 480)
@@ -0,0 +1,22 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+/**
+ *
+ * Models implementing this interface provide a graph representation of
+ * themselves as a {@link String} with Dot syntax.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public interface IDotCompatible {
+
+ /**
+ *
+ * Returns a Dot representation of the model.
+ *
+ *
+ * @return string with Dot syntax that describes the model.
+ */
+ public abstract String getDotRepresentation();
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java (revision 480)
@@ -0,0 +1,40 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.List;
+
+/**
+ *
+ * This interface defines basic functions for classes that implement a memory
+ * about the recent events of a sequences.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ *
+ * @param
+ * Type of the sequence elements that are memorized.
+ */
+public interface IMemory {
+
+ /**
+ * 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);
+
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java (revision 480)
@@ -0,0 +1,194 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.io.Serializable;
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.List;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ *
+ * This interface defines the functionalities provided by stochastic processes.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+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 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} 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.
+ *
+ * @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.
+ *
+ * @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);
+
+ /**
+ *
+ * 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 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 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-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java (revision 480)
@@ -0,0 +1,95 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ *
+ * 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.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ *
+ * @param
+ * Type which is memorized.
+ */
+public class IncompleteMemory implements IMemory {
+
+ /**
+ *
+ * Maximum length of the memory.
+ *
+ */
+ private int length;
+
+ /**
+ *
+ * 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();
+ }
+
+ /*
+ * (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
+ }
+ }
+
+ /**
+ *
+ * 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-events/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java (revision 480)
@@ -0,0 +1,137 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.eventcore.ReplayableEvent;
+
+/**
+ *
+ * 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.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class ModelFlattener {
+
+ private static final String EVENT_SEPARATOR = "-=-";
+
+ 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;
+ }
+
+ /**
+ *
+ * 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().getStandardId();
+ 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(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()
+ .getStandardId());
+ TrieNode> firstOrderTransitionChild = firstOrderNode
+ .getChildCreate(new Event(transitionID
+ .toString()));
+ firstOrderTransitionChild.setCount(transitionChild
+ .getCount());
+ }
+ }
+ }
+ }
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java (revision 480)
@@ -0,0 +1,200 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ *
+ * Implements Prediction by Partial Match (PPM) based on the following formula
+ * (LaTeX-style notation):
+ *
+ * @author Steffen Herbold
+ *
+ */
+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:
+ *
+ * @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-events/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java (revision 480)
@@ -0,0 +1,472 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.io.Serializable;
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+
+import de.ugoe.cs.util.StringTools;
+
+import edu.uci.ics.jung.graph.DelegateTree;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.Tree;
+
+/**
+ *
+ * This class implements a trie , i.e., a tree of sequences that the
+ * occurence of subsequences up to a predefined length. This length is the trie
+ * order.
+ *
+ *
+ * @author Steffen Herbold
+ *
+ * @param
+ * Type of the symbols that are stored in the trie.
+ *
+ * @see TrieNode
+ */
+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.
+ *
+ * @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-events/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java (revision 480)
@@ -0,0 +1,416 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.Trie.Edge;
+import de.ugoe.cs.quest.usageprofiles.Trie.TrieVertex;
+import edu.uci.ics.jung.graph.Tree;
+
+/**
+ *
+ * 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)}.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+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();
+ }
+ }
+}
Index: /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java
===================================================================
--- /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java (revision 480)
+++ /trunk/quest-core-events/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java (revision 480)
@@ -0,0 +1,443 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.io.Serializable;
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+
+import de.ugoe.cs.quest.usageprofiles.Trie.Edge;
+import de.ugoe.cs.quest.usageprofiles.Trie.TrieVertex;
+import de.ugoe.cs.util.StringTools;
+import edu.uci.ics.jung.graph.DelegateTree;
+import edu.uci.ics.jung.graph.Tree;
+
+/**
+ *
+ * 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.
+ *
+ *
+ * @author Steffen Herbold
+ *
+ * @param
+ * Type of the symbols that are stored in the trie.
+ * @see Trie
+ */
+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;
+ }
+}