Ignore:
Timestamp:
04/13/11 15:53:14 (14 years ago)
Author:
sherbold
Message:

+ added class TrieBasedModel? as base class for all usage models that calculate probabilities based on a trie
+ extracted everything except the probability calculation from PPM to TrieBasedModel?
+ added HighOrderMarkovModel? based on TrieBasedModel?

Location:
trunk/EventBenchCore/src/de/ugoe/cs/eventbench
Files:
2 added
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java

    r7 r12  
    11package de.ugoe.cs.eventbench.data; 
     2 
     3import java.security.InvalidParameterException; 
    24 
    35 
    … …  
    3234         
    3335        public Event(String type) { 
     36                if( type==null ) { 
     37                        throw new InvalidParameterException("Event type must not be null"); 
     38                } 
    3439                this.type = type; 
    3540        } 
    … …  
    4146                } 
    4247                if (other instanceof Event<?>) { 
    43                         Event<?> otherToken = (Event<?>) other; 
    44                         return otherToken.type.equals(this.type) 
    45                                         && otherToken.target.equals(this.target); 
     48                        Event<?> otherEvent = (Event<?>) other; 
     49                        if( target!=null ) { 
     50                                return type.equals(otherEvent.type) 
     51                                        && target.equals(otherEvent.target); 
     52                        } else { 
     53                                return type.equals(otherEvent.type) 
     54                                        && target==otherEvent.target; 
     55                        } 
    4656                } else { 
    4757                        return false; 
    … …  
    7080 
    7181        public String getStandardId() { 
    72                 String id = target + "." + getType(); 
     82                String id = ""; 
     83                if( target!=null ) { 
     84                        id += target + "."; 
     85                } 
     86                id += getType(); 
    7387                if ( idInfo!="" ) { 
    7488                        id += "." + idInfo; 

  • trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java

    r9 r12  
    11package de.ugoe.cs.eventbench.ppm; 
    22 
     3import java.util.ArrayList; 
    34import java.util.LinkedList; 
    45import java.util.List; 
    … …  
    67 
    78import de.ugoe.cs.eventbench.data.Event; 
    8 import de.ugoe.cs.eventbench.markov.IncompleteMemory; 
     9import de.ugoe.cs.util.console.Console; 
    910 
    10 public class PredictionByPartialMatch { 
     11public class PredictionByPartialMatch extends TrieBasedModel { 
    1112         
    12         private int maxOrder; 
    13          
    14         private Trie<Event<?>> trie; 
    15          
    16         private double probEscape; 
    17          
    18         private final Random r; 
     13        double probEscape; 
    1914         
    2015        public PredictionByPartialMatch(int maxOrder, Random r) { 
    … …  
    2318         
    2419        public PredictionByPartialMatch(int maxOrder, Random r, double probEscape) { 
    25                 this.maxOrder = maxOrder; 
    26                 this.r = r; // TODO defensive copy instead? 
     20                super(maxOrder, r); 
    2721                this.probEscape = probEscape; 
    2822        } 
    … …  
    3630        } 
    3731         
    38         // the training is basically the generation of the trie 
    39         public void train(List<List<Event<?>>> sequences) { 
    40                 trie = new Trie<Event<?>>(); 
    41                  
    42                 for(List<Event<?>> sequence : sequences) { 
    43                         List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive copy 
    44                         currentSequence.add(0, Event.STARTEVENT); 
    45                         currentSequence.add(Event.ENDEVENT); 
    46                          
    47                         trie.train(currentSequence, maxOrder); 
    48                 } 
    49         } 
    50          
    51         /*private void addToTrie(List<Event<?>> sequence) { 
    52                 if( knownSymbols==null ) { 
    53                         knownSymbols = new LinkedHashSet<Event<?>>(); 
    54                 } 
    55                 IncompleteMemory<Event<?>> latestActions = new IncompleteMemory<Event<?>>(maxOrder); 
    56                 int i=0; 
    57                 for(Event<?> currentEvent : sequence) { 
    58                         latestActions.add(currentEvent); 
    59                         knownSymbols.add(currentEvent); 
    60                         i++; 
    61                         if( i>=maxOrder ) { 
    62                                 trie.add(latestActions.getLast(maxOrder)); 
    63                         } 
    64                 } 
    65                 int sequenceLength = sequence.size(); 
    66                 for( int j=maxOrder-1 ; j>0 ; j-- ) { 
    67                         trie.add(sequence.subList(sequenceLength-j, sequenceLength)); 
    68                 } 
    69         }*/ 
    70          
    71         public List<? extends Event<?>> randomSequence() { 
    72                 List<Event<?>> sequence = new LinkedList<Event<?>>(); 
    73                  
    74                 IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(maxOrder-1); 
    75                 context.add(Event.STARTEVENT); 
    76                  
    77                 Event<?> currentState = Event.STARTEVENT; 
    78                  
    79                 boolean endFound = false; 
    80                  
    81                 while(!endFound) { 
    82                         double randVal = r.nextDouble(); 
    83                         double probSum = 0.0; 
    84                         List<Event<?>> currentContext = context.getLast(maxOrder); 
    85                         for( Event<?> symbol : trie.getKnownSymbols() ) { 
    86                                 probSum += getProbability(currentContext, symbol); 
    87                                 if( probSum>=randVal ) { 
    88                                         endFound = (symbol==Event.ENDEVENT); 
    89                                         if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) { 
    90                                                 // only add the symbol the sequence if it is not START or END 
    91                                                 context.add(symbol); 
    92                                                 currentState = symbol; 
    93                                                 sequence.add(currentState); 
    94                                         } 
    95                                         break; 
    96                                 } 
    97                         } 
    98                 } 
    99                 return sequence; 
    100         } 
    101                  
    102         private double getProbability(List<Event<?>> context, Event<?> symbol) { 
     32        @Override 
     33        protected double getProbability(List<Event<?>> context, Event<?> symbol) { 
    10334                double result = 0.0d; 
    10435                double resultCurrentContex = 0.0d; 
    … …  
    13263        } 
    13364         
    134         @Override 
    135         public String toString() { 
    136                 return trie.toString(); 
    137         } 
    138          
    139         /* 
    14065        public void testStuff() { 
    14166                // basically an inline unit test without assertions but manual observation 
    142                 List<String> list = new ArrayList<String>(); 
    143                 list.add(initialSymbol); 
    144                 list.add("a"); 
    145                 list.add("b"); 
    146                 list.add("r"); 
    147                 list.add("a"); 
    148                 list.add("c"); 
    149                 list.add("a"); 
    150                 list.add("d"); 
    151                 list.add("a"); 
    152                 list.add("b"); 
    153                 list.add("r"); 
    154                 list.add("a"); 
    155                 list.add(endSymbol); 
     67                List<Event<?>> list = new ArrayList<Event<?>>(); 
     68                list.add(new Event<Object>("a")); 
     69                list.add(new Event<Object>("b")); 
     70                list.add(new Event<Object>("r")); 
     71                list.add(new Event<Object>("a")); 
     72                list.add(new Event<Object>("c")); 
     73                list.add(new Event<Object>("a")); 
     74                list.add(new Event<Object>("d")); 
     75                list.add(new Event<Object>("a")); 
     76                list.add(new Event<Object>("b")); 
     77                list.add(new Event<Object>("r")); 
     78                list.add(new Event<Object>("a")); 
    15679                 
    157                 PredictionByPartialMatch model = new PredictionByPartialMatch(); 
    158                 model.trie = new Trie<String>(); 
    159                 model.trainStringTrie(list); 
     80                int maxOrder = 3; 
     81                PredictionByPartialMatch model = new PredictionByPartialMatch(maxOrder, new Random()); 
     82                model.trie = new Trie<Event<?>>(); 
     83                model.trie.train(list, maxOrder); 
    16084                model.trie.display(); 
    16185                 
    162                 List<String> context = new ArrayList<String>(); 
    163                 String symbol = "a"; 
     86                List<Event<?>> context = new ArrayList<Event<?>>(); 
     87                Event<Object> symbol = new Event<Object>("a"); 
    16488                // expected: 5 
    16589                Console.traceln(""+model.trie.getCount(context, symbol)); 
    16690                 
    16791                // expected: 0 
    168                 context.add("b"); 
     92                context.add(new Event<Object>("b")); 
    16993                Console.traceln(""+model.trie.getCount(context, symbol)); 
    17094                 
    17195                // expected: 2 
    172                 context.add("r"); 
     96                context.add(new Event<Object>("r")); 
    17397                Console.traceln(""+model.trie.getCount(context, symbol)); 
    17498                 
    17599                // exptected: [b, r] 
    176                 context = new ArrayList<String>(); 
    177                 context.add("a"); 
    178                 context.add("b"); 
    179                 context.add("r"); 
     100                context = new ArrayList<Event<?>>(); 
     101                context.add(new Event<Object>("a")); 
     102                context.add(new Event<Object>("b")); 
     103                context.add(new Event<Object>("r")); 
    180104                Console.traceln(model.trie.getContextSuffix(context).toString()); 
    181105                 
    182106                // exptected: [] 
    183                 context = new ArrayList<String>(); 
    184                 context.add("e"); 
     107                context = new ArrayList<Event<?>>(); 
     108                context.add(new Event<Object>("e")); 
    185109                Console.traceln(model.trie.getContextSuffix(context).toString()); 
    186110                 
    187111                // exptected: {a, b, c, d, r} 
    188                 context = new ArrayList<String>(); 
     112                context = new ArrayList<Event<?>>(); 
    189113                Console.traceln(model.trie.getFollowingSymbols(context).toString()); 
    190114                 
    191115                // exptected: {b, c, d} 
    192                 context = new ArrayList<String>(); 
    193                 context.add("a"); 
     116                context = new ArrayList<Event<?>>(); 
     117                context.add(new Event<Object>("a")); 
    194118                Console.traceln(model.trie.getFollowingSymbols(context).toString()); 
    195119                 
    196120                // exptected: [] 
    197                 context = new ArrayList<String>(); 
    198                 context.add("a"); 
    199                 context.add("b"); 
    200                 context.add("r"); 
     121                context = new ArrayList<Event<?>>(); 
     122                context.add(new Event<Object>("a")); 
     123                context.add(new Event<Object>("b")); 
     124                context.add(new Event<Object>("r")); 
    201125                Console.traceln(model.trie.getFollowingSymbols(context).toString()); 
    202126                 
    203127                // exptected: 0.0d 
    204                 context = new ArrayList<String>(); 
    205                 context.add("a"); 
    206                 Console.traceln(""+model.getProbability(context, "z")); 
    207         }*/ 
     128                context = new ArrayList<Event<?>>(); 
     129                context.add(new Event<Object>("a")); 
     130                Console.traceln(""+model.getProbability(context, new Event<Object>("z"))); 
     131        } 
    208132} 
Note: See TracChangeset for help on using the changeset viewer.