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

//   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 an inverted high-order Markov models. The idea behind this is that the most likely events, become the most unlikely events and the most unlikely events become the most likely events.
 * </p>
 * <p>
 * The empirical probability of an observation is N-n/(k-1)N with N the total number of observations, n the number a specific observation was seen and k the number of different observations. 
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class InvertedHighOrderMarkovModel extends TrieBasedModel {

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

    /**
     * <p>
     * Constructor. Creates a new HighOrderMarkovModel with a defined Markov order.
     * </p>
     * 
     * @param maxOrder
     *            Markov order of the model
     * @param r
     *            random number generator used by probabilistic methods of the class
     */
    public InvertedHighOrderMarkovModel(int maxOrder, Random r) {
        super(maxOrder, r);
    }

    /**
     * <p>
     * Calculates the probability of the next Event being symbol based on the order of the Markov
     * model. The order is defined in the constructor {@link #HighOrderMarkovModel(int, Random)}.
     * </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;

        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);
        int sumCountFollowers = 0; // N(s\sigma')
        for (Event follower : followers) {
            sumCountFollowers += trie.getCount(contextCopy, follower);
        }

        int countSymbol = trie.getCount(contextCopy, symbol);
        if (sumCountFollowers != 0) {
            result = ((double) (sumCountFollowers-countSymbol)) / ((followers.size()-1)*sumCountFollowers);
        }

        return result;
    }

}