Changeset 109

Timestamp:

07/07/11 09:32:31 (13 years ago)

Author:

sherbold

Message:

• extended PPM to enforce a minimum markov order

File:

• trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java (modified) (4 diffs)

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

@@ -28 +28 @@
          */
         private static final long serialVersionUID = 1L;
+
+        /**
+         * <p>
+         * Minimum order of the Markov model.
+         * </p>
+         */
+        private int minOrder;
 
         /**
@@ -67 +74 @@
          */
         public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) {
+                this(markovOrder, 0, r, probEscape);
+        }
+
+        /**
+         * <p>
+         * Creates a new PredictionByPartialMatch model with a given Markov order
+         * and escape probability.
+         * </p>
+         * 
+         * @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
+         */
+        public PredictionByPartialMatch(int markovOrder, int minOrder, Random r,
+                        double probEscape) {
                 super(markovOrder, r);
                 this.probEscape = probEscape;
+                this.minOrder = minOrder;
         }
 
@@ -97 +127 @@
          * <p>
          * Calculates the probability of the next event based on the formula:<br>
-         * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^1 escape^{i-1}
-         * P_{MM^i}(X_n|X_{n-1},...,X_{n-i})(1-escape)<br>
+         * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i}
+         * P_{MM^i}(X_n
+         * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},...
+         * ,X_{n-min})<br>
          * P_{MM^i} denotes the probability in an i-th order Markov model.
          * </p>
@@ -124 +156 @@
 
                 int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
-                if (contextCopy.size() == 0) {
-                        resultCurrentContex = ((double) countSymbol) / sumCountFollowers;
+                if (sumCountFollowers == 0) {
+                        resultCurrentContex = 0.0;
                 } else {
-                        if (sumCountFollowers == 0) {
-                                resultCurrentContex = 0.0;
-                        } else {
-                                resultCurrentContex = ((double) countSymbol / sumCountFollowers)
-                                                * (1 - probEscape);
-                        }
+                        resultCurrentContex = (double) countSymbol / sumCountFollowers;
+                }
+                if (contextCopy.size() != minOrder) {
+                        resultCurrentContex *= (1 - probEscape);
                         contextCopy.remove(0);
-                        double probSuffix = getProbability(contextCopy, symbol);
-                        if (followers.size() == 0) {
-                                resultShorterContex = probSuffix;
-                        } else {
-                                resultShorterContex = probEscape * probSuffix;
+                        if (contextCopy.size() >= minOrder) {
+                                double probSuffix = getProbability(contextCopy, symbol);
+
+                                if (followers.size() == 0) {
+                                        resultShorterContex = probSuffix;
+                                } else {
+                                        resultShorterContex = probEscape * probSuffix;
+                                }
                         }
                 }