source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java @ 342

Last change on this file since 342 was 342, checked in by sherbold, 13 years ago
  • Property svn:mime-type set to text/plain
File size: 10.0 KB
Line 
1package de.ugoe.cs.eventbench.models;
2
3import java.security.InvalidParameterException;
4import java.util.ArrayList;
5import java.util.Collection;
6import java.util.HashSet;
7import java.util.LinkedHashSet;
8import java.util.LinkedList;
9import java.util.List;
10import java.util.Random;
11import java.util.Set;
12
13import de.ugoe.cs.eventbench.data.Event;
14import de.ugoe.cs.eventbench.models.Trie.Edge;
15import de.ugoe.cs.eventbench.models.Trie.TrieVertex;
16import edu.uci.ics.jung.graph.Tree;
17
18/**
19 * <p>
20 * Implements a skeleton for stochastic processes that can calculate
21 * probabilities based on a trie. The skeleton provides all functionalities of
22 * {@link IStochasticProcess} except
23 * {@link IStochasticProcess#getProbability(List, Event)}.
24 * </p>
25 *
26 * @author Steffen Herbold
27 * @version 1.0
28 */
29public abstract class TrieBasedModel implements IStochasticProcess {
30
31        /**
32         * <p>
33         * Id for object serialization.
34         * </p>
35         */
36        private static final long serialVersionUID = 1L;
37
38        /**
39         * <p>
40         * The order of the trie, i.e., the maximum length of subsequences stored in
41         * the trie.
42         * </p>
43         */
44        protected int trieOrder;
45
46        /**
47         * <p>
48         * Trie on which the probability calculations are based.
49         * </p>
50         */
51        protected Trie<Event<?>> trie = null;
52
53        /**
54         * <p>
55         * Random number generator used by probabilistic sequence generation
56         * methods.
57         * </p>
58         */
59        protected final Random r;
60
61        /**
62         * <p>
63         * Constructor. Creates a new TrieBasedModel that can be used for stochastic
64         * processes with a Markov order less than or equal to {@code markovOrder}.
65         * </p>
66         *
67         * @param markovOrder
68         *            Markov order of the model
69         * @param r
70         *            random number generator used by probabilistic methods of the
71         *            class
72         * @throws InvalidParameterException
73         *             thrown if markovOrder is less than 0 or the random number
74         *             generator r is null
75         */
76        public TrieBasedModel(int markovOrder, Random r) {
77                super();
78                if (markovOrder < 0) {
79                        throw new InvalidParameterException(
80                                        "markov order must not be less than 0");
81                }
82                if (r == null) {
83                        throw new InvalidParameterException(
84                                        "random number generator r must not be null");
85                }
86                this.trieOrder = markovOrder + 1;
87                this.r = r;
88        }
89
90        /**
91         * <p>
92         * Trains the model by generating a trie from which probabilities are
93         * calculated. The trie is newly generated based solely on the passed
94         * sequences. If an existing model should only be updated, use
95         * {@link #update(Collection)} instead.
96         * </p>
97         *
98         * @param sequences
99         *            training data
100         * @throws InvalidParameterException
101         *             thrown is sequences is null
102         */
103        public void train(Collection<List<? extends Event<?>>> sequences) {
104                trie = null;
105                update(sequences);
106        }
107
108        /**
109         * <p>
110         * Trains the model by updating the trie from which the probabilities are
111         * calculated. This function updates an existing trie. In case no trie
112         * exists yet, a new trie is generated and the function behaves like
113         * {@link #train(Collection)}.
114         * </p>
115         *
116         * @param sequences
117         *            training data
118         * @throws InvalidParameterException
119         *             thrown is sequences is null
120         */
121        public void update(Collection<List<? extends Event<?>>> sequences) {
122                if (sequences == null) {
123                        throw new InvalidParameterException("sequences must not be null");
124                }
125                if (trie == null) {
126                        trie = new Trie<Event<?>>();
127                }
128                for (List<? extends Event<?>> sequence : sequences) {
129                        List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive
130                                                                                                                                                                        // copy
131                        currentSequence.add(0, Event.STARTEVENT);
132                        currentSequence.add(Event.ENDEVENT);
133
134                        trie.train(currentSequence, trieOrder);
135                }
136        }
137
138        /*
139         * (non-Javadoc)
140         *
141         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#randomSequence()
142         */
143        @Override
144        public List<? extends Event<?>> randomSequence() {
145                List<Event<?>> sequence = new LinkedList<Event<?>>();
146                if (trie != null) {
147                        IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(
148                                        trieOrder - 1);
149                        context.add(Event.STARTEVENT);
150
151                        Event<?> currentState = Event.STARTEVENT;
152
153                        boolean endFound = false;
154
155                        while (!endFound) {
156                                double randVal = r.nextDouble();
157                                double probSum = 0.0;
158                                List<Event<?>> currentContext = context.getLast(trieOrder);
159                                for (Event<?> symbol : trie.getKnownSymbols()) {
160                                        probSum += getProbability(currentContext, symbol);
161                                        if (probSum >= randVal) {
162                                                endFound = (symbol == Event.ENDEVENT);
163                                                if (!(symbol == Event.STARTEVENT || symbol == Event.ENDEVENT)) {
164                                                        // only add the symbol the sequence if it is not
165                                                        // START
166                                                        // or END
167                                                        context.add(symbol);
168                                                        currentState = symbol;
169                                                        sequence.add(currentState);
170                                                }
171                                                break;
172                                        }
173                                }
174                        }
175                }
176                return sequence;
177        }
178
179        /**
180         * <p>
181         * Returns a Dot representation of the internal trie.
182         * </p>
183         *
184         * @return dot representation of the internal trie
185         */
186        public String getTrieDotRepresentation() {
187                if (trie == null) {
188                        return "";
189                } else {
190                        return trie.getDotRepresentation();
191                }
192        }
193
194        /**
195         * <p>
196         * Returns a {@link Tree} of the internal trie that can be used for
197         * visualization.
198         * </p>
199         *
200         * @return {@link Tree} depicting the internal trie
201         */
202        public Tree<TrieVertex, Edge> getTrieGraph() {
203                if (trie == null) {
204                        return null;
205                } else {
206                        return trie.getGraph();
207                }
208        }
209
210        /**
211         * <p>
212         * The string representation of the model is {@link Trie#toString()} of
213         * {@link #trie}.
214         * </p>
215         *
216         * @see java.lang.Object#toString()
217         */
218        @Override
219        public String toString() {
220                if (trie == null) {
221                        return "";
222                } else {
223                        return trie.toString();
224                }
225        }
226
227        /*
228         * (non-Javadoc)
229         *
230         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumStates()
231         */
232        @Override
233        public int getNumSymbols() {
234                if (trie == null) {
235                        return 0;
236                } else {
237                        return trie.getNumSymbols();
238                }
239        }
240
241        /*
242         * (non-Javadoc)
243         *
244         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getStateStrings()
245         */
246        @Override
247        public String[] getSymbolStrings() {
248                if (trie == null) {
249                        return new String[0];
250                }
251                String[] stateStrings = new String[getNumSymbols()];
252                int i = 0;
253                for (Event<?> symbol : trie.getKnownSymbols()) {
254                        stateStrings[i] = symbol.toString();
255                        i++;
256                }
257                return stateStrings;
258        }
259
260        /*
261         * (non-Javadoc)
262         *
263         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getEvents()
264         */
265        @Override
266        public Collection<? extends Event<?>> getEvents() {
267                if (trie == null) {
268                        return new HashSet<Event<?>>();
269                } else {
270                        return trie.getKnownSymbols();
271                }
272        }
273
274        /*
275         * (non-Javadoc)
276         *
277         * @see
278         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int)
279         */
280        @Override
281        public Collection<List<? extends Event<?>>> generateSequences(int length) {
282                return generateSequences(length, false);
283        }
284
285        /*
286         * (non-Javadoc)
287         *
288         * @see
289         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int,
290         * boolean)
291         */
292        @Override
293        public Set<List<? extends Event<?>>> generateSequences(int length,
294                        boolean fromStart) {
295                Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();
296                if (length < 1) {
297                        throw new InvalidParameterException(
298                                        "Length of generated subsequences must be at least 1.");
299                }
300                if (length == 1) {
301                        if (fromStart) {
302                                List<Event<?>> subSeq = new LinkedList<Event<?>>();
303                                subSeq.add(Event.STARTEVENT);
304                                sequenceSet.add(subSeq);
305                        } else {
306                                for (Event<?> event : getEvents()) {
307                                        List<Event<?>> subSeq = new LinkedList<Event<?>>();
308                                        subSeq.add(event);
309                                        sequenceSet.add(subSeq);
310                                }
311                        }
312                        return sequenceSet;
313                }
314                Collection<? extends Event<?>> events = getEvents();
315                Collection<List<? extends Event<?>>> seqsShorter = generateSequences(
316                                length - 1, fromStart);
317                for (Event<?> event : events) {
318                        for (List<? extends Event<?>> seqShorter : seqsShorter) {
319                                Event<?> lastEvent = event;
320                                if (getProbability(seqShorter, lastEvent) > 0.0) {
321                                        List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
322                                        subSeq.add(lastEvent);
323                                        sequenceSet.add(subSeq);
324                                }
325                        }
326                }
327                return sequenceSet;
328        }
329
330        /*
331         * (non-Javadoc)
332         *
333         * @see
334         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateValidSequences
335         * (int)
336         */
337        @Override
338        public Collection<List<? extends Event<?>>> generateValidSequences(
339                        int length) {
340                // check for min-length implicitly done by generateSequences
341                Collection<List<? extends Event<?>>> allSequences = generateSequences(
342                                length, true);
343                Collection<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>();
344                for (List<? extends Event<?>> sequence : allSequences) {
345                        if (sequence.size() == length
346                                        && Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) {
347                                validSequences.add(sequence);
348                        }
349                }
350                return validSequences;
351        }
352
353        /*
354         * (non-Javadoc)
355         *
356         * @see
357         * de.ugoe.cs.eventbench.models.IStochasticProcess#getProbability(java.util
358         * .List)
359         */
360        @Override
361        public double getProbability(List<? extends Event<?>> sequence) {
362                if (sequence == null) {
363                        throw new InvalidParameterException("sequence must not be null");
364                }
365                double prob = 1.0;
366                List<Event<?>> context = new LinkedList<Event<?>>();
367                for (Event<?> event : sequence) {
368                        prob *= getProbability(context, event);
369                        context.add(event);
370                }
371                return prob;
372        }
373
374        /*
375         * (non-Javadoc)
376         *
377         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumFOMStates()
378         */
379        @Override
380        public int getNumFOMStates() {
381                if (trie == null) {
382                        return 0;
383                } else {
384                        return trie.getNumLeafAncestors();
385                }
386        }
387
388        /*
389         * (non-Javadoc)
390         *
391         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumTransitions()
392         */
393        @Override
394        public int getNumTransitions() {
395                if (trie == null) {
396                        return 0;
397                } else {
398                        return trie.getNumLeafs();
399                }
400        }
401}
Note: See TracBrowser for help on using the repository browser.