source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java @ 109

package de.ugoe.cs.eventbench.models;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import de.ugoe.cs.eventbench.data.Event;

/**
 * <p>
 * Implements Prediction by Partial Match (PPM) based on the following formula
 * (LaTeX-style notation):<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_{MM^i} denotes the probability in an i-th order Markov model.
 * </p>
 * 
 * @author Steffen Herbold
 * 
 */
public class PredictionByPartialMatch extends TrieBasedModel {

        /**
         * <p>
         * Id for object serialization.
         * </p>
         */
        private static final long serialVersionUID = 1L;

        /**
         * <p>
         * Minimum order of the Markov model.
         * </p>
         */
        private int minOrder;

        /**
         * <p>
         * Probability to use a lower-order Markov model
         * </p>
         */
        double probEscape;

        /**
         * <p>
         * Constructor. Creates a new PredictionByPartialMatch model with a given
         * Markov order and a default escape probability of 0.1.
         * </p>
         * 
         * @param markovOrder
         *            Markov order of the model
         * @param r
         *            random number generator used by probabilistic methods of the
         *            class
         */
        public PredictionByPartialMatch(int markovOrder, Random r) {
                this(markovOrder, r, 0.1);
        }

        /**
         * <p>
         * Creates a new PredictionByPartialMatch model with a given Markov order
         * and escape probability.
         * </p>
         * 
         * @param markovOrder
         *            Markov order of the model
         * @param r
         *            random number generator used by probabilistic methods of the
         *            class
         * @param probEscape
         *            escape probability used by the model
         */
        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;
        }

        /**
         * <p>
         * Sets the escape probability of the model.
         * </p>
         * 
         * @param probEscape
         *            new escape probability
         */
        public void setProbEscape(double probEscape) {
                this.probEscape = probEscape;
        }

        /**
         * <p>
         * Returns the escape probability of the model.
         * </p>
         * 
         * @return escape probability of the model
         */
        public double getProbEscape() {
                return probEscape;
        }

        /**
         * <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}^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>
         */
        @Override
        public double getProbability(List<? extends Event<?>> context,
                        Event<?> symbol) {
                double result = 0.0d;
                double resultCurrentContex = 0.0d;
                double resultShorterContex = 0.0d;

                List<Event<?>> contextCopy;
                if (context.size() >= trieOrder) {
                        contextCopy = new LinkedList<Event<?>>(context.subList(
                                        context.size() - trieOrder + 1, context.size()));
                } else {
                        contextCopy = new LinkedList<Event<?>>(context);
                }

                Collection<Event<?>> followers = trie.getFollowingSymbols(contextCopy); // \Sigma'
                int sumCountFollowers = 0; // N(s\sigma')
                for (Event<?> follower : followers) {
                        sumCountFollowers += trie.getCount(contextCopy, follower);
                }

                int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
                if (sumCountFollowers == 0) {
                        resultCurrentContex = 0.0;
                } else {
                        resultCurrentContex = (double) countSymbol / sumCountFollowers;
                }
                if (contextCopy.size() != minOrder) {
                        resultCurrentContex *= (1 - probEscape);
                        contextCopy.remove(0);
                        if (contextCopy.size() >= minOrder) {
                                double probSuffix = getProbability(contextCopy, symbol);

                                if (followers.size() == 0) {
                                        resultShorterContex = probSuffix;
                                } else {
                                        resultShorterContex = probEscape * probSuffix;
                                }
                        }
                }
                result = resultCurrentContex + resultShorterContex;

                return result;
        }
}