source: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/PredictionByPartialMatch.java @ 927

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.usageprofiles;

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

import de.ugoe.cs.autoquest.eventcore.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 IllegalArgumentException
     *             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 IllegalArgumentException("minOrder must be greather than or equal to 0");
        }
        if (minOrder > markovOrder) {
            throw new IllegalArgumentException(
                                                "minOrder must be less than or equal to markovOrder");
        }
        if (probEscape <= 0.0 || probEscape >= 1.0) {
            throw new IllegalArgumentException("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.autoquest.usageprofiles.IStochasticProcess#getProbability(java.util.List,
     *      de.ugoe.cs.autoquest.eventcore.Event)
     */
    @Override
    public double getProbability(List<Event> context, Event symbol) {
        if (context == null) {
            throw new IllegalArgumentException("context must not be null");
        }
        if (symbol == null) {
            throw new IllegalArgumentException("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;
    }
}