Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java	(revision 11)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java	(revision 12)
@@ -1,3 +1,5 @@
 package de.ugoe.cs.eventbench.data;
+
+import java.security.InvalidParameterException;
 
 
@@ -32,4 +34,7 @@
 	
 	public Event(String type) {
+		if( type==null ) {
+			throw new InvalidParameterException("Event type must not be null");
+		}
 		this.type = type;
 	}
@@ -41,7 +46,12 @@
 		}
 		if (other instanceof Event<?>) {
-			Event<?> otherToken = (Event<?>) other;
-			return otherToken.type.equals(this.type)
-					&& otherToken.target.equals(this.target);
+			Event<?> otherEvent = (Event<?>) other;
+			if( target!=null ) {
+				return type.equals(otherEvent.type)
+					&& target.equals(otherEvent.target);
+			} else {
+				return type.equals(otherEvent.type)
+					&& target==otherEvent.target;
+			}
 		} else {
 			return false;
@@ -70,5 +80,9 @@
 
 	public String getStandardId() {
-		String id = target + "." + getType();
+		String id = "";
+		if( target!=null ) {
+			id += target + ".";
+		}
+		id += getType();
 		if ( idInfo!="" ) {
 			id += "." + idInfo;
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/HighOrderMarkovModel.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/HighOrderMarkovModel.java	(revision 12)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/HighOrderMarkovModel.java	(revision 12)
@@ -0,0 +1,37 @@
+package de.ugoe.cs.eventbench.markov;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.eventbench.data.Event;
+import de.ugoe.cs.eventbench.ppm.TrieBasedModel;
+
+public class HighOrderMarkovModel extends TrieBasedModel {
+	
+	public HighOrderMarkovModel(int maxOrder, Random r) {
+		super(maxOrder, r);
+	}
+		
+	@Override
+	protected double getProbability(List<Event<?>> context, Event<?> symbol) {
+		double result = 0.0d;
+		
+		List<Event<?>> contextCopy = new LinkedList<Event<?>>(context);
+
+	
+		List<Event<?>> 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/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java	(revision 11)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java	(revision 12)
@@ -1,4 +1,5 @@
 package de.ugoe.cs.eventbench.ppm;
 
+import java.util.ArrayList;
 import java.util.LinkedList;
 import java.util.List;
@@ -6,15 +7,9 @@
 
 import de.ugoe.cs.eventbench.data.Event;
-import de.ugoe.cs.eventbench.markov.IncompleteMemory;
+import de.ugoe.cs.util.console.Console;
 
-public class PredictionByPartialMatch {
+public class PredictionByPartialMatch extends TrieBasedModel {
 	
-	private int maxOrder;
-	
-	private Trie<Event<?>> trie;
-	
-	private double probEscape;
-	
-	private final Random r;
+	double probEscape;
 	
 	public PredictionByPartialMatch(int maxOrder, Random r) {
@@ -23,6 +18,5 @@
 	
 	public PredictionByPartialMatch(int maxOrder, Random r, double probEscape) {
-		this.maxOrder = maxOrder;
-		this.r = r; // TODO defensive copy instead?
+		super(maxOrder, r);
 		this.probEscape = probEscape;
 	}
@@ -36,69 +30,6 @@
 	}
 	
-	// the training is basically the generation of the trie
-	public void train(List<List<Event<?>>> sequences) {
-		trie = new Trie<Event<?>>();
-		
-		for(List<Event<?>> sequence : sequences) {
-			List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive copy
-			currentSequence.add(0, Event.STARTEVENT);
-			currentSequence.add(Event.ENDEVENT);
-			
-			trie.train(currentSequence, maxOrder);
-		}
-	}
-	
-	/*private void addToTrie(List<Event<?>> sequence) {
-		if( knownSymbols==null ) {
-			knownSymbols = new LinkedHashSet<Event<?>>();
-		}
-		IncompleteMemory<Event<?>> latestActions = new IncompleteMemory<Event<?>>(maxOrder);
-		int i=0;
-		for(Event<?> currentEvent : sequence) {
-			latestActions.add(currentEvent);
-			knownSymbols.add(currentEvent);
-			i++;
-			if( i>=maxOrder ) {
-				trie.add(latestActions.getLast(maxOrder));
-			}
-		}
-		int sequenceLength = sequence.size();
-		for( int j=maxOrder-1 ; j>0 ; j-- ) {
-			trie.add(sequence.subList(sequenceLength-j, sequenceLength));
-		}
-	}*/
-	
-	public List<? extends Event<?>> randomSequence() {
-		List<Event<?>> sequence = new LinkedList<Event<?>>();
-		
-		IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(maxOrder-1);
-		context.add(Event.STARTEVENT);
-		
-		Event<?> currentState = Event.STARTEVENT;
-		
-		boolean endFound = false;
-		
-		while(!endFound) {
-			double randVal = r.nextDouble();
-			double probSum = 0.0;
-			List<Event<?>> currentContext = context.getLast(maxOrder);
-			for( Event<?> symbol : trie.getKnownSymbols() ) {
-				probSum += getProbability(currentContext, symbol);
-				if( probSum>=randVal ) {
-					endFound = (symbol==Event.ENDEVENT);
-					if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) {
-						// only add the symbol the sequence if it is not START or END
-						context.add(symbol);
-						currentState = symbol;
-						sequence.add(currentState);
-					}
-					break;
-				}
-			}
-		}
-		return sequence;
-	}
-		
-	private double getProbability(List<Event<?>> context, Event<?> symbol) {
+	@Override
+	protected double getProbability(List<Event<?>> context, Event<?> symbol) {
 		double result = 0.0d;
 		double resultCurrentContex = 0.0d;
@@ -132,77 +63,70 @@
 	}
 	
-	@Override
-	public String toString() {
-		return trie.toString();
-	}
-	
-	/*
 	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);
+		List<Event<?>> list = new ArrayList<Event<?>>();
+		list.add(new Event<Object>("a"));
+		list.add(new Event<Object>("b"));
+		list.add(new Event<Object>("r"));
+		list.add(new Event<Object>("a"));
+		list.add(new Event<Object>("c"));
+		list.add(new Event<Object>("a"));
+		list.add(new Event<Object>("d"));
+		list.add(new Event<Object>("a"));
+		list.add(new Event<Object>("b"));
+		list.add(new Event<Object>("r"));
+		list.add(new Event<Object>("a"));
 		
-		PredictionByPartialMatch model = new PredictionByPartialMatch();
-		model.trie = new Trie<String>();
-		model.trainStringTrie(list);
+		int maxOrder = 3;
+		PredictionByPartialMatch model = new PredictionByPartialMatch(maxOrder, new Random());
+		model.trie = new Trie<Event<?>>();
+		model.trie.train(list, maxOrder);
 		model.trie.display();
 		
-		List<String> context = new ArrayList<String>();
-		String symbol = "a";
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		Event<Object> symbol = new Event<Object>("a");
 		// expected: 5
 		Console.traceln(""+model.trie.getCount(context, symbol));
 		
 		// expected: 0
-		context.add("b");
+		context.add(new Event<Object>("b"));
 		Console.traceln(""+model.trie.getCount(context, symbol));
 		
 		// expected: 2
-		context.add("r");
+		context.add(new Event<Object>("r"));
 		Console.traceln(""+model.trie.getCount(context, symbol));
 		
 		// exptected: [b, r]
-		context = new ArrayList<String>();
-		context.add("a");
-		context.add("b");
-		context.add("r");
+		context = new ArrayList<Event<?>>();
+		context.add(new Event<Object>("a"));
+		context.add(new Event<Object>("b"));
+		context.add(new Event<Object>("r"));
 		Console.traceln(model.trie.getContextSuffix(context).toString());
 		
 		// exptected: []
-		context = new ArrayList<String>();
-		context.add("e");
+		context = new ArrayList<Event<?>>();
+		context.add(new Event<Object>("e"));
 		Console.traceln(model.trie.getContextSuffix(context).toString());
 		
 		// exptected: {a, b, c, d, r}
-		context = new ArrayList<String>();
+		context = new ArrayList<Event<?>>();
 		Console.traceln(model.trie.getFollowingSymbols(context).toString());
 		
 		// exptected: {b, c, d}
-		context = new ArrayList<String>();
-		context.add("a");
+		context = new ArrayList<Event<?>>();
+		context.add(new Event<Object>("a"));
 		Console.traceln(model.trie.getFollowingSymbols(context).toString());
 		
 		// exptected: []
-		context = new ArrayList<String>();
-		context.add("a");
-		context.add("b");
-		context.add("r");
+		context = new ArrayList<Event<?>>();
+		context.add(new Event<Object>("a"));
+		context.add(new Event<Object>("b"));
+		context.add(new Event<Object>("r"));
 		Console.traceln(model.trie.getFollowingSymbols(context).toString());
 		
 		// exptected: 0.0d
-		context = new ArrayList<String>();
-		context.add("a");
-		Console.traceln(""+model.getProbability(context, "z"));
-	}*/
+		context = new ArrayList<Event<?>>();
+		context.add(new Event<Object>("a"));
+		Console.traceln(""+model.getProbability(context, new Event<Object>("z")));
+	}
 }
Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieBasedModel.java
===================================================================
--- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieBasedModel.java	(revision 12)
+++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieBasedModel.java	(revision 12)
@@ -0,0 +1,74 @@
+package de.ugoe.cs.eventbench.ppm;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.eventbench.data.Event;
+import de.ugoe.cs.eventbench.markov.IncompleteMemory;
+
+public abstract class TrieBasedModel {
+
+	protected int maxOrder;
+
+	protected abstract double getProbability(List<Event<?>> context, Event<?> symbol);
+
+	protected Trie<Event<?>> trie;
+	protected final Random r;
+
+	
+	public TrieBasedModel(int maxOrder, Random r) {
+		super();
+		this.maxOrder = maxOrder;
+		this.r = r;
+	}
+
+	public void train(List<List<Event<?>>> sequences) {
+		trie = new Trie<Event<?>>();
+		
+		for(List<Event<?>> sequence : sequences) {
+			List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive copy
+			currentSequence.add(0, Event.STARTEVENT);
+			currentSequence.add(Event.ENDEVENT);
+			
+			trie.train(currentSequence, maxOrder);
+		}
+	}
+
+	public List<? extends Event<?>> randomSequence() {
+		List<Event<?>> sequence = new LinkedList<Event<?>>();
+		
+		IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(maxOrder-1);
+		context.add(Event.STARTEVENT);
+		
+		Event<?> currentState = Event.STARTEVENT;
+		
+		boolean endFound = false;
+		
+		while(!endFound) {
+			double randVal = r.nextDouble();
+			double probSum = 0.0;
+			List<Event<?>> currentContext = context.getLast(maxOrder);
+			for( Event<?> symbol : trie.getKnownSymbols() ) {
+				probSum += getProbability(currentContext, symbol);
+				if( probSum>=randVal ) {
+					endFound = (symbol==Event.ENDEVENT);
+					if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) {
+						// only add the symbol the sequence if it is not START or END
+						context.add(symbol);
+						currentState = symbol;
+						sequence.add(currentState);
+					}
+					break;
+				}
+			}
+		}
+		return sequence;
+	}
+
+	@Override
+	public String toString() {
+		return trie.toString();
+	}
+
+}