("START");
-
- /**
- *
- * Global end event that can be used to indicate the end of a sequence.
- */
- public static final Event ENDEVENT = new Event("END");
+public class Event {
/**
@@ -42,11 +10,12 @@
*
*/
- protected String type;
-
+ private String type;
+
/**
- * Target of the event.
+ *
+ * Target of the event.
*/
- protected String target = null;
-
+ private String target = null;
+
/**
*
@@ -54,57 +23,24 @@
*
*/
- protected String targetShort = null;
+ private 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
- */
+
+
+ private String idInfo = null;
+
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) {
+ 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;
- }
+ Event otherToken = (Event) other;
+ return otherToken.type.equals(this.type)
+ && otherToken.target.equals(this.target);
} else {
return false;
@@ -112,69 +48,22 @@
}
- 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;
+ if (targetShort!=null) {
+ shortId = targetShort+"."+getType();
+ if (idInfo!=null) {
+ 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)) {
+ String id = target + "." + getType();
+ if ( idInfo!=null ) {
id += "." + idInfo;
}
@@ -182,79 +71,41 @@
}
- /**
- *
- * 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() {
+
+ public 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 + type.hashCode();
+ if( target!=null ) {
+ hash = multiplier * hash + target.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
+ *
+ * @param target target of the event
* @return true, if target was changed, false otherwise
*/
public boolean setTarget(String target) {
- if (this.target != null) {
+ if( this.target!=null ) {
return false;
}
@@ -262,17 +113,14 @@
return true;
}
-
+
/**
*
- * Sets the short description of the event target. Once set, the target
- * cannot be changed.
- *
- *
- * @param targetShort
- * short target description
+ * 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) {
+ if( this.targetShort!=null ) {
return false;
}
@@ -280,48 +128,3 @@
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/EventBenchCore/src/de/ugoe/cs/eventbench/data/IReplayable.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/IReplayable.java (revision 425)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/IReplayable.java (revision 1)
@@ -1,35 +1,8 @@
package de.ugoe.cs.eventbench.data;
-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
- */
+public interface IReplayable {
+
+ String getReplayXml();
+
String getTarget();
}
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/ReplayableEvent.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/ReplayableEvent.java (revision 425)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/ReplayableEvent.java (revision 1)
@@ -1,167 +1,46 @@
package de.ugoe.cs.eventbench.data;
-import java.security.InvalidParameterException;
import java.util.LinkedList;
import java.util.List;
-import de.ugoe.cs.eventbench.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;
+ private List replayEvents = new LinkedList();;
- /**
- *
- * 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)
- */
+ private boolean replayValid = true;
+
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;
+ public void addReplayEvent(T replayable) {
+ replayEvents.add(replayable);
}
-
+
/**
*
* Returns a the list of replay events.
- *
+ *
*
* The return value is a copy of the list used internally!
*
- *
- * @return list of replay events.
+ * @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/EventBenchCore/src/de/ugoe/cs/eventbench/markov/DotPrinter.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/DotPrinter.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/DotPrinter.java (revision 1)
@@ -0,0 +1,5 @@
+package de.ugoe.cs.eventbench.markov;
+
+public interface DotPrinter {
+ public abstract void printDot();
+}
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/IMemory.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/IMemory.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/IMemory.java (revision 1)
@@ -0,0 +1,40 @@
+package de.ugoe.cs.eventbench.markov;
+
+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/EventBenchCore/src/de/ugoe/cs/eventbench/markov/IncompleteMemory.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/IncompleteMemory.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/IncompleteMemory.java (revision 1)
@@ -0,0 +1,33 @@
+package de.ugoe.cs.eventbench.markov;
+
+import java.util.LinkedList;
+import java.util.List;
+
+public class IncompleteMemory implements IMemory {
+
+ private int length;
+
+ private List history;
+
+ public IncompleteMemory(int length) {
+ this.length = length;
+ history = new LinkedList();
+ }
+
+ @Override
+ public void add(T state) {
+ if( history.size()==length ) {
+ history.remove(0);
+ }
+ history.add(state);
+ }
+
+ @Override
+ public List getLast(int num) {
+ return new LinkedList(history); // defensive copy
+ }
+
+ public int getLength() {
+ return history.size();
+ }
+}
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/MarkovModel.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/MarkovModel.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/MarkovModel.java (revision 1)
@@ -0,0 +1,242 @@
+package de.ugoe.cs.eventbench.markov;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import Jama.Matrix;
+
+import de.ugoe.cs.eventbench.data.Event;
+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;
+
+public class MarkovModel implements DotPrinter {
+
+ private State initialState;
+ private State endState;
+
+ private List states;
+ private List stateIdList;
+
+ private Random r;
+
+ final static int MAX_STATDIST_ITERATIONS = 1000;
+
+ /**
+ *
+ * Default constructor. Creates a new random number generator.
+ *
+ */
+ public MarkovModel() {
+ this(new Random());
+ }
+
+ /**
+ *
+ * Creates a new {@link MarkovModel} with a predefined random number generator.
+ *
+ *
+ * @param r random number generator
+ */
+ public MarkovModel(Random r) {
+ this.r = r; // defensive copy would be better, but constructor Random(r) does not seem to exist.
+ }
+
+ public void printRandomWalk() {
+ State currentState = initialState;
+ IMemory history = new IncompleteMemory(5); // this is NOT used here, just for testing ...
+ history.add(currentState);
+ Console.println(currentState.getId());
+ while(!currentState.equals(endState)) {
+ currentState = currentState.getNextState();
+ Console.println(currentState.getId());
+ history.add(currentState);
+ }
+ }
+
+ public List> randomSequence() {
+ List> sequence = new LinkedList>();
+ State currentState = initialState;
+ if( currentState.getAction()!=null ) {
+ sequence.add(currentState.getAction());
+ }
+ System.out.println(currentState.getId());
+ while(!currentState.equals(endState)) {
+ currentState = currentState.getNextState();
+ if( currentState.getAction()!=null ) {
+ sequence.add(currentState.getAction());
+ }
+ System.out.println(currentState.getId());
+ }
+ return sequence;
+ }
+
+ public void printDot() {
+ int numUnprintableStates = 0;
+ System.out.println("digraph model {");
+ for( State state : states ) {
+ if( state instanceof DotPrinter ) {
+ ((DotPrinter) state).printDot();
+ } else {
+ numUnprintableStates++;
+ }
+ }
+ System.out.println('}');
+ if( numUnprintableStates>0 ) {
+ Console.println("" + numUnprintableStates + "/" + states.size() + "were unprintable!");
+ }
+ }
+
+ public Graph getGraph() {
+ Graph graph = new SparseMultigraph();
+
+ for( State state : states) {
+ try {
+ SimpleState simpleState = (SimpleState) state;
+ String from = simpleState.getShortId();
+ for( int i=0 ; i>> sequences) {
+ Event fromElement = null;
+ Event toElement = null;
+ SimpleState fromState;
+ SimpleState toState;
+
+ states = new ArrayList();
+ stateIdList = new ArrayList();
+ initialState = new SimpleState("GLOBALSTARTSTATE", null);
+ initialState.setRandom(r);
+ states.add(initialState);
+ stateIdList.add("GLOBALSTARTSTATE");
+ endState = new SimpleState("GLOBALENDSTATE", null);
+ endState.setRandom(r);
+ states.add(endState);
+ stateIdList.add("GLOBALENDSTATE");
+ for( List> sequence : sequences ) {
+ for( int i=0; i action) {
+ SimpleState state = null;
+ String id = action.getStandardId();
+ String idShort = action.getShortId();
+ int index = stateIdList.indexOf(id);
+ if( index!=-1 ) {
+ state = (SimpleState) states.get(index);
+ } else {
+ state = new SimpleState(id, action, idShort);
+ state.setRandom(r);
+ states.add(state);
+ stateIdList.add(id);
+ }
+ return state;
+ }
+
+ ///////////////////////////////////////////////////////////
+
+ // states must be SimpleState, this functions will throw bad cast exceptions
+ public double calcEntropy() {
+ int numStates = states.size();
+ // create transmission matrix
+ Matrix transmissionMatrix = new Matrix(numStates, numStates);
+ for( int i=0 ; i1 ) {
+ 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 transitionProbs;
+ List toStates;
+
+ // members for learning
+ private int transitionsObserved;
+
+ private String idShort = null;
+
+ public SimpleState(String id, Event action) {
+ super(id, action);
+ transitionsObserved = 0;
+ toStates = new ArrayList();
+ transitionProbs = new ArrayList();
+ }
+
+ public SimpleState(String id, Event action, String idShort) {
+ this(id, action);
+ this.idShort = idShort;
+ }
+
+ @Override
+ public State getNextState() {
+ double randVal = rand.nextDouble();
+ double probSum = 0;
+ int index = 0;
+ while( index=0 ) {
+ prob = transitionProbs.get(index);
+ }
+ return prob;
+ }
+
+ public String getShortId() {
+ String shortId;
+ if( idShort!=null ) {
+ shortId = idShort;
+ } else {
+ shortId = getId();
+ }
+ return shortId;
+ }
+
+ @Override
+ public void printDot() {
+ final String thisSaneId = getShortId().replace("\"", "\\\"").replaceAll("[\r\n]","");
+ System.out.println(" " + hashCode() + " [label=\""+thisSaneId+"\"];");
+ for(int i=0 ; i " + toStates.get(i).hashCode() + " ");
+ System.out.println("[label=\"" + transitionProbs.get(i) + "\"];");
+ }
+
+ }
+
+}
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/State.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/State.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/State.java (revision 1)
@@ -0,0 +1,97 @@
+package de.ugoe.cs.eventbench.markov;
+
+import java.util.Random;
+
+import de.ugoe.cs.eventbench.data.Event;
+
+public abstract class State {
+
+ /**
+ * {@link Event} associated with the state.
+ */
+ private Event action;
+
+ /**
+ * Identifier of the state
+ */
+ private String id;
+
+ /**
+ * Random number generator used for state transmissions.
+ */
+ protected Random rand;
+
+ /**
+ * State transmission function to be used by models.
+ * @return
+ */
+ public abstract State getNextState();
+
+ /**
+ * Creates a new State object. The id should be unique.
+ * @param id identifier string of the state
+ */
+ protected State(String id, Event action) {
+ this.id = id;
+ this.action = action;
+ }
+
+ /**
+ * Dummy method for history-less state implementations.
+ */
+ public void setHistoryObject() {}
+
+ /**
+ * Defines a random number generator to be used by getNextState.
+ * @param r Random number generator
+ */
+ public void setRandom(Random r) {
+ rand = r;
+ }
+
+ /**
+ * Returns the id of the state.
+ * @return id of the state
+ */
+ public String getId() {
+ return id;
+ }
+
+ /**
+ * The {@link Event} associated with this state.
+ * @return {@link Event} associated with this state
+ */
+ public Event getAction() {
+ return action;
+ }
+
+ /**
+ * Two states are equal if their id string is equal.
+ */
+ @Override
+ public boolean equals(Object other) {
+ if( other==this ) {
+ return true;
+ }
+ boolean isEqual = false;
+ if( other instanceof State ) {
+ isEqual = id.equals(((State) other).id);
+ }
+ return isEqual;
+ }
+
+
+ /* (non-Javadoc)
+ * @see java.lang.Object#hashCode()
+ */
+ @Override
+ public int hashCode() {
+ int multiplier = 37;
+ int hash = 42;
+
+ hash = multiplier*hash + id.hashCode();
+
+ return hash;
+ }
+
+}
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java (revision 1)
@@ -0,0 +1,106 @@
+package de.ugoe.cs.eventbench.ppm;
+
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import de.ugoe.cs.eventbench.data.Event;
+import de.ugoe.cs.eventbench.markov.IncompleteMemory;
+import de.ugoe.cs.util.console.Console;
+
+public class PredictionByPartialMatch {
+
+ private String initialSymbol = "GLOBALSTARTSTATE";
+ private String endSymbol = "GLOBALENDSTATE";
+
+ private int maxOrder = 3;
+
+ private Trie trie;
+
+ private Set knownSymbols;
+
+ // the training is basically the generation of the trie
+ public void train(List>> sequences) {
+ trie = new Trie();
+ knownSymbols = new LinkedHashSet();
+ knownSymbols.add(initialSymbol);
+ knownSymbols.add(endSymbol);
+
+ for(List> sequence : sequences) {
+ IncompleteMemory latestActions = new IncompleteMemory(maxOrder); // TODO need to check if it should be maxOrder+1
+ latestActions.add(initialSymbol);
+ for(Event currentAction : sequence) {
+ String currentId = currentAction.getStandardId();
+ latestActions.add(currentId);
+ knownSymbols.add(currentId);
+ if( latestActions.getLength()==maxOrder ) { // FIXME needs special case for sequences shorter than maxOrder
+ trie.add(latestActions.getLast(maxOrder));
+ }
+ }
+ latestActions.add(endSymbol);
+ if( latestActions.getLength()==maxOrder ) { // FIXME needs special case for sequences shorter than maxOrder
+ trie.add(latestActions.getLast(maxOrder));
+ }
+ }
+ }
+
+ public void printRandomWalk(Random r) {
+ IncompleteMemory context = new IncompleteMemory(maxOrder-1);
+
+ context.add(initialSymbol);
+
+ String currentState = initialSymbol;
+
+ Console.println(currentState);
+ while(!endSymbol.equals(currentState)) {
+ double randVal = r.nextDouble();
+ double probSum = 0.0;
+ List currentContext = context.getLast(maxOrder);
+ for( String symbol : knownSymbols ) {
+ probSum += getProbability(currentContext, symbol);
+ if( probSum>=randVal ) {
+ currentContext.add(symbol);
+ currentState = symbol;
+ Console.println(currentState);
+ break;
+ }
+ }
+ }
+ }
+
+ private double getProbability(List context, String symbol) {
+ double result = 0.0;
+ int countContextSymbol = 0;
+ List contextSuffix = trie.getContextSuffix(context);
+ if( contextSuffix.isEmpty() ) {
+ result = 1.0d / knownSymbols.size();
+ } else {
+ countContextSymbol = trie.getCount(contextSuffix, symbol);
+ List followers = trie.getFollowingSymbols(contextSuffix);
+ int countContextFollowers = 0;
+ for( String follower : followers ) {
+ countContextFollowers += trie.getCount(contextSuffix, follower);
+ }
+
+ if( followers.isEmpty() ) {
+ throw new AssertionError("Invalid return value of getContextSuffix!");
+ }
+ if( countContextSymbol!=0 ) {
+ result = ((double) countContextSymbol) / (followers.size()+countContextFollowers);
+ } else { // escape
+ double probEscape = ((double) followers.size()) / (followers.size()+countContextFollowers);
+ contextSuffix.remove(0);
+ double probSuffix = getProbability(contextSuffix, symbol);
+ result = probEscape*probSuffix;
+ }
+ }
+
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return trie.toString();
+ }
+}
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java (revision 1)
@@ -0,0 +1,100 @@
+package de.ugoe.cs.eventbench.ppm;
+
+import java.util.LinkedList;
+import java.util.List;
+
+public class Trie {
+
+ private List> children = new LinkedList>();
+
+
+ public void add(List subsequence) {
+ if( !subsequence.isEmpty() ) {
+ subsequence = new LinkedList(subsequence); // copy list!
+ T firstSymbol = subsequence.get(0);
+ getChildCreate(firstSymbol).add(subsequence);
+ }
+ }
+
+ // FIXME clones of TrieNode.getChildCreate
+ protected TrieNode getChildCreate(T symbol) {
+ TrieNode node = getChild(symbol);
+ if( node==null ) {
+ node = new TrieNode(symbol);
+ children.add(node);
+ }
+ return node;
+ }
+
+ // FIXME clones of TrieNode.getChild
+ protected TrieNode getChild(T symbol) {
+ for( TrieNode child : children ) {
+ if( child.getSymbol().equals(symbol) ) {
+ return child;
+ }
+ }
+ return null;
+ }
+
+ public int getCount(List sequence) {
+ int count = 0;
+ TrieNode node = find(sequence);
+ if( node!=null ) {
+ count = node.getCount();
+ }
+ return count;
+ }
+
+ public int getCount(List sequence, T follower) {
+ List tmpSequence = new LinkedList(sequence);
+ tmpSequence.add(follower);
+ return getCount(tmpSequence);
+
+ }
+
+ public TrieNode find(List sequence) {
+ TrieNode result = null;
+ if( !sequence.isEmpty() ) {
+ TrieNode node = getChild(sequence.get(0));
+ if( node!=null ) {
+ result = node.find(sequence);
+ }
+ }
+ return result;
+ }
+
+ public List getFollowingSymbols(List sequence) {
+ List result = null;
+ TrieNode node = find(sequence);
+ if( node!=null ) {
+ result = node.getFollowingSymbols();
+ }
+ return result;
+ }
+
+ public List getContextSuffix(List context) {
+ List contextSuffix = new LinkedList(context);
+ 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;
+ }
+ }
+ contextSuffix.remove(0);
+ }
+ }
+
+ return contextSuffix;
+ }
+
+ @Override
+ public String toString() {
+ return children.toString();
+ }
+}
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java (revision 1)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java (revision 1)
@@ -0,0 +1,99 @@
+package de.ugoe.cs.eventbench.ppm;
+
+import java.security.InvalidParameterException;
+import java.util.LinkedList;
+import java.util.List;
+
+import de.ugoe.cs.util.StringTools;
+
+
+class TrieNode {
+
+ private int count;
+ private final T symbol;
+
+ private List> children;
+
+ public TrieNode(T symbol) {
+ if( symbol==null ) {
+ throw new InvalidParameterException("symbol must not be null.");
+ }
+ this.symbol = symbol;
+ count = 0;
+ children = new LinkedList>();
+ }
+
+ 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);
+ }
+ }
+ }
+
+ public T getSymbol() {
+ return symbol;
+ }
+
+ public int getCount() {
+ return count;
+ }
+
+ protected TrieNode getChildCreate(T symbol) {
+ TrieNode node = getChild(symbol);
+ if( node==null ) {
+ node = new TrieNode(symbol);
+ children.add(node);
+ }
+ return node;
+ }
+
+ protected TrieNode getChild(T symbol) {
+ for( TrieNode child : children ) {
+ if( child.getSymbol().equals(symbol) ) {
+ return child;
+ }
+ }
+ return null;
+ }
+
+
+
+ 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;
+ }
+
+ public List getFollowingSymbols() {
+ List followingSymbols = new LinkedList();
+ for( TrieNode child : children ) {
+ followingSymbols.add(child.getSymbol());
+ }
+ return followingSymbols;
+ }
+
+ @Override
+ public String toString() {
+ String str = symbol.toString()+" #"+count;
+ if( !children.isEmpty() ) {
+ str += StringTools.ENDLINE + children.toString();
+ }
+ return str;
+ }
+
+}