Index: /trunk/EventBenchCore/.classpath
===================================================================
--- /trunk/EventBenchCore/.classpath	(revision 4)
+++ /trunk/EventBenchCore/.classpath	(revision 5)
@@ -20,4 +20,5 @@
 	<classpathentry kind="lib" path="lib/vecmath-1.3.1.jar"/>
 	<classpathentry kind="lib" path="lib/wstx-asl-3.2.6.jar"/>
+	<classpathentry kind="lib" path="lib/commons-codec-1.5.jar"/>
 	<classpathentry combineaccessrules="false" kind="src" path="/JavaHelperLib"/>
 	<classpathentry kind="output" path="bin"/>
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java	(revision 4)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java	(revision 5)
@@ -26,5 +26,5 @@
 
 
-	private String idInfo = null;
+	private String idInfo = "";
 	
 	public Event(String type) {
@@ -59,5 +59,5 @@
 		if (targetShort!=null) {
 			shortId = targetShort+"."+getType();
-			if (idInfo!=null) {
+			if (idInfo!="") {
 				shortId += "."+idInfo;
 			}
@@ -68,5 +68,5 @@
 	public String getStandardId() {
 		String id = target + "." + getType();
-		if ( idInfo!=null ) {
+		if ( idInfo!="" ) {
 			id += "." + idInfo;
 		}
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java	(revision 4)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java	(revision 5)
@@ -1,5 +1,7 @@
 package de.ugoe.cs.eventbench.ppm;
 
+import java.util.ArrayList;
 import java.util.LinkedHashSet;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Random;
@@ -12,6 +14,6 @@
 public class PredictionByPartialMatch {
 	
-	private String initialSymbol = "GLOBALSTARTSTATE";
-	private String endSymbol = "GLOBALENDSTATE";
+	private String initialSymbol = "GS";
+	private String endSymbol = "GE";
 	
 	private int maxOrder = 3;
@@ -20,4 +22,8 @@
 	
 	private Set<String> knownSymbols;
+	
+	private double probEscape = 0.2d; // TODO getter/setter - steering parameter!
+	
+	private Random r = new Random(); // TODO should be defined in the constructor
 	
 	// the training is basically the generation of the trie
@@ -29,25 +35,112 @@
 		
 		for(List<Event<?>> sequence : sequences) {
-			IncompleteMemory<String> latestActions = new IncompleteMemory<String>(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
+			List<String> stringSequence = new LinkedList<String>();
+			stringSequence.add(initialSymbol);
+			for( Event<?> event : sequence ) {
+				stringSequence.add(event.getStandardId());
+			}
+			stringSequence.add(endSymbol);
+			
+			trainStringTrie(stringSequence);
+		}
+	}
+	
+	private void trainStringTrie(List<String> sequence) {
+		knownSymbols = new LinkedHashSet<String>();		
+		IncompleteMemory<String> latestActions = new IncompleteMemory<String>(maxOrder);
+		int i=0;
+		for(String currentAction : sequence) {
+			String currentId = currentAction;
+			latestActions.add(currentId);
+			knownSymbols.add(currentId);
+			i++;
+			if( i>=maxOrder ) {
 				trie.add(latestActions.getLast(maxOrder));
 			}
 		}
-	}
-	
-	public void printRandomWalk(Random r) {
+		int sequenceLength = sequence.size();
+		for( int j=maxOrder-1 ; j>0 ; j-- ) {
+			trie.add(sequence.subList(sequenceLength-j, sequenceLength));
+		}
+	}
+	
+	public void testStuff() {
+		// basically an inline unit test without assertions but manual observation
+		List<String> list = new ArrayList<String>();
+		list.add(initialSymbol);
+		list.add("a");
+		list.add("b");
+		list.add("r");
+		list.add("a");
+		list.add("c");
+		list.add("a");
+		list.add("d");
+		list.add("a");
+		list.add("b");
+		list.add("r");
+		list.add("a");
+		list.add(endSymbol);
+		
+		PredictionByPartialMatch model = new PredictionByPartialMatch();
+		model.trie = new Trie<String>();
+		model.trainStringTrie(list);
+		model.trie.display();
+		Console.println("------------------------");
+		model.randomSequence();/*
+		Console.println("------------------------");
+		model.randomSequence();
+		Console.println("------------------------");
+		model.randomSequence();
+		Console.println("------------------------");*/
+		
+		List<String> context = new ArrayList<String>();
+		String symbol = "a";
+		// expected: 5
+		Console.traceln(""+model.trie.getCount(context, symbol));
+		
+		// expected: 0
+		context.add("b");
+		Console.traceln(""+model.trie.getCount(context, symbol));
+		
+		// expected: 2
+		context.add("r");
+		Console.traceln(""+model.trie.getCount(context, symbol));
+		
+		// exptected: [b, r]
+		context = new ArrayList<String>();
+		context.add("a");
+		context.add("b");
+		context.add("r");
+		Console.traceln(model.trie.getContextSuffix(context).toString());
+		
+		// exptected: []
+		context = new ArrayList<String>();
+		context.add("e");
+		Console.traceln(model.trie.getContextSuffix(context).toString());
+		
+		// exptected: {a, b, c, d, r}
+		context = new ArrayList<String>();
+		Console.traceln(model.trie.getFollowingSymbols(context).toString());
+		
+		// exptected: {b, c, d}
+		context = new ArrayList<String>();
+		context.add("a");
+		Console.traceln(model.trie.getFollowingSymbols(context).toString());
+		
+		// exptected: []
+		context = new ArrayList<String>();
+		context.add("a");
+		context.add("b");
+		context.add("r");
+		Console.traceln(model.trie.getFollowingSymbols(context).toString());
+	}
+	
+	// TODO needs to be changed from String to <? extends Event>
+	public List<String> randomSequence() {
+		List<String> sequence = new LinkedList<String>();
+		
 		IncompleteMemory<String> context = new IncompleteMemory<String>(maxOrder-1);
-		
 		context.add(initialSymbol);
+		sequence.add(initialSymbol);
 		
 		String currentState = initialSymbol;
@@ -61,5 +154,40 @@
 				probSum += getProbability(currentContext, symbol);
 				if( probSum>=randVal ) {
-					currentContext.add(symbol);
+					context.add(symbol);
+					currentState = symbol;
+					sequence.add(currentState);
+					break;
+				}
+			}
+		}
+		return sequence;
+	}
+	
+	/*public void printRandomWalk(Random r) {
+		IncompleteMemory<String> context = new IncompleteMemory<String>(maxOrder-1);
+		
+		context.add(initialSymbol);
+		
+		String currentState = initialSymbol;
+		
+		Console.println(currentState);
+		while(!endSymbol.equals(currentState)) {
+			double randVal = r.nextDouble();
+			double probSum = 0.0;
+			List<String> currentContext = context.getLast(maxOrder);
+			// DEBUG //
+			Console.traceln("Context: " + currentContext.toString());
+			double tmpSum = 0.0d;
+			for( String symbol : knownSymbols ) {
+				double prob = getProbability(currentContext, symbol);
+				tmpSum += prob;
+				Console.traceln(symbol + ": " + prob);
+			}
+			Console.traceln("Sum: " + tmpSum);
+			// DEBUG-END //
+			for( String symbol : knownSymbols ) {
+				probSum += getProbability(currentContext, symbol);
+				if( probSum>=randVal-0.3 ) {
+					context.add(symbol);
 					currentState = symbol;
 					Console.println(currentState);
@@ -68,6 +196,41 @@
 			}
 		}
-	}
-	
+	}*/
+	
+	private double getProbability(List<String> context, String symbol) {
+		// FIXME needs exception handling for unknown symbols
+		// if the symbol is not contained in the trie, context.remove(0) will fail
+		double result = 0.0d;
+		double resultCurrentContex = 0.0d;
+		double resultShorterContex = 0.0d;
+		
+		List<String> contextCopy = new LinkedList<String>(context); // defensive copy
+
+	
+		List<String> followers = trie.getFollowingSymbols(contextCopy); // \Sigma'
+		int sumCountFollowers = 0; // N(s\sigma')
+		for( String follower : followers ) {
+			sumCountFollowers += trie.getCount(contextCopy, follower);
+		}
+		
+		int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
+		if( contextCopy.size()==0 ) {
+			resultCurrentContex = ((double) countSymbol) / sumCountFollowers;
+		} else {
+			resultCurrentContex = ((double) countSymbol / sumCountFollowers)*(1-probEscape);
+			contextCopy.remove(0); 
+			double probSuffix = getProbability(contextCopy, symbol);
+			if( followers.size()==0 ) {
+				resultShorterContex = probSuffix;
+			} else {
+				resultShorterContex = probEscape*probSuffix;
+			}
+		}
+		result = resultCurrentContex+resultShorterContex;
+		
+		return result;
+	}
+	
+	/*
 	private double getProbability(List<String> context, String symbol) {
 		double result = 0.0; 
@@ -75,5 +238,6 @@
 		List<String> contextSuffix = trie.getContextSuffix(context);
 		if( contextSuffix.isEmpty() ) {
-			result = 1.0d / knownSymbols.size(); 
+			// unobserved context! everything is possible... assuming identical distribution
+			result = 1.0d / knownSymbols.size(); // why 1.0 and not N(symbol)
 		} else {
 			countContextSymbol = trie.getCount(contextSuffix, symbol);
@@ -85,5 +249,5 @@
 			
 			if( followers.isEmpty() ) {
-				throw new AssertionError("Invalid return value of getContextSuffix!");
+				throw new AssertionError("Invalid return value of trie.getContextSuffix()!");
 			}
 			if( countContextSymbol!=0 ) {
@@ -91,5 +255,5 @@
 			} else { // escape
 				double probEscape = ((double) followers.size()) / (followers.size()+countContextFollowers);
-				contextSuffix.remove(0);
+				contextSuffix.remove(0); 
 				double probSuffix = getProbability(contextSuffix, symbol);
 				result = probEscape*probSuffix;
@@ -98,5 +262,5 @@
 
 		return result;
-	}
+	}*/
 	
 	@Override
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java	(revision 4)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java	(revision 5)
@@ -1,9 +1,26 @@
 package de.ugoe.cs.eventbench.ppm;
 
+import java.awt.Dimension;
+import java.awt.Rectangle;
+import java.awt.Shape;
 import java.util.LinkedList;
 import java.util.List;
 
+import javax.swing.JFrame;
+
+import org.apache.commons.collections15.Transformer;
+
+import edu.uci.ics.jung.algorithms.layout.Layout;
+import edu.uci.ics.jung.algorithms.layout.TreeLayout;
+import edu.uci.ics.jung.graph.DelegateTree;
+import edu.uci.ics.jung.graph.Tree;
+import edu.uci.ics.jung.visualization.BasicVisualizationServer;
+import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
+import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;
+
 public class Trie<T> {
 	
+	// Children of the Trie root
+	// should contain counts of all elements
 	private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>();
 	
@@ -11,5 +28,5 @@
 	public void add(List<T> subsequence) {
 		if( !subsequence.isEmpty() ) {
-			subsequence = new LinkedList<T>(subsequence);  // copy list!
+			subsequence = new LinkedList<T>(subsequence);  // defensive copy!
 			T firstSymbol = subsequence.get(0);
 			getChildCreate(firstSymbol).add(subsequence);
@@ -37,4 +54,5 @@
 	}
 
+	// get the count of "sequence"
 	public int getCount(List<T> sequence) {
 		int count = 0;
@@ -46,4 +64,5 @@
 	}
 	
+	// get the count of "sequence,follower"
 	public int getCount(List<T> sequence, T follower) {
 		List<T> tmpSequence = new LinkedList<T>(sequence);
@@ -54,9 +73,11 @@
 	
 	public TrieNode<T> find(List<T> sequence) {
+		List<T> sequenceCopy = new LinkedList<T>(sequence);
 		TrieNode<T> result = null;
-		if( !sequence.isEmpty() ) {
-			TrieNode<T> node = getChild(sequence.get(0));
+		if( !sequenceCopy.isEmpty() ) {
+			TrieNode<T> node = getChild(sequenceCopy.get(0));
 			if( node!=null ) {
-				result = node.find(sequence);
+				sequenceCopy.remove(0);
+				result = node.find(sequenceCopy);
 			}
 		}
@@ -64,15 +85,23 @@
 	}
 	
+	// returns all symbols that follow the defined sequence
 	public List<T> getFollowingSymbols(List<T> sequence) {
-		List<T> result = null;
-		TrieNode<T> node = find(sequence);
-		if( node!=null ) {
-			result = node.getFollowingSymbols();
+		List<T> result = new LinkedList<T>();
+		if( sequence==null || sequence.isEmpty() ) {
+			for( TrieNode<T> child : children ) {
+				result.add(child.getSymbol());
+			}
+		} else {
+			TrieNode<T> node = find(sequence);
+			if( node!=null ) {
+				result = node.getFollowingSymbols();
+			}
 		}
 		return result;
 	}
 	
+	// longest suffix of context, that is contained in the tree and whose children are leaves
 	public List<T> getContextSuffix(List<T> context) {
-		List<T> contextSuffix = new LinkedList<T>(context);
+		List<T> contextSuffix = new LinkedList<T>(context); // defensive copy
 		boolean suffixFound = false;
 		
@@ -87,9 +116,65 @@
 					}
 				}
-				contextSuffix.remove(0);
+				if( !suffixFound ) {
+					contextSuffix.remove(0);
+				}
 			}
 		}
 		
 		return contextSuffix;
+	}
+	
+	
+	static public class Edge{}
+	
+	static public class TrieVertex {
+		private String id;
+		protected TrieVertex(String id) {
+			this.id = id;
+		}
+		public String toString() {
+			return id;
+		}
+	}
+	
+	private Tree<TrieVertex, Edge> getGraph() {
+		DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
+		
+		TrieVertex root = new TrieVertex("root");
+		graph.addVertex(root);
+				
+		for( TrieNode<T> node : children ) {
+			node.getGraph(root, graph);
+		}
+		
+		return graph;
+	}
+	
+	public void display() {
+		Tree<TrieVertex, Edge> graph = this.getGraph();
+		Layout<TrieVertex, Edge> layout = new TreeLayout<TrieVertex, Edge>(graph, 60);
+		// The BasicVisualizationServer<V,E> is parameterized by the edge types
+		BasicVisualizationServer<TrieVertex,Edge> vv =
+		new BasicVisualizationServer<TrieVertex,Edge>(layout);
+		vv.setPreferredSize(new Dimension(1100,850)); //Sets the viewing area size
+		
+		
+		final Rectangle rect = new Rectangle(40, 20);
+			
+		Transformer<TrieVertex, Shape> vertexShapeTransformer =
+			new Transformer<TrieVertex, Shape>() {
+				public Shape transform(TrieVertex s) {
+					return rect;
+				}
+		};
+		vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);
+		vv.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer);
+		vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<TrieVertex>());
+		
+		JFrame frame = new JFrame("Trie");
+		frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
+		frame.getContentPane().add(vv);
+		frame.pack();
+		frame.setVisible(true);
 	}
 	
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java	(revision 4)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java	(revision 5)
@@ -5,5 +5,8 @@
 import java.util.List;
 
+import de.ugoe.cs.eventbench.ppm.Trie.Edge;
+import de.ugoe.cs.eventbench.ppm.Trie.TrieVertex;
 import de.ugoe.cs.util.StringTools;
+import edu.uci.ics.jung.graph.DelegateTree;
 
 
@@ -80,4 +83,5 @@
 	}
 	
+	// returns all symbols that follow this node
 	public List<T> getFollowingSymbols() {
 		List<T> followingSymbols = new LinkedList<T>();
@@ -97,3 +101,11 @@
 	}
 
+	public void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
+		TrieVertex vertex = new TrieVertex(getSymbol().toString()+"#"+getCount());
+		graph.addChild( new Edge() , parent, vertex );
+		for( TrieNode<T> node : children ) {
+			node.getGraph(vertex, graph);
+		}		
+	}
+
 }