Changeset 100 for trunk/EventBenchCore


Ignore:
Timestamp:
07/04/11 14:09:17 (13 years ago)
Author:
sherbold
Message:
  • code documentation
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r95 r100  
    1414import edu.uci.ics.jung.graph.Tree; 
    1515 
     16/** 
     17 * <p> 
     18 * Implements a skeleton for stochastic processes that can calculate 
     19 * probabilities based on a trie. The skeleton provides all functionalities of 
     20 * {@link IStochasticProcess} except 
     21 * {@link IStochasticProcess#getProbability(List, Event)}. 
     22 * </p> 
     23 *  
     24 * @author Steffen Herbold 
     25 * @version 1.0 
     26 */ 
    1627public abstract class TrieBasedModel implements IStochasticProcess { 
    1728 
    1829        /** 
     30         * <p> 
    1931         * Id for object serialization. 
     32         * </p> 
    2033         */ 
    2134        private static final long serialVersionUID = 1L; 
    2235 
     36        /** 
     37         * <p> 
     38         * The order of the trie, i.e., the maximum length of subsequences stored in 
     39         * the trie. 
     40         * </p> 
     41         */ 
    2342        protected int trieOrder; 
    2443 
     44        /** 
     45         * <p> 
     46         * Trie on which the probability calculations are based. 
     47         * </p> 
     48         */ 
    2549        protected Trie<Event<?>> trie; 
     50 
     51        /** 
     52         * <p> 
     53         * Random number generator used by probabilistic sequence generation 
     54         * methods. 
     55         * </p> 
     56         */ 
    2657        protected final Random r; 
    2758 
    28          
     59        /** 
     60         * <p> 
     61         * Constructor. Creates a new TrieBasedModel that can be used for stochastic 
     62         * processes with a Markov order less than or equal to {@code markovOrder}. 
     63         * </p> 
     64         *  
     65         * @param markovOrder 
     66         *            Markov order of the model 
     67         * @param r 
     68         *            random number generator used by probabilistic methods of the 
     69         *            class 
     70         */ 
    2971        public TrieBasedModel(int markovOrder, Random r) { 
    3072                super(); 
    31                 this.trieOrder = markovOrder+1; 
     73                this.trieOrder = markovOrder + 1; 
    3274                this.r = r; 
    3375        } 
    3476 
     77        /** 
     78         * <p> 
     79         * Trains the model by generating a trie from which probabilities are 
     80         * calculated. 
     81         * </p> 
     82         *  
     83         * @param sequences 
     84         *            training data 
     85         */ 
    3586        public void train(List<List<Event<?>>> sequences) { 
    3687                trie = new Trie<Event<?>>(); 
    37                  
    38                 for(List<Event<?>> sequence : sequences) { 
    39                         List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive copy 
     88 
     89                for (List<Event<?>> sequence : sequences) { 
     90                        List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive 
     91                                                                                                                                                                        // copy 
    4092                        currentSequence.add(0, Event.STARTEVENT); 
    4193                        currentSequence.add(Event.ENDEVENT); 
    42                          
     94 
    4395                        trie.train(currentSequence, trieOrder); 
    4496                } 
    4597        } 
    4698 
    47         /* (non-Javadoc) 
     99        /* 
     100         * (non-Javadoc) 
     101         *  
    48102         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#randomSequence() 
    49103         */ 
    … …  
    51105        public List<? extends Event<?>> randomSequence() { 
    52106                List<Event<?>> sequence = new LinkedList<Event<?>>(); 
    53                  
    54                 IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(trieOrder-1); 
     107 
     108                IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>( 
     109                                trieOrder - 1); 
    55110                context.add(Event.STARTEVENT); 
    56                  
     111 
    57112                Event<?> currentState = Event.STARTEVENT; 
    58                  
     113 
    59114                boolean endFound = false; 
    60                  
    61                 while(!endFound) { 
     115 
     116                while (!endFound) { 
    62117                        double randVal = r.nextDouble(); 
    63118                        double probSum = 0.0; 
    64119                        List<Event<?>> currentContext = context.getLast(trieOrder); 
    65                         for( Event<?> symbol : trie.getKnownSymbols() ) { 
     120                        for (Event<?> symbol : trie.getKnownSymbols()) { 
    66121                                probSum += getProbability(currentContext, symbol); 
    67                                 if( probSum>=randVal ) { 
    68                                         endFound = (symbol==Event.ENDEVENT); 
    69                                         if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) { 
    70                                                 // only add the symbol the sequence if it is not START or END 
     122                                if (probSum >= randVal) { 
     123                                        endFound = (symbol == Event.ENDEVENT); 
     124                                        if (!(symbol == Event.STARTEVENT || symbol == Event.ENDEVENT)) { 
     125                                                // only add the symbol the sequence if it is not START 
     126                                                // or END 
    71127                                                context.add(symbol); 
    72128                                                currentState = symbol; 
    … …  
    79135                return sequence; 
    80136        } 
    81          
     137 
     138        /** 
     139         * <p> 
     140         * Returns a Dot representation of the internal trie. 
     141         * </p> 
     142         *  
     143         * @return dot representation of the internal trie 
     144         */ 
    82145        public String getTrieDotRepresentation() { 
    83146                return trie.getDotRepresentation(); 
    84147        } 
    85          
     148 
     149        /** 
     150         * <p> 
     151         * Returns a {@link Tree} of the internal trie that can be used for 
     152         * visualization. 
     153         * </p> 
     154         *  
     155         * @return {@link Tree} depicting the internal trie 
     156         */ 
    86157        public Tree<TrieVertex, Edge> getTrieGraph() { 
    87158                return trie.getGraph(); 
    88159        } 
    89160 
     161        /** 
     162         * <p> 
     163         * The string representation of the model is {@link Trie#toString()} of 
     164         * {@link #trie}. 
     165         * </p> 
     166         *  
     167         * @see java.lang.Object#toString() 
     168         */ 
    90169        @Override 
    91170        public String toString() { 
    92171                return trie.toString(); 
    93172        } 
    94          
     173 
     174        /* 
     175         * (non-Javadoc) 
     176         *  
     177         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumStates() 
     178         */ 
     179        @Override 
    95180        public int getNumStates() { 
    96181                return trie.getNumSymbols(); 
    97182        } 
    98          
     183 
     184        /* 
     185         * (non-Javadoc) 
     186         *  
     187         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getStateStrings() 
     188         */ 
     189        @Override 
    99190        public String[] getStateStrings() { 
    100191                String[] stateStrings = new String[getNumStates()]; 
    101                 int i=0; 
    102                 for( Event<?> symbol : trie.getKnownSymbols() ) { 
     192                int i = 0; 
     193                for (Event<?> symbol : trie.getKnownSymbols()) { 
    103194                        stateStrings[i] = symbol.toString(); 
    104195                        i++; 
    … …  
    106197                return stateStrings; 
    107198        } 
    108          
     199 
     200        /* 
     201         * (non-Javadoc) 
     202         *  
     203         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getEvents() 
     204         */ 
     205        @Override 
    109206        public Set<? extends Event<?>> getEvents() { 
    110207                return trie.getKnownSymbols(); 
    111208        } 
    112          
     209 
     210        /* 
     211         * (non-Javadoc) 
     212         *  
     213         * @see 
     214         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int) 
     215         */ 
     216        @Override 
    113217        public Set<List<? extends Event<?>>> generateSequences(int length) { 
    114218                return generateSequences(length, false); 
    115                 /*Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();; 
    116                 if( length<1 ) { 
    117                         throw new InvalidParameterException("Length of generated subsequences must be at least 1."); 
    118                 } 
    119                 if( length==1 ) { 
    120                         for( Event<?> event : getEvents() ) { 
     219        } 
     220 
     221        /* 
     222         * (non-Javadoc) 
     223         *  
     224         * @see 
     225         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int, 
     226         * boolean) 
     227         */ 
     228        @Override 
     229        public Set<List<? extends Event<?>>> generateSequences(int length, 
     230                        boolean fromStart) { 
     231                Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>(); 
     232                ; 
     233                if (length < 1) { 
     234                        throw new InvalidParameterException( 
     235                                        "Length of generated subsequences must be at least 1."); 
     236                } 
     237                if (length == 1) { 
     238                        if (fromStart) { 
    121239                                List<Event<?>> subSeq = new LinkedList<Event<?>>(); 
    122                                 subSeq.add(event); 
     240                                subSeq.add(Event.STARTEVENT); 
    123241                                sequenceSet.add(subSeq); 
     242                        } else { 
     243                                for (Event<?> event : getEvents()) { 
     244                                        List<Event<?>> subSeq = new LinkedList<Event<?>>(); 
     245                                        subSeq.add(event); 
     246                                        sequenceSet.add(subSeq); 
     247                                } 
    124248                        } 
    125249                        return sequenceSet; 
    126250                } 
    127251                Set<? extends Event<?>> events = getEvents(); 
    128                 Set<List<? extends Event<?>>> seqsShorter = generateSequences(length-1); 
    129                 for( Event<?> event : events ) { 
    130                         for( List<? extends Event<?>> seqShorter : seqsShorter ) { 
     252                Set<List<? extends Event<?>>> seqsShorter = generateSequences( 
     253                                length - 1, fromStart); 
     254                for (Event<?> event : events) { 
     255                        for (List<? extends Event<?>> seqShorter : seqsShorter) { 
    131256                                Event<?> lastEvent = event; 
    132                                 if( getProbability(seqShorter, lastEvent)>0.0 ) { 
     257                                if (getProbability(seqShorter, lastEvent) > 0.0) { 
    133258                                        List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter); 
    134259                                        subSeq.add(lastEvent); 
    … …  
    138263                } 
    139264                return sequenceSet; 
    140                 */ 
    141         } 
    142          
    143         // if startValid, all sequences will start in Event.STARTEVENT 
    144         public Set<List<? extends Event<?>>> generateSequences(int length, boolean fromStart) { 
    145                 Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();; 
    146                 if( length<1 ) { 
    147                         throw new InvalidParameterException("Length of generated subsequences must be at least 1."); 
    148                 } 
    149                 if( length==1 ) { 
    150                         if( fromStart ) { 
    151                                 List<Event<?>> subSeq = new LinkedList<Event<?>>(); 
    152                                 subSeq.add(Event.STARTEVENT); 
    153                                 sequenceSet.add(subSeq); 
    154                         } else { 
    155                                 for( Event<?> event : getEvents() ) { 
    156                                         List<Event<?>> subSeq = new LinkedList<Event<?>>(); 
    157                                         subSeq.add(event); 
    158                                         sequenceSet.add(subSeq); 
    159                                 } 
    160                         } 
    161                         return sequenceSet; 
    162                 } 
    163                 Set<? extends Event<?>> events = getEvents(); 
    164                 Set<List<? extends Event<?>>> seqsShorter = generateSequences(length-1, fromStart); 
    165                 for( Event<?> event : events ) { 
    166                         for( List<? extends Event<?>> seqShorter : seqsShorter ) { 
    167                                 Event<?> lastEvent = event; 
    168                                 if( getProbability(seqShorter, lastEvent)>0.0 ) { 
    169                                         List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter); 
    170                                         subSeq.add(lastEvent); 
    171                                         sequenceSet.add(subSeq); 
    172                                 } 
    173                         } 
    174                 } 
    175                 return sequenceSet; 
    176         } 
    177          
    178         // sequences from start to end 
     265        } 
     266 
     267        /* 
     268         * (non-Javadoc) 
     269         *  
     270         * @see 
     271         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateValidSequences 
     272         * (int) 
     273         */ 
     274        @Override 
    179275        public Set<List<? extends Event<?>>> generateValidSequences(int length) { 
    180276                // check for min-length implicitly done by generateSequences 
    181                 Set<List<? extends Event<?>>> allSequences = generateSequences(length, true); 
     277                Set<List<? extends Event<?>>> allSequences = generateSequences(length, 
     278                                true); 
    182279                Set<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>(); 
    183                 for( List<? extends Event<?>> sequence : allSequences ) { 
    184                         if( sequence.size()==length && Event.ENDEVENT.equals(sequence.get(sequence.size()-1)) ) { 
     280                for (List<? extends Event<?>> sequence : allSequences) { 
     281                        if (sequence.size() == length 
     282                                        && Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) { 
    185283                                validSequences.add(sequence); 
    186284                        } 
Note: See TracChangeset for help on using the changeset viewer.