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

package de.ugoe.cs.eventbench.models;

import java.security.InvalidParameterException;
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}^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>
 * 
 * @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>
         */
        protected int minOrder;

        /**
         * <p>
         * Probability to use a lower-order Markov model
         * </p>
         */
        protected 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
         * @throws InvalidParameterException thrown if minOrder is less than 0 or greater than markovOrder or probEscape is not in the interval (0,1)
         */
        public PredictionByPartialMatch(int markovOrder, int minOrder, Random r,
                        double probEscape) {
                super(markovOrder, r);
                if( minOrder< 0 ) {
                        throw new InvalidParameterException("minOrder must be greather than or equal to 0");
                }
                if( minOrder>markovOrder) {
                        throw new InvalidParameterException("minOrder must be less than or equal to markovOrder");
                }
                if( probEscape<=0.0 || probEscape>=1.0) {
                        throw new InvalidParameterException("probEscape must be in the interval (0,1)");
                }
                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>
         * 
         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getProbability(java.util.List,
         *      de.ugoe.cs.eventbench.data.Event)
         */
        @Override
        public double getProbability(List<? extends Event<?>> context,
                        Event<?> symbol) {
                if (context == null) {
                        throw new InvalidParameterException("context must not be null");
                }
                if (symbol == null) {
                        throw new InvalidParameterException("symbol must not be null");
                }
                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;
        }
}