// 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.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.List; import java.util.Random; import java.util.Set; import de.ugoe.cs.autoquest.eventcore.Event; import de.ugoe.cs.autoquest.usageprofiles.Trie.Edge; import de.ugoe.cs.autoquest.usageprofiles.Trie.TrieVertex; import edu.uci.ics.jung.graph.Tree; /** *
* Implements a skeleton for stochastic processes that can calculate probabilities based on a trie. * The skeleton provides all functionalities of {@link IStochasticProcess} except * {@link IStochasticProcess#getProbability(List, Event)}. *
* * @author Steffen Herbold * @version 1.0 */ public abstract class TrieBasedModel implements IStochasticProcess { /** ** Id for object serialization. *
*/ private static final long serialVersionUID = 1L; /** ** The order of the trie, i.e., the maximum length of subsequences stored in the trie. *
*/ protected int trieOrder; /** ** Trie on which the probability calculations are based. *
*/ protected Trie* Random number generator used by probabilistic sequence generation methods. *
*/ protected final Random r; /** ** Constructor. Creates a new TrieBasedModel that can be used for stochastic processes with a * Markov order less than or equal to {@code markovOrder}. *
* * @param markovOrder * Markov order of the model * @param r * random number generator used by probabilistic methods of the class * @throws IllegalArgumentException * thrown if markovOrder is less than 0 or the random number generator r is null */ public TrieBasedModel(int markovOrder, Random r) { super(); if (markovOrder < 0) { throw new IllegalArgumentException("markov order must not be less than 0"); } if (r == null) { throw new IllegalArgumentException("random number generator r must not be null"); } this.trieOrder = markovOrder + 1; this.r = r; } /** ** Trains the model by generating a trie from which probabilities are calculated. The trie is * newly generated based solely on the passed sequences. If an existing model should only be * updated, use {@link #update(Collection)} instead. *
* * @param sequences * training data * @throws IllegalArgumentException * thrown is sequences is null */ public void train(Collection* Trains the model by updating the trie from which the probabilities are calculated. This * function updates an existing trie. In case no trie exists yet, a new trie is generated and * the function behaves like {@link #train(Collection)}. *
* * @param sequences * training data * @throws IllegalArgumentException * thrown is sequences is null */ public void update(Collection* Returns a Dot representation of the internal trie. *
* * @return dot representation of the internal trie */ public String getTrieDotRepresentation() { if (trie == null) { return ""; } else { return trie.getDotRepresentation(); } } /** ** Returns a {@link Tree} of the internal trie that can be used for visualization. *
* * @return {@link Tree} depicting the internal trie */ public Tree* The string representation of the model is {@link Trie#toString()} of {@link #trie}. *
* * @see java.lang.Object#toString() */ @Override public String toString() { if (trie == null) { return ""; } else { return trie.toString(); } } /* * (non-Javadoc) * * @see de.ugoe.cs.autoquest.usageprofiles.IStochasticProcess#getNumStates() */ @Override public int getNumSymbols() { if (trie == null) { return 0; } else { return trie.getNumSymbols(); } } /* * (non-Javadoc) * * @see de.ugoe.cs.autoquest.usageprofiles.IStochasticProcess#getStateStrings() */ @Override public String[] getSymbolStrings() { if (trie == null) { return new String[0]; } String[] stateStrings = new String[getNumSymbols()]; int i = 0; for (Event symbol : trie.getKnownSymbols()) { if (symbol.toString() == null) { stateStrings[i] = "null"; } else { stateStrings[i] = symbol.toString(); } i++; } return stateStrings; } /* * (non-Javadoc) * * @see de.ugoe.cs.autoquest.usageprofiles.IStochasticProcess#getEvents() */ @Override public Collection