1 | package de.ugoe.cs.eventbench.coverage;
|
---|
2 |
|
---|
3 | import java.security.InvalidParameterException;
|
---|
4 | import java.util.ArrayList;
|
---|
5 | import java.util.LinkedHashMap;
|
---|
6 | import java.util.LinkedHashSet;
|
---|
7 | import java.util.LinkedList;
|
---|
8 | import java.util.List;
|
---|
9 | import java.util.Map;
|
---|
10 | import java.util.Set;
|
---|
11 |
|
---|
12 | import de.ugoe.cs.eventbench.data.Event;
|
---|
13 | import de.ugoe.cs.eventbench.models.IStochasticProcess;
|
---|
14 |
|
---|
15 | public class CoverageCalculator {
|
---|
16 |
|
---|
17 | private final IStochasticProcess process;
|
---|
18 | private final List<List<Event<?>>> sequences;
|
---|
19 | private final int length;
|
---|
20 |
|
---|
21 | private Set<List<Event<?>>> containedSubSeqs = null;
|
---|
22 | private Set<List<Event<?>>> allPossibleSubSeqs = null;
|
---|
23 | private Map<List<Event<?>>, Double> subSeqWeights = null;
|
---|
24 |
|
---|
25 | |
---|
26 | public CoverageCalculator(IStochasticProcess process, List<List<Event<?>>> sequences, int length) {
|
---|
27 | this.process = process;
|
---|
28 | this.sequences = sequences;
|
---|
29 | this.length = length;
|
---|
30 | }
|
---|
31 |
|
---|
32 |
|
---|
33 | public double getCoverageAllNoWeight() {
|
---|
34 | if( containedSubSeqs==null ) {
|
---|
35 | containedSubSeqs = containedSubSequences(sequences, length);
|
---|
36 | }
|
---|
37 | return((double) containedSubSeqs.size())/numSequences(process, length);
|
---|
38 | }
|
---|
39 |
|
---|
40 | public double getCoveragePossibleNoWeight() {
|
---|
41 | if( containedSubSeqs==null ) {
|
---|
42 | containedSubSeqs = containedSubSequences(sequences, length);
|
---|
43 | }
|
---|
44 | if( allPossibleSubSeqs==null ) {
|
---|
45 | allPossibleSubSeqs = generateSubSequences(process, length);
|
---|
46 | }
|
---|
47 | return((double) containedSubSeqs.size())/allPossibleSubSeqs.size();
|
---|
48 | }
|
---|
49 |
|
---|
50 | public double getCoveragePossibleWeight() {
|
---|
51 | if( containedSubSeqs==null ) {
|
---|
52 | containedSubSeqs = containedSubSequences(sequences, length);
|
---|
53 | }
|
---|
54 | if( allPossibleSubSeqs==null ) {
|
---|
55 | allPossibleSubSeqs = generateSubSequences(process, length);
|
---|
56 | }
|
---|
57 | if( subSeqWeights==null ) {
|
---|
58 | subSeqWeights = generateWeights(process, allPossibleSubSeqs);
|
---|
59 | }
|
---|
60 | double weight = 0.0;
|
---|
61 | for( List<Event<?>> subSeq : containedSubSeqs ) {
|
---|
62 | weight += subSeqWeights.get(subSeq);
|
---|
63 | }
|
---|
64 | return weight;
|
---|
65 | }
|
---|
66 |
|
---|
67 | private Map<List<Event<?>>, Double> generateWeights(IStochasticProcess process, Set<List<Event<?>>> sequences) {
|
---|
68 | Map<List<Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<Event<?>>, Double>();
|
---|
69 | double sum = 0.0;
|
---|
70 | for( List<Event<?>> sequence : sequences ) {
|
---|
71 | double prob = 1.0;
|
---|
72 | List<Event<?>> context = new LinkedList<Event<?>>();
|
---|
73 | for( Event<?> event : sequence ) {
|
---|
74 | prob *= process.getProbability(context, event);
|
---|
75 | context.add(event);
|
---|
76 | }
|
---|
77 | subSeqWeights.put(sequence, prob);
|
---|
78 | sum += prob;
|
---|
79 | }
|
---|
80 | if( sum<1.0 ) {
|
---|
81 | for( Map.Entry<List<Event<?>>, Double> entry : subSeqWeights.entrySet() ) {
|
---|
82 | entry.setValue(entry.getValue()/sum);
|
---|
83 | }
|
---|
84 | }
|
---|
85 | return subSeqWeights;
|
---|
86 | }
|
---|
87 |
|
---|
88 | private long numSequences(IStochasticProcess process, int length) {
|
---|
89 | return (long) Math.pow(process.getNumStates(), length);
|
---|
90 | }
|
---|
91 |
|
---|
92 | // O(symbols^length)
|
---|
93 | private Set<List<Event<?>>> generateSubSequences(IStochasticProcess process, int length) {
|
---|
94 | Set<List<Event<?>>> subSequenceSet = new LinkedHashSet<List<Event<?>>>();;
|
---|
95 | if( length<1 ) {
|
---|
96 | throw new InvalidParameterException("Length of generated subsequences must be at least 1.");
|
---|
97 | }
|
---|
98 | if( length==1 ) {
|
---|
99 | for( Event<?> event : process.getEvents() ) {
|
---|
100 | List<Event<?>> subSeq = new LinkedList<Event<?>>();
|
---|
101 | subSeq.add(event);
|
---|
102 | subSequenceSet.add(subSeq);
|
---|
103 | }
|
---|
104 | return subSequenceSet;
|
---|
105 | }
|
---|
106 | Set<Event<?>> events = process.getEvents();
|
---|
107 | Set<List<Event<?>>> subSeqsShorter = generateSubSequences(process, length-1);
|
---|
108 | for( Event<?> event : events ) {
|
---|
109 | for( List<Event<?>> subSequence : subSeqsShorter ) {
|
---|
110 | Event<?> lastEvent = event;
|
---|
111 | if( process.getProbability(subSequence, lastEvent)>0.0 ) {
|
---|
112 | List<Event<?>> subSeq = new ArrayList<Event<?>>(subSequence);
|
---|
113 | subSeq.add(lastEvent);
|
---|
114 | subSequenceSet.add(subSeq);
|
---|
115 | }
|
---|
116 | }
|
---|
117 | }
|
---|
118 | return subSequenceSet;
|
---|
119 | }
|
---|
120 |
|
---|
121 | // O(numSeq*lenSeq)
|
---|
122 | private Set<List<Event<?>>> containedSubSequences(List<List<Event<?>>> sequences, int length) {
|
---|
123 | Set<List<Event<?>>> containedSubSeqs = new LinkedHashSet<List<Event<?>>>();
|
---|
124 | List<Event<?>> subSeq = new LinkedList<Event<?>>();
|
---|
125 | boolean minLengthReached = false;
|
---|
126 | for( List<Event<?>> sequence : sequences ) {
|
---|
127 | for( Event<?> event : sequence ) {
|
---|
128 | subSeq.add(event);
|
---|
129 | if( !minLengthReached ) {
|
---|
130 | if( subSeq.size()==length ) {
|
---|
131 | minLengthReached=true;
|
---|
132 | }
|
---|
133 | } else {
|
---|
134 | subSeq.remove(0);
|
---|
135 | }
|
---|
136 | if( minLengthReached ) {
|
---|
137 | if( !containedSubSeqs.contains(subSeq) ) {
|
---|
138 | containedSubSeqs.add(new LinkedList<Event<?>>(subSeq));
|
---|
139 | }
|
---|
140 | }
|
---|
141 | }
|
---|
142 | }
|
---|
143 | return containedSubSeqs;
|
---|
144 | }
|
---|
145 |
|
---|
146 | }
|
---|