Changeset 100

Timestamp:

07/04/11 14:09:17 (13 years ago)

Author:

sherbold

Message:

• code documentation

File:

• trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java (modified) (5 diffs)

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java

@@ -14 +14 @@
 import edu.uci.ics.jung.graph.Tree;
 
+/**
+ * <p>
+ * 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)}.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
 public abstract class TrieBasedModel implements IStochasticProcess {
 
         /**
+         * <p>
          * Id for object serialization.
+         * </p>
          */
         private static final long serialVersionUID = 1L;
 
+        /**
+         * <p>
+         * The order of the trie, i.e., the maximum length of subsequences stored in
+         * the trie.
+         * </p>
+         */
         protected int trieOrder;
 
+        /**
+         * <p>
+         * Trie on which the probability calculations are based.
+         * </p>
+         */
         protected Trie<Event<?>> trie;
+
+        /**
+         * <p>
+         * Random number generator used by probabilistic sequence generation
+         * methods.
+         * </p>
+         */
         protected final Random r;
 
-        
+        /**
+         * <p>
+         * Constructor. Creates a new TrieBasedModel that can be used for stochastic
+         * processes with a Markov order less than or equal to {@code markovOrder}.
+         * </p>
+         * 
+         * @param markovOrder
+         *            Markov order of the model
+         * @param r
+         *            random number generator used by probabilistic methods of the
+         *            class
+         */
         public TrieBasedModel(int markovOrder, Random r) {
                 super();
-                this.trieOrder = markovOrder+1;
+                this.trieOrder = markovOrder + 1;
                 this.r = r;
         }
 
+        /**
+         * <p>
+         * Trains the model by generating a trie from which probabilities are
+         * calculated.
+         * </p>
+         * 
+         * @param sequences
+         *            training data
+         */
         public void train(List<List<Event<?>>> sequences) {
                 trie = new Trie<Event<?>>();
-                
-                for(List<Event<?>> sequence : sequences) {
-                        List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive copy
+
+                for (List<Event<?>> sequence : sequences) {
+                        List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive
+                                                                                                                                                                        // copy
                         currentSequence.add(0, Event.STARTEVENT);
                         currentSequence.add(Event.ENDEVENT);
-                        
+
                         trie.train(currentSequence, trieOrder);
                 }
         }
 
-        /* (non-Javadoc)
+        /*
+         * (non-Javadoc)
+         * 
          * @see de.ugoe.cs.eventbench.models.IStochasticProcess#randomSequence()
          */
@@ -51 +105 @@
         public List<? extends Event<?>> randomSequence() {
                 List<Event<?>> sequence = new LinkedList<Event<?>>();
-                
-                IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(trieOrder-1);
+
+                IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(
+                                trieOrder - 1);
                 context.add(Event.STARTEVENT);
-                
+
                 Event<?> currentState = Event.STARTEVENT;
-                
+
                 boolean endFound = false;
-                
-                while(!endFound) {
+
+                while (!endFound) {
                         double randVal = r.nextDouble();
                         double probSum = 0.0;
                         List<Event<?>> currentContext = context.getLast(trieOrder);
-                        for( Event<?> symbol : trie.getKnownSymbols() ) {
+                        for (Event<?> symbol : trie.getKnownSymbols()) {
                                 probSum += getProbability(currentContext, symbol);
-                                if( probSum>=randVal ) {
-                                        endFound = (symbol==Event.ENDEVENT);
-                                        if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) {
-                                                // only add the symbol the sequence if it is not START or END
+                                if (probSum >= randVal) {
+                                        endFound = (symbol == Event.ENDEVENT);
+                                        if (!(symbol == Event.STARTEVENT || symbol == Event.ENDEVENT)) {
+                                                // only add the symbol the sequence if it is not START
+                                                // or END
                                                 context.add(symbol);
                                                 currentState = symbol;
@@ -79 +135 @@
                 return sequence;
         }
-        
+
+        /**
+         * <p>
+         * Returns a Dot representation of the internal trie.
+         * </p>
+         * 
+         * @return dot representation of the internal trie
+         */
         public String getTrieDotRepresentation() {
                 return trie.getDotRepresentation();
         }
-        
+
+        /**
+         * <p>
+         * Returns a {@link Tree} of the internal trie that can be used for
+         * visualization.
+         * </p>
+         * 
+         * @return {@link Tree} depicting the internal trie
+         */
         public Tree<TrieVertex, Edge> getTrieGraph() {
                 return trie.getGraph();
         }
 
+        /**
+         * <p>
+         * The string representation of the model is {@link Trie#toString()} of
+         * {@link #trie}.
+         * </p>
+         * 
+         * @see java.lang.Object#toString()
+         */
         @Override
         public String toString() {
                 return trie.toString();
         }
-        
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumStates()
+         */
+        @Override
         public int getNumStates() {
                 return trie.getNumSymbols();
         }
-        
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getStateStrings()
+         */
+        @Override
         public String[] getStateStrings() {
                 String[] stateStrings = new String[getNumStates()];
-                int i=0;
-                for( Event<?> symbol : trie.getKnownSymbols() ) {
+                int i = 0;
+                for (Event<?> symbol : trie.getKnownSymbols()) {
                         stateStrings[i] = symbol.toString();
                         i++;
@@ -106 +197 @@
                 return stateStrings;
         }
-        
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getEvents()
+         */
+        @Override
         public Set<? extends Event<?>> getEvents() {
                 return trie.getKnownSymbols();
         }
-        
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see
+         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int)
+         */
+        @Override
         public Set<List<? extends Event<?>>> generateSequences(int length) {
                 return generateSequences(length, false);
-                /*Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();;
-                if( length<1 ) {
-                        throw new InvalidParameterException("Length of generated subsequences must be at least 1.");
-                }
-                if( length==1 ) {
-                        for( Event<?> event : getEvents() ) {
+        }
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see
+         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int,
+         * boolean)
+         */
+        @Override
+        public Set<List<? extends Event<?>>> generateSequences(int length,
+                        boolean fromStart) {
+                Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();
+                ;
+                if (length < 1) {
+                        throw new InvalidParameterException(
+                                        "Length of generated subsequences must be at least 1.");
+                }
+                if (length == 1) {
+                        if (fromStart) {
                                 List<Event<?>> subSeq = new LinkedList<Event<?>>();
-                                subSeq.add(event);
+                                subSeq.add(Event.STARTEVENT);
                                 sequenceSet.add(subSeq);
+                        } else {
+                                for (Event<?> event : getEvents()) {
+                                        List<Event<?>> subSeq = new LinkedList<Event<?>>();
+                                        subSeq.add(event);
+                                        sequenceSet.add(subSeq);
+                                }
                         }
                         return sequenceSet;
                 }
                 Set<? extends Event<?>> events = getEvents();
-                Set<List<? extends Event<?>>> seqsShorter = generateSequences(length-1);
-                for( Event<?> event : events ) {
-                        for( List<? extends Event<?>> seqShorter : seqsShorter ) {
+                Set<List<? extends Event<?>>> seqsShorter = generateSequences(
+                                length - 1, fromStart);
+                for (Event<?> event : events) {
+                        for (List<? extends Event<?>> seqShorter : seqsShorter) {
                                 Event<?> lastEvent = event;
-                                if( getProbability(seqShorter, lastEvent)>0.0 ) {
+                                if (getProbability(seqShorter, lastEvent) > 0.0) {
                                         List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
                                         subSeq.add(lastEvent);
@@ -138 +263 @@
                 }
                 return sequenceSet;
-                */
-        }
-        
-        // if startValid, all sequences will start in Event.STARTEVENT
-        public Set<List<? extends Event<?>>> generateSequences(int length, boolean fromStart) {
-                Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();;
-                if( length<1 ) {
-                        throw new InvalidParameterException("Length of generated subsequences must be at least 1.");
-                }
-                if( length==1 ) {
-                        if( fromStart ) {
-                                List<Event<?>> subSeq = new LinkedList<Event<?>>();
-                                subSeq.add(Event.STARTEVENT);
-                                sequenceSet.add(subSeq);
-                        } else {
-                                for( Event<?> event : getEvents() ) {
-                                        List<Event<?>> subSeq = new LinkedList<Event<?>>();
-                                        subSeq.add(event);
-                                        sequenceSet.add(subSeq);
-                                }
-                        }
-                        return sequenceSet;
-                }
-                Set<? extends Event<?>> events = getEvents();
-                Set<List<? extends Event<?>>> seqsShorter = generateSequences(length-1, fromStart);
-                for( Event<?> event : events ) {
-                        for( List<? extends Event<?>> seqShorter : seqsShorter ) {
-                                Event<?> lastEvent = event;
-                                if( getProbability(seqShorter, lastEvent)>0.0 ) {
-                                        List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
-                                        subSeq.add(lastEvent);
-                                        sequenceSet.add(subSeq);
-                                }
-                        }
-                }
-                return sequenceSet;
-        }
-        
-        // sequences from start to end
+        }
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see
+         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateValidSequences
+         * (int)
+         */
+        @Override
         public Set<List<? extends Event<?>>> generateValidSequences(int length) {
                 // check for min-length implicitly done by generateSequences
-                Set<List<? extends Event<?>>> allSequences = generateSequences(length, true);
+                Set<List<? extends Event<?>>> allSequences = generateSequences(length,
+                                true);
                 Set<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>();
-                for( List<? extends Event<?>> sequence : allSequences ) {
-                        if( sequence.size()==length && Event.ENDEVENT.equals(sequence.get(sequence.size()-1)) ) {
+                for (List<? extends Event<?>> sequence : allSequences) {
+                        if (sequence.size() == length
+                                        && Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) {
                                 validSequences.add(sequence);
                         }