Changeset 9 for trunk

Timestamp:

04/13/11 14:13:45 (14 years ago)

Author:

sherbold

Message:

• moved training logic for single sequences from PPM to Trie

Location:

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm

Files:

• PredictionByPartialMatch.java (modified) (6 diffs)
• Trie.java (modified) (2 diffs)

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java

@@ -1 +1 @@
 package de.ugoe.cs.eventbench.ppm;
 
-import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Random;
-import java.util.Set;
 
 import de.ugoe.cs.eventbench.data.Event;
@@ -12 +10 @@
 public class PredictionByPartialMatch {
         
-        private int maxOrder = 3;
+        private int maxOrder;
         
         private Trie<Event<?>> trie;
         
-        private Set<Event<?>> knownSymbols;
-        
         private double probEscape;
         
         private final Random r;
         
-        public PredictionByPartialMatch(Random r) {
-                this(r, 0.1);
-        }
-        
-        public PredictionByPartialMatch(Random r, double probEscape) {
+        public PredictionByPartialMatch(int maxOrder, Random r) {
+                this(maxOrder, r, 0.1);
+        }
+        
+        public PredictionByPartialMatch(int maxOrder, Random r, double probEscape) {
+                this.maxOrder = maxOrder;
                 this.r = r; // TODO defensive copy instead?
                 this.probEscape = probEscape;
@@ -42 +39 @@
         public void train(List<List<Event<?>>> sequences) {
                 trie = new Trie<Event<?>>();
-                knownSymbols = new LinkedHashSet<Event<?>>();
-                knownSymbols.add(Event.STARTEVENT);
-                knownSymbols.add(Event.ENDEVENT);
                 
                 for(List<Event<?>> sequence : sequences) {
@@ -51 +45 @@
                         currentSequence.add(Event.ENDEVENT);
                         
-                        addToTrie(currentSequence);
-                }
-        }
-        
-        private void addToTrie(List<Event<?>> sequence) {
+                        trie.train(currentSequence, maxOrder);
+                }
+        }
+        
+        /*private void addToTrie(List<Event<?>> sequence) {
                 if( knownSymbols==null ) {
                         knownSymbols = new LinkedHashSet<Event<?>>();
@@ -73 +67 @@
                         trie.add(sequence.subList(sequenceLength-j, sequenceLength));
                 }
-        }
+        }*/
         
         public List<? extends Event<?>> randomSequence() {
@@ -89 +83 @@
                         double probSum = 0.0;
                         List<Event<?>> currentContext = context.getLast(maxOrder);
-                        for( Event<?> symbol : knownSymbols ) {
+                        for( Event<?> symbol : trie.getKnownSymbols() ) {
                                 probSum += getProbability(currentContext, symbol);
                                 if( probSum>=randVal ) {

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java

@@ -4 +4 @@
 import java.awt.Rectangle;
 import java.awt.Shape;
+import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Set;
 
 import javax.swing.JFrame;
 
 import org.apache.commons.collections15.Transformer;
+
+import de.ugoe.cs.eventbench.markov.IncompleteMemory;
 
 import edu.uci.ics.jung.algorithms.layout.Layout;
@@ -21 +25 @@
 public class Trie<T> {
         
+        private Set<T> knownSymbols;
+        
         private final TrieNode<T> rootNode;
         
         public Trie() {
                 rootNode = new TrieNode<T>();
+                knownSymbols = new LinkedHashSet<T>();
+        }
+        
+        public Set<T> getKnownSymbols() {
+                return new LinkedHashSet<T>(knownSymbols);
+        }
+        
+        // trains the current Trie using the given sequence and adds all subsequence of length maxOrder
+        public void train(List<T> sequence, int maxOrder) {
+                IncompleteMemory<T> latestActions = new IncompleteMemory<T>(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));
+                }
         }
         
 
+        // increases the counters for each symbol in the subsequence
         public void add(List<T> subsequence) {
-                if( !subsequence.isEmpty() ) {
+                if( subsequence!=null && !subsequence.isEmpty() ) {
+                        knownSymbols.addAll(subsequence);
                         subsequence = new LinkedList<T>(subsequence);  // defensive copy!
                         T firstSymbol = subsequence.get(0);