source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/HighOrderMarkovModel.java @ 101

package de.ugoe.cs.eventbench.models;

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

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

/**
 * <p>Implements high-order Markov models.</p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class HighOrderMarkovModel 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 HighOrderMarkovModel(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.eventbench.models.IStochasticProcess#getProbability(java.util.List, de.ugoe.cs.eventbench.data.Event)
         */
        @Override
        public double getProbability(List<? extends Event<?>> context, Event<?> symbol) {
                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);
                }

        
                List<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) countSymbol / sumCountFollowers);
                }
                
                return result;
        }

}