Changeset 559


Ignore:
Timestamp:
08/17/12 09:05:19 (12 years ago)
Author:
sherbold
Message:
  • adapted to quest coding style
Location:
trunk
Files:
22 edited

Legend:

Unmodified
Added
Removed

  • trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/FileEqualsAssertEvent.java

    r548 r559  
     1 
    12package de.ugoe.cs.quest.assertions; 
    23 

  • trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/FileEqualsReplay.java

    r548 r559  
     1 
    12package de.ugoe.cs.quest.assertions; 
    23 
    … …  
    1617public class FileEqualsReplay implements IReplayable { 
    1718 
    18         /** 
    19         * <p> 
    20         * The file that should be equal to expectedFile. 
    21         * </p> 
    22         */ 
    23         protected final String actualFile; 
     19    /** 
     20    * <p> 
     21    * The file that should be equal to expectedFile. 
     22    * </p> 
     23    */ 
     24    protected final String actualFile; 
    2425 
    25         /** 
    26         * <p> 
    27         * The file that is used as the reference. 
    28         * </p> 
    29         */ 
    30         protected final String expectedFile; 
     26    /** 
     27    * <p> 
     28    * The file that is used as the reference. 
     29    * </p> 
     30    */ 
     31    protected final String expectedFile; 
    3132 
    32         /** 
    33         * <p> 
    34         * Id for object serialization. 
    35         * </p> 
    36         */ 
    37         private static final long serialVersionUID = 1L; 
     33    /** 
     34    * <p> 
     35    * Id for object serialization. 
     36    * </p> 
     37    */ 
     38    private static final long serialVersionUID = 1L; 
    3839 
    39         /** 
    40          * <p> 
    41          * Constructor. Creates a new FileEqualsReplay. 
    42          * </p> 
    43          *  
    44          * @param expectedFile 
    45          *            name and path of the expected file 
    46          * @param actualFile 
    47          *            name and path of the actual file 
    48          * @throws InvalidParameterException 
    49          *             thrown if expectedFile or actualFile are null 
    50          */ 
    51         public FileEqualsReplay(String expectedFile, String actualFile) { 
    52                 if (expectedFile == null) { 
    53                         throw new InvalidParameterException( 
    54                                         "expected file must not be null"); 
    55                 } 
    56                 if (actualFile == null) { 
    57                         throw new InvalidParameterException("actual file must not be null"); 
    58                 } 
    59                 this.expectedFile = expectedFile; 
    60                 this.actualFile = actualFile; 
    61         } 
     40    /** 
     41     * <p> 
     42     * Constructor. Creates a new FileEqualsReplay. 
     43     * </p> 
     44     *  
     45     * @param expectedFile 
     46     *            name and path of the expected file 
     47     * @param actualFile 
     48     *            name and path of the actual file 
     49     * @throws InvalidParameterException 
     50     *             thrown if expectedFile or actualFile are null 
     51     */ 
     52    public FileEqualsReplay(String expectedFile, String actualFile) { 
     53        if (expectedFile == null) { 
     54            throw new InvalidParameterException("expected file must not be null"); 
     55        } 
     56        if (actualFile == null) { 
     57            throw new InvalidParameterException("actual file must not be null"); 
     58        } 
     59        this.expectedFile = expectedFile; 
     60        this.actualFile = actualFile; 
     61    } 
    6262 
    63         /* 
    64         * (non-Javadoc) 
    65         *  
    66         * @see de.ugoe.cs.quest.eventcore.IReplayable#getReplay() 
    67         */ 
    68         public String getReplay() { 
     63    /* 
     64    * (non-Javadoc) 
     65    *  
     66    * @see de.ugoe.cs.quest.eventcore.IReplayable#getReplay() 
     67    */ 
     68    public String getReplay() { 
    6969 
    70                 String actualFileTmp = StringTools.xmlEntityReplacement(actualFile); 
    71                 String expectedFileTmp = StringTools.xmlEntityReplacement(expectedFile); 
     70        String actualFileTmp = StringTools.xmlEntityReplacement(actualFile); 
     71        String expectedFileTmp = StringTools.xmlEntityReplacement(expectedFile); 
    7272 
    73                 StringBuilder currentMsgStr = new StringBuilder(800); 
    74                 currentMsgStr.append("  <fileEquals "); 
    75                 currentMsgStr.append("actualFile=\"" + actualFileTmp + "\" "); 
    76                 currentMsgStr.append("expectedFile=\"" + expectedFileTmp + "\"/>"); 
    77                 currentMsgStr.append(StringTools.ENDLINE); 
    78                 return currentMsgStr.toString(); 
    79         } 
     73        StringBuilder currentMsgStr = new StringBuilder(800); 
     74        currentMsgStr.append("  <fileEquals "); 
     75        currentMsgStr.append("actualFile=\"" + actualFileTmp + "\" "); 
     76        currentMsgStr.append("expectedFile=\"" + expectedFileTmp + "\"/>"); 
     77        currentMsgStr.append(StringTools.ENDLINE); 
     78        return currentMsgStr.toString(); 
     79    } 
    8080 
    8181} 

  • trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/TextEqualsAssertEventType.java

    r548 r559  
     1 
    12package de.ugoe.cs.quest.assertions; 
    23 

  • trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/TextEqualsReplay.java

    r548 r559  
     1 
    12package de.ugoe.cs.quest.assertions; 
    23 
    … …  
    1617public class TextEqualsReplay implements IReplayable { 
    1718 
    18         /** 
    19         * <p> 
    20         * Reference value which is compared to the targets text. 
    21         * </p> 
    22         */ 
    23         protected final String expectedValue; 
     19    /** 
     20    * <p> 
     21    * Reference value which is compared to the targets text. 
     22    * </p> 
     23    */ 
     24    protected final String expectedValue; 
    2425 
    25         /** 
    26         * <p> 
    27         * Target to which the text is compared. 
    28         * </p> 
    29         */ 
    30         protected final String target; 
     26    /** 
     27    * <p> 
     28    * Target to which the text is compared. 
     29    * </p> 
     30    */ 
     31    protected final String target; 
    3132 
    32         /** 
    33         * <p> 
    34         * Id for object serialization. 
    35         * </p> 
    36         */ 
    37         private static final long serialVersionUID = 1L; 
     33    /** 
     34    * <p> 
     35    * Id for object serialization. 
     36    * </p> 
     37    */ 
     38    private static final long serialVersionUID = 1L; 
    3839 
    39         /** 
    40         * <p> 
    41         * Constructor. Creates a new TextEqualsReplay. 
    42         *  
    43         * @param expectedValue 
    44         *            expected string value 
    45         * @param target 
    46          *            string description of the target whose string value is 
    47          *            compared to the expected value 
    48         * @throws InvalidParameterException 
    49         *             thrown if target is null 
    50         */ 
    51         public TextEqualsReplay(String expectedValue, String target) { 
    52                 if (target == null) { 
    53                         throw new InvalidParameterException("target must not be null"); 
    54                 } 
    55                 this.expectedValue = expectedValue; 
    56                 this.target = target; 
    57         } 
     40    /** 
     41    * <p> 
     42    * Constructor. Creates a new TextEqualsReplay. 
     43    *  
     44    * @param expectedValue 
     45    *            expected string value 
     46    * @param target 
     47     *            string description of the target whose string value is compared to the expected 
     48     *            value 
     49    * @throws InvalidParameterException 
     50    *             thrown if target is null 
     51    */ 
     52    public TextEqualsReplay(String expectedValue, String target) { 
     53        if (target == null) { 
     54            throw new InvalidParameterException("target must not be null"); 
     55        } 
     56        this.expectedValue = expectedValue; 
     57        this.target = target; 
     58    } 
    5859 
    59         /* 
    60         * (non-Javadoc) 
    61         *  
    62         * @see de.ugoe.cs.quest.eventcore.IReplayable#getReplay() 
    63         */ 
    64         @Override 
    65         public String getReplay() { 
     60    /* 
     61    * (non-Javadoc) 
     62    *  
     63    * @see de.ugoe.cs.quest.eventcore.IReplayable#getReplay() 
     64    */ 
     65    @Override 
     66    public String getReplay() { 
    6667 
    67                 String expectedValueTmp = StringTools.xmlEntityReplacement(expectedValue); 
     68        String expectedValueTmp = StringTools.xmlEntityReplacement(expectedValue); 
    6869 
    69                 StringBuilder currentMsgStr = new StringBuilder(400); 
    70                 currentMsgStr.append(" <textEquals expectedValue=\"" + expectedValueTmp 
    71                                 + "\">"); 
    72                 currentMsgStr.append(StringTools.ENDLINE); 
    73                 currentMsgStr.append("<target>"); 
    74                 currentMsgStr.append(StringTools.ENDLINE); 
    75                 currentMsgStr.append(target); 
    76                 currentMsgStr.append(StringTools.ENDLINE); 
    77                 currentMsgStr.append("</target>"); 
    78                 currentMsgStr.append(StringTools.ENDLINE); 
    79                 currentMsgStr.append("</textEquals>"); 
    80                 currentMsgStr.append(StringTools.ENDLINE); 
    81                 return currentMsgStr.toString(); 
    82         } 
     70        StringBuilder currentMsgStr = new StringBuilder(400); 
     71        currentMsgStr.append(" <textEquals expectedValue=\"" + expectedValueTmp + "\">"); 
     72        currentMsgStr.append(StringTools.ENDLINE); 
     73        currentMsgStr.append("<target>"); 
     74        currentMsgStr.append(StringTools.ENDLINE); 
     75        currentMsgStr.append(target); 
     76        currentMsgStr.append(StringTools.ENDLINE); 
     77        currentMsgStr.append("</target>"); 
     78        currentMsgStr.append(StringTools.ENDLINE); 
     79        currentMsgStr.append("</textEquals>"); 
     80        currentMsgStr.append(StringTools.ENDLINE); 
     81        return currentMsgStr.toString(); 
     82    } 
    8383 
    84         /* 
    85         * (non-Javadoc) 
    86         *  
    87         * @see de.ugoe.cs.quest.eventcore.IReplayable#getTarget() 
    88         */ 
    89         //@Override TODO 
    90         public String getTarget() { 
    91                 return target; 
    92         } 
     84    /* 
     85    * (non-Javadoc) 
     86    *  
     87    * @see de.ugoe.cs.quest.eventcore.IReplayable#getTarget() 
     88    */ 
     89    // @Override TODO 
     90    public String getTarget() { 
     91        return target; 
     92    } 
    9393 
    9494} 

  • trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorObserved.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.coverage; 
    23 
    … …  
    1213/** 
    1314 * <p> 
    14  * This class calculates various types of sequence coverage in relation to a 
    15  * collection of observed sequences. 
     15 * This class calculates various types of sequence coverage in relation to a collection of observed 
     16 * sequences. 
    1617 * </p> 
    1718 *  
    … …  
    2122public class CoverageCalculatorObserved { 
    2223 
    23         /** 
    24          * <p> 
    25          * Sequences for which the coverage is calculated. 
    26          * </p> 
    27          */ 
    28         private final Collection<List<Event>> sequences; 
    29  
    30         /** 
    31          * <p> 
    32          * Observed sequences that are baseline for the coverage calculation. 
    33          * </p> 
    34          */ 
    35         private final Collection<List<Event>> observedSequences; 
    36  
    37         /** 
    38          * <p> 
    39          * Length of the subsequences in relation to which the covarage is 
    40          * calculated. 
    41          * </p> 
    42          */ 
    43         private final int length; 
    44  
    45         /** 
    46          * <p> 
    47          * All subsequences of {@link #length} of {@link #sequences}. 
    48          * </p> 
    49          */ 
    50         private Collection<List<Event>> subSeqsGenerated = null; 
    51  
    52         /** 
    53          * <p> 
    54          * All subsequences of {@link #length} of {@link #observedSequences}. 
    55          * </p> 
    56          */ 
    57         private Collection<List<Event>> subSeqsObserved = null; 
    58  
    59         /** 
    60          * <p> 
    61          * Constructor. Creates a new CoverageCalculatorObserved for given 
    62          * collections of observed sequences and generated sequences. 
    63          * </p> 
    64          *  
    65          * @param observedSequences 
    66          *            observed sequences in relation to which the coverage is 
    67          *            calculated; must not be null 
    68          * @param sequences 
    69          *            sequences for which the coverage is calculated; must not be 
    70          *            null 
    71          * @param length 
    72          *            length of the subsequences for which the coverage is analyzed; 
    73          *            must be >0 
    74          * @throws InvalidParameterException 
    75          *             thrown if observedSequences or sequences is null or length 
    76          *             less than or equal to 0 
    77          */ 
    78         public CoverageCalculatorObserved( 
    79                         Collection<List<Event>> observedSequences, 
    80                         Collection<List<Event>> sequences, int length) { 
    81                 if (observedSequences == null) { 
    82                         throw new InvalidParameterException( 
    83                                         "observed sequences must not be null"); 
    84                 } 
    85                 if (sequences == null) { 
    86                         throw new InvalidParameterException("sequences must not be null"); 
    87                 } 
    88                 if (length <= 0) { 
    89                         throw new InvalidParameterException( 
    90                                         "length must be >0; actual value: " + length); 
    91                 } 
    92                 this.observedSequences = observedSequences; 
    93                 this.sequences = sequences; 
    94                 this.length = length; 
    95         } 
    96  
    97         /** 
    98          * <p> 
    99          * Calculates the percentage of subsequences of length k that occur, with 
    100          * reference to those that were observed. 
    101          * </p> 
    102          *  
    103          * @return coverage percentage 
    104          */ 
    105         public double getCoverageObserved() { 
    106                 createSubSeqs(); 
    107                 Collection<List<Event>> subSeqsObservedCopy = new LinkedHashSet<List<Event>>( 
    108                                 subSeqsObserved); 
    109                 subSeqsObservedCopy.retainAll(subSeqsGenerated); 
    110                 return ((double) subSeqsObservedCopy.size()) / subSeqsObserved.size(); 
    111         } 
    112  
    113         /** 
    114          * <p> 
    115          * Calculates the weight of subsequences of length k that occur, with 
    116          * reference to those that were observed. 
    117          * </p> 
    118          *  
    119          * @param process 
    120          *            stochastic process in reference to which the weight is 
    121          *            calculated 
    122          * @return coverage percentage 
    123          */ 
    124  
    125         public double getCoverageObservedWeigth(IStochasticProcess process) { 
    126                 createSubSeqs(); 
    127                 Map<List<Event>, Double> weightMap = SequenceTools 
    128                                 .generateWeights(process, subSeqsObserved); 
    129  
    130                 Collection<List<Event>> subSeqsObservedCopy = new LinkedHashSet<List<Event>>( 
    131                                 subSeqsObserved); 
    132                 subSeqsObservedCopy.retainAll(subSeqsGenerated); 
    133                 double weight = 0.0d; 
    134                 for (List<Event> subSeq : subSeqsObservedCopy) { 
    135                         weight += weightMap.get(subSeq); 
    136                 } 
    137                 return weight; 
    138         } 
    139  
    140         /** 
    141          * <p> 
    142          * Calculates the percentage of generated subsequences of length k that 
    143          * occur and have not been observed, with reference to all generated 
    144          * subsequences. 
    145          * </p> 
    146          *  
    147          * @return coverage percentage 
    148          */ 
    149         public double getNewPercentage() { 
    150                 createSubSeqs(); 
    151                 Collection<List<Event>> subSeqsGeneratedCopy = new LinkedHashSet<List<Event>>( 
    152                                 subSeqsGenerated); 
    153                 subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
    154                 return ((double) subSeqsGeneratedCopy.size()) / subSeqsGenerated.size(); 
    155         } 
    156  
    157         /** 
    158          * <p> 
    159          * Calculates the percentage of generated subsequences of length k that 
    160          * occur and have not been observed, with references to all possible new 
    161          * subsequences. 
    162          * </p> 
    163          *  
    164          * @param process 
    165          *            stochastic process which is used to determine which 
    166          *            subsequences are possible 
    167          * @return coverage percentage 
    168          * @throws InvalidParameterException 
    169          *             thrown if process is null 
    170          */ 
    171         public double getCoveragePossibleNew(IStochasticProcess process) { 
    172                 if (process == null) { 
    173                         throw new InvalidParameterException("process must not be null"); 
    174                 } 
    175                 createSubSeqs(); 
    176                 Collection<List<Event>> subSeqsGeneratedCopy = new LinkedHashSet<List<Event>>( 
    177                                 subSeqsGenerated); 
    178                 Collection<List<Event>> subSeqsPossible = process 
    179                                 .generateSequences(length); 
    180                 subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
    181                 subSeqsPossible.removeAll(subSeqsObserved); 
    182                 int possibleSize = subSeqsPossible.size(); 
    183                 subSeqsPossible.retainAll(subSeqsGeneratedCopy); 
    184                 return ((double) subSeqsPossible.size()) / possibleSize; 
    185         } 
    186  
    187         /** 
    188          * <p> 
    189          * Calculates the weight of generated subsequences of length k that occur 
    190          * and have not been observed, with references to all possible new 
    191          * subsequences. 
    192          * </p> 
    193          *  
    194          * @param process 
    195          *            stochastic process which is used to determine the weights and 
    196          *            which subsequences are possible 
    197          * @return coverage percentage 
    198          * @throws InvalidParameterException 
    199          *             thrown if process is null 
    200          */ 
    201         public double getCoveragePossibleNewWeight(IStochasticProcess process) { 
    202                 if (process == null) { 
    203                         throw new InvalidParameterException("process must not be null"); 
    204                 } 
    205                 createSubSeqs(); 
    206                 Collection<List<Event>> subSeqsGeneratedCopy = new LinkedHashSet<List<Event>>( 
    207                                 subSeqsGenerated); 
    208                 Collection<List<Event>> subSeqsPossible = process 
    209                                 .generateSequences(length); 
    210                 subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
    211                 subSeqsPossible.removeAll(subSeqsObserved); 
    212                 Map<List<Event>, Double> weightMap = SequenceTools 
    213                                 .generateWeights(process, subSeqsPossible); 
    214                 double weight = 0.0d; 
    215                 for (List<Event> subSeq : subSeqsGeneratedCopy) { 
    216                         Double currentWeight = weightMap.get(subSeq); 
    217                         if( currentWeight!=null ) { 
    218                                 weight += currentWeight; 
    219                         } 
    220                 } 
    221                 return weight; 
    222         } 
    223  
    224         /** 
    225          * <p> 
    226          * Returns the number of covered subsequences of length k. 
    227          * </p> 
    228          *  
    229          * @return number of covered subsequences 
    230          */ 
    231         public int getNumObserved() { 
    232                 createSubSeqs(); 
    233                 return subSeqsObserved.size(); 
    234         } 
    235  
    236         /** 
    237          * <p> 
    238          * Returns the number of covered subsequences of length k. 
    239          * </p> 
    240          *  
    241          * @return number of covered subsequences 
    242          */ 
    243         public int getNumCovered() { 
    244                 createSubSeqs(); 
    245                 return subSeqsGenerated.size(); 
    246         } 
    247  
    248         public int getNumNew() { 
    249                 createSubSeqs(); 
    250                 Collection<List<Event>> subSeqsGeneratedCopy = new LinkedHashSet<List<Event>>( 
    251                                 subSeqsGenerated); 
    252                 subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
    253                 return subSeqsGeneratedCopy.size(); 
    254         } 
    255  
    256         /** 
    257          * <p> 
    258          * Helper function that calcuates the subsequences of length k that have 
    259          * been observed and generated. 
    260          * </p> 
    261          */ 
    262         private void createSubSeqs() { 
    263                 if (subSeqsObserved == null) { 
    264                         subSeqsObserved = SequenceTools.containedSubSequences( 
    265                                         observedSequences, length); 
    266                 } 
    267                 if (subSeqsGenerated == null) { 
    268                         subSeqsGenerated = SequenceTools.containedSubSequences(sequences, 
    269                                         length); 
    270                 } 
    271         } 
     24    /** 
     25     * <p> 
     26     * Sequences for which the coverage is calculated. 
     27     * </p> 
     28     */ 
     29    private final Collection<List<Event>> sequences; 
     30 
     31    /** 
     32     * <p> 
     33     * Observed sequences that are baseline for the coverage calculation. 
     34     * </p> 
     35     */ 
     36    private final Collection<List<Event>> observedSequences; 
     37 
     38    /** 
     39     * <p> 
     40     * Length of the subsequences in relation to which the covarage is calculated. 
     41     * </p> 
     42     */ 
     43    private final int length; 
     44 
     45    /** 
     46     * <p> 
     47     * All subsequences of {@link #length} of {@link #sequences}. 
     48     * </p> 
     49     */ 
     50    private Collection<List<Event>> subSeqsGenerated = null; 
     51 
     52    /** 
     53     * <p> 
     54     * All subsequences of {@link #length} of {@link #observedSequences}. 
     55     * </p> 
     56     */ 
     57    private Collection<List<Event>> subSeqsObserved = null; 
     58 
     59    /** 
     60     * <p> 
     61     * Constructor. Creates a new CoverageCalculatorObserved for given collections of observed 
     62     * sequences and generated sequences. 
     63     * </p> 
     64     *  
     65     * @param observedSequences 
     66     *            observed sequences in relation to which the coverage is calculated; must not be 
     67     *            null 
     68     * @param sequences 
     69     *            sequences for which the coverage is calculated; must not be null 
     70     * @param length 
     71     *            length of the subsequences for which the coverage is analyzed; must be >0 
     72     * @throws InvalidParameterException 
     73     *             thrown if observedSequences or sequences is null or length less than or equal to 
     74     *             0 
     75     */ 
     76    public CoverageCalculatorObserved(Collection<List<Event>> observedSequences, 
     77                                      Collection<List<Event>> sequences, 
     78                                      int length) 
     79    { 
     80        if (observedSequences == null) { 
     81            throw new InvalidParameterException("observed sequences must not be null"); 
     82        } 
     83        if (sequences == null) { 
     84            throw new InvalidParameterException("sequences must not be null"); 
     85        } 
     86        if (length <= 0) { 
     87            throw new InvalidParameterException("length must be >0; actual value: " + length); 
     88        } 
     89        this.observedSequences = observedSequences; 
     90        this.sequences = sequences; 
     91        this.length = length; 
     92    } 
     93 
     94    /** 
     95     * <p> 
     96     * Calculates the percentage of subsequences of length k that occur, with reference to those 
     97     * that were observed. 
     98     * </p> 
     99     *  
     100     * @return coverage percentage 
     101     */ 
     102    public double getCoverageObserved() { 
     103        createSubSeqs(); 
     104        Collection<List<Event>> subSeqsObservedCopy = 
     105            new LinkedHashSet<List<Event>>(subSeqsObserved); 
     106        subSeqsObservedCopy.retainAll(subSeqsGenerated); 
     107        return ((double) subSeqsObservedCopy.size()) / subSeqsObserved.size(); 
     108    } 
     109 
     110    /** 
     111     * <p> 
     112     * Calculates the weight of subsequences of length k that occur, with reference to those that 
     113     * were observed. 
     114     * </p> 
     115     *  
     116     * @param process 
     117     *            stochastic process in reference to which the weight is calculated 
     118     * @return coverage percentage 
     119     */ 
     120 
     121    public double getCoverageObservedWeigth(IStochasticProcess process) { 
     122        createSubSeqs(); 
     123        Map<List<Event>, Double> weightMap = 
     124            SequenceTools.generateWeights(process, subSeqsObserved); 
     125 
     126        Collection<List<Event>> subSeqsObservedCopy = 
     127            new LinkedHashSet<List<Event>>(subSeqsObserved); 
     128        subSeqsObservedCopy.retainAll(subSeqsGenerated); 
     129        double weight = 0.0d; 
     130        for (List<Event> subSeq : subSeqsObservedCopy) { 
     131            weight += weightMap.get(subSeq); 
     132        } 
     133        return weight; 
     134    } 
     135 
     136    /** 
     137     * <p> 
     138     * Calculates the percentage of generated subsequences of length k that occur and have not been 
     139     * observed, with reference to all generated subsequences. 
     140     * </p> 
     141     *  
     142     * @return coverage percentage 
     143     */ 
     144    public double getNewPercentage() { 
     145        createSubSeqs(); 
     146        Collection<List<Event>> subSeqsGeneratedCopy = 
     147            new LinkedHashSet<List<Event>>(subSeqsGenerated); 
     148        subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
     149        return ((double) subSeqsGeneratedCopy.size()) / subSeqsGenerated.size(); 
     150    } 
     151 
     152    /** 
     153     * <p> 
     154     * Calculates the percentage of generated subsequences of length k that occur and have not been 
     155     * observed, with references to all possible new subsequences. 
     156     * </p> 
     157     *  
     158     * @param process 
     159     *            stochastic process which is used to determine which subsequences are possible 
     160     * @return coverage percentage 
     161     * @throws InvalidParameterException 
     162     *             thrown if process is null 
     163     */ 
     164    public double getCoveragePossibleNew(IStochasticProcess process) { 
     165        if (process == null) { 
     166            throw new InvalidParameterException("process must not be null"); 
     167        } 
     168        createSubSeqs(); 
     169        Collection<List<Event>> subSeqsGeneratedCopy = 
     170            new LinkedHashSet<List<Event>>(subSeqsGenerated); 
     171        Collection<List<Event>> subSeqsPossible = process.generateSequences(length); 
     172        subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
     173        subSeqsPossible.removeAll(subSeqsObserved); 
     174        int possibleSize = subSeqsPossible.size(); 
     175        subSeqsPossible.retainAll(subSeqsGeneratedCopy); 
     176        return ((double) subSeqsPossible.size()) / possibleSize; 
     177    } 
     178 
     179    /** 
     180     * <p> 
     181     * Calculates the weight of generated subsequences of length k that occur and have not been 
     182     * observed, with references to all possible new subsequences. 
     183     * </p> 
     184     *  
     185     * @param process 
     186     *            stochastic process which is used to determine the weights and which subsequences 
     187     *            are possible 
     188     * @return coverage percentage 
     189     * @throws InvalidParameterException 
     190     *             thrown if process is null 
     191     */ 
     192    public double getCoveragePossibleNewWeight(IStochasticProcess process) { 
     193        if (process == null) { 
     194            throw new InvalidParameterException("process must not be null"); 
     195        } 
     196        createSubSeqs(); 
     197        Collection<List<Event>> subSeqsGeneratedCopy = 
     198            new LinkedHashSet<List<Event>>(subSeqsGenerated); 
     199        Collection<List<Event>> subSeqsPossible = process.generateSequences(length); 
     200        subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
     201        subSeqsPossible.removeAll(subSeqsObserved); 
     202        Map<List<Event>, Double> weightMap = 
     203            SequenceTools.generateWeights(process, subSeqsPossible); 
     204        double weight = 0.0d; 
     205        for (List<Event> subSeq : subSeqsGeneratedCopy) { 
     206            Double currentWeight = weightMap.get(subSeq); 
     207            if (currentWeight != null) { 
     208                weight += currentWeight; 
     209            } 
     210        } 
     211        return weight; 
     212    } 
     213 
     214    /** 
     215     * <p> 
     216     * Returns the number of covered subsequences of length k. 
     217     * </p> 
     218     *  
     219     * @return number of covered subsequences 
     220     */ 
     221    public int getNumObserved() { 
     222        createSubSeqs(); 
     223        return subSeqsObserved.size(); 
     224    } 
     225 
     226    /** 
     227     * <p> 
     228     * Returns the number of covered subsequences of length k. 
     229     * </p> 
     230     *  
     231     * @return number of covered subsequences 
     232     */ 
     233    public int getNumCovered() { 
     234        createSubSeqs(); 
     235        return subSeqsGenerated.size(); 
     236    } 
     237 
     238    public int getNumNew() { 
     239        createSubSeqs(); 
     240        Collection<List<Event>> subSeqsGeneratedCopy = 
     241            new LinkedHashSet<List<Event>>(subSeqsGenerated); 
     242        subSeqsGeneratedCopy.removeAll(subSeqsObserved); 
     243        return subSeqsGeneratedCopy.size(); 
     244    } 
     245 
     246    /** 
     247     * <p> 
     248     * Helper function that calcuates the subsequences of length k that have been observed and 
     249     * generated. 
     250     * </p> 
     251     */ 
     252    private void createSubSeqs() { 
     253        if (subSeqsObserved == null) { 
     254            subSeqsObserved = SequenceTools.containedSubSequences(observedSequences, length); 
     255        } 
     256        if (subSeqsGenerated == null) { 
     257            subSeqsGenerated = SequenceTools.containedSubSequences(sequences, length); 
     258        } 
     259    } 
    272260} 

  • trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorProcess.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.coverage; 
    23 
    … …  
    1112/** 
    1213 * <p> 
    13  * This class calculates various types of sequence coverage in relation to a 
    14  * stochastic process. 
     14 * This class calculates various types of sequence coverage in relation to a stochastic process. 
    1515 * </p> 
    1616 *  
    … …  
    2020public class CoverageCalculatorProcess { 
    2121 
    22         /** 
    23          * <p> 
    24          * Stochastic process that is the foundation for probabilistic coverages and 
    25          * coverages with reference to all possible sequences. 
    26          * </p> 
    27          */ 
    28         private final IStochasticProcess process; 
    29  
    30         /** 
    31          * <p> 
    32          * Sequences for which the coverage is calculated. 
    33          * </p> 
    34          */ 
    35         private Collection<List<Event>> sequences; 
    36  
    37         /** 
    38          * <p> 
    39          * Length of the subsequences in relation to which the coverage is 
    40          * calculated. 
    41          * </p> 
    42          */ 
    43         private final int length; 
    44  
    45         /** 
    46          * <p> 
    47          * All subsequences of {@link #length} of {@link #sequences}. 
    48          * </p> 
    49          */ 
    50         private Collection<List<Event>> containedSubSeqs = null; 
    51  
    52         /** 
    53          * <p> 
    54          * All subsequences of {@link #length} that can be generated by 
    55          * {@link #process}. 
    56          * </p> 
    57          */ 
    58         private Collection<List<Event>> allPossibleSubSeqs = null; 
    59  
    60         /** 
    61          * <p> 
    62          * The probabilities of all subsequences of {@link #length} according to 
    63          * {@link #process}. 
    64          * </p> 
    65          */ 
    66         private Map<List<Event>, Double> subSeqWeights = null; 
    67  
    68         /** 
    69          * <p> 
    70          * Constructor. Creates a new CoverageCalculatorProcess for a given 
    71          * stochastic process and generated sequences. 
    72          * </p> 
    73          *  
    74          * @param process 
    75          *            stochastic process used for coverage calculations; must not be 
    76          *            null 
    77          * @param sequences 
    78          *            sequences for which the coverage is calculated; must not be 
    79          *            null 
    80          * @param length 
    81          *            length of the subsequences for which the coverage is analyzed; 
    82          *            must be >0 
    83          * @throws InvalidParameterException 
    84          *             thrown if process or sequences is null or length less than or equal to 0 
    85          */ 
    86         public CoverageCalculatorProcess(IStochasticProcess process, 
    87                         Collection<List<Event>> sequences, int length) { 
    88                 if (process == null) { 
    89                         throw new InvalidParameterException("process must not be null"); 
    90                 } 
    91                 if (sequences == null) { 
    92                         throw new InvalidParameterException("sequences must not be null"); 
    93                 } 
    94                 if (length <= 0) { 
    95                         throw new InvalidParameterException( 
    96                                         "length must be >0; actual value: " + length); 
    97                 } 
    98                 this.process = process; 
    99                 this.sequences = sequences; 
    100                 this.length = length; 
    101         } 
    102  
    103         /** 
    104          * <p> 
    105          * Calculates the percentage of subsequences of length k that occur, 
    106          * including those that cannot be generated by {@link #process}. 
    107          * </p> 
    108          *  
    109          * @return coverage percentage 
    110          */ 
    111         public double getCoverageAllNoWeight() { 
    112                 if (containedSubSeqs == null) { 
    113                         containedSubSeqs = SequenceTools.containedSubSequences(sequences, 
    114                                         length); 
    115                 } 
    116                 return ((double) containedSubSeqs.size()) 
    117                                 / SequenceTools.numSequences(process, length); 
    118         } 
    119  
    120         /** 
    121          * <p> 
    122          * Calculates the percentage of subsequences of length k that occur and can 
    123          * generated by {@link #process}. 
    124          * </p> 
    125          *  
    126          * @return coverage percentage 
    127          */ 
    128         public double getCoveragePossibleNoWeight() { 
    129                 if (containedSubSeqs == null) { 
    130                         containedSubSeqs = SequenceTools.containedSubSequences(sequences, 
    131                                         length); 
    132                 } 
    133                 if (allPossibleSubSeqs == null) { 
    134                         allPossibleSubSeqs = process.generateSequences(length); 
    135                 } 
    136                 return ((double) containedSubSeqs.size()) / allPossibleSubSeqs.size(); 
    137         } 
    138  
    139         /** 
    140          * <p> 
    141          * Calculates the weight of the subsequences that occur with relation to 
    142          * {@link #process}, i.e., the mass of the subsequence probability covered 
    143          * by the subsequences. 
    144          * </p> 
    145          *  
    146          * @return coverage weight 
    147          */ 
    148         public double getCoveragePossibleWeight() { 
    149                 if (containedSubSeqs == null) { 
    150                         containedSubSeqs = SequenceTools.containedSubSequences(sequences, 
    151                                         length); 
    152                 } 
    153                 if (allPossibleSubSeqs == null) { 
    154                         allPossibleSubSeqs = process.generateSequences(length); 
    155                 } 
    156                 if (subSeqWeights == null) { 
    157                         subSeqWeights = SequenceTools.generateWeights(process, 
    158                                         allPossibleSubSeqs); 
    159                 } 
    160                 double weight = 0.0; 
    161                 for (List<Event> subSeq : containedSubSeqs) { 
    162                         Double curWeight = subSeqWeights.get(subSeq); 
    163                         if( curWeight!=null ) { 
    164                                 weight += curWeight; 
    165                         } 
    166                 } 
    167                 return weight; 
    168         } 
    169  
    170         /** 
    171          * <p> 
    172          * Returns the number of covered subsequences of length k. 
    173          * </p> 
    174          *  
    175          * @return number of covered subsequences 
    176          */ 
    177         public int getNumCovered() { 
    178                 if (containedSubSeqs == null) { 
    179                         containedSubSeqs = SequenceTools.containedSubSequences(sequences, 
    180                                         length); 
    181                 } 
    182                 return containedSubSeqs.size(); 
    183         } 
    184  
    185         /** 
    186          * <p> 
    187          * Returns the number of possible subsequences of length k according to the 
    188          * stochastic process. 
    189          * </p> 
    190          *  
    191          * @return number of possible subsequences 
    192          */ 
    193         public int getNumPossible() { 
    194                 if (allPossibleSubSeqs == null) { 
    195                         allPossibleSubSeqs = process.generateSequences(length); 
    196                 } 
    197                 return allPossibleSubSeqs.size(); 
    198         } 
    199  
    200         /** 
    201          * <p> 
    202          * Sets a new collection of sequences for which the coverage is analyzed. 
    203          * </p> 
    204          *  
    205          * @param newSequences 
    206          *            new collection of sequences 
    207          * @throws InvalidParameterException 
    208          *             thrown is newSequences is null 
    209          */ 
    210         public void setSequences(Collection<List<Event>> newSequences) { 
    211                 if (newSequences == null) { 
    212                         throw new InvalidParameterException("sequences must not be null"); 
    213                 } 
    214                 this.sequences = newSequences; 
    215                 containedSubSeqs = null; 
    216         } 
     22    /** 
     23     * <p> 
     24     * Stochastic process that is the foundation for probabilistic coverages and coverages with 
     25     * reference to all possible sequences. 
     26     * </p> 
     27     */ 
     28    private final IStochasticProcess process; 
     29 
     30    /** 
     31     * <p> 
     32     * Sequences for which the coverage is calculated. 
     33     * </p> 
     34     */ 
     35    private Collection<List<Event>> sequences; 
     36 
     37    /** 
     38     * <p> 
     39     * Length of the subsequences in relation to which the coverage is calculated. 
     40     * </p> 
     41     */ 
     42    private final int length; 
     43 
     44    /** 
     45     * <p> 
     46     * All subsequences of {@link #length} of {@link #sequences}. 
     47     * </p> 
     48     */ 
     49    private Collection<List<Event>> containedSubSeqs = null; 
     50 
     51    /** 
     52     * <p> 
     53     * All subsequences of {@link #length} that can be generated by {@link #process}. 
     54     * </p> 
     55     */ 
     56    private Collection<List<Event>> allPossibleSubSeqs = null; 
     57 
     58    /** 
     59     * <p> 
     60     * The probabilities of all subsequences of {@link #length} according to {@link #process}. 
     61     * </p> 
     62     */ 
     63    private Map<List<Event>, Double> subSeqWeights = null; 
     64 
     65    /** 
     66     * <p> 
     67     * Constructor. Creates a new CoverageCalculatorProcess for a given stochastic process and 
     68     * generated sequences. 
     69     * </p> 
     70     *  
     71     * @param process 
     72     *            stochastic process used for coverage calculations; must not be null 
     73     * @param sequences 
     74     *            sequences for which the coverage is calculated; must not be null 
     75     * @param length 
     76     *            length of the subsequences for which the coverage is analyzed; must be >0 
     77     * @throws InvalidParameterException 
     78     *             thrown if process or sequences is null or length less than or equal to 0 
     79     */ 
     80    public CoverageCalculatorProcess(IStochasticProcess process, 
     81                                     Collection<List<Event>> sequences, 
     82                                     int length) 
     83    { 
     84        if (process == null) { 
     85            throw new InvalidParameterException("process must not be null"); 
     86        } 
     87        if (sequences == null) { 
     88            throw new InvalidParameterException("sequences must not be null"); 
     89        } 
     90        if (length <= 0) { 
     91            throw new InvalidParameterException("length must be >0; actual value: " + length); 
     92        } 
     93        this.process = process; 
     94        this.sequences = sequences; 
     95        this.length = length; 
     96    } 
     97 
     98    /** 
     99     * <p> 
     100     * Calculates the percentage of subsequences of length k that occur, including those that cannot 
     101     * be generated by {@link #process}. 
     102     * </p> 
     103     *  
     104     * @return coverage percentage 
     105     */ 
     106    public double getCoverageAllNoWeight() { 
     107        if (containedSubSeqs == null) { 
     108            containedSubSeqs = SequenceTools.containedSubSequences(sequences, length); 
     109        } 
     110        return ((double) containedSubSeqs.size()) / SequenceTools.numSequences(process, length); 
     111    } 
     112 
     113    /** 
     114     * <p> 
     115     * Calculates the percentage of subsequences of length k that occur and can generated by 
     116     * {@link #process}. 
     117     * </p> 
     118     *  
     119     * @return coverage percentage 
     120     */ 
     121    public double getCoveragePossibleNoWeight() { 
     122        if (containedSubSeqs == null) { 
     123            containedSubSeqs = SequenceTools.containedSubSequences(sequences, length); 
     124        } 
     125        if (allPossibleSubSeqs == null) { 
     126            allPossibleSubSeqs = process.generateSequences(length); 
     127        } 
     128        return ((double) containedSubSeqs.size()) / allPossibleSubSeqs.size(); 
     129    } 
     130 
     131    /** 
     132     * <p> 
     133     * Calculates the weight of the subsequences that occur with relation to {@link #process}, i.e., 
     134     * the mass of the subsequence probability covered by the subsequences. 
     135     * </p> 
     136     *  
     137     * @return coverage weight 
     138     */ 
     139    public double getCoveragePossibleWeight() { 
     140        if (containedSubSeqs == null) { 
     141            containedSubSeqs = SequenceTools.containedSubSequences(sequences, length); 
     142        } 
     143        if (allPossibleSubSeqs == null) { 
     144            allPossibleSubSeqs = process.generateSequences(length); 
     145        } 
     146        if (subSeqWeights == null) { 
     147            subSeqWeights = SequenceTools.generateWeights(process, allPossibleSubSeqs); 
     148        } 
     149        double weight = 0.0; 
     150        for (List<Event> subSeq : containedSubSeqs) { 
     151            Double curWeight = subSeqWeights.get(subSeq); 
     152            if (curWeight != null) { 
     153                weight += curWeight; 
     154            } 
     155        } 
     156        return weight; 
     157    } 
     158 
     159    /** 
     160     * <p> 
     161     * Returns the number of covered subsequences of length k. 
     162     * </p> 
     163     *  
     164     * @return number of covered subsequences 
     165     */ 
     166    public int getNumCovered() { 
     167        if (containedSubSeqs == null) { 
     168            containedSubSeqs = SequenceTools.containedSubSequences(sequences, length); 
     169        } 
     170        return containedSubSeqs.size(); 
     171    } 
     172 
     173    /** 
     174     * <p> 
     175     * Returns the number of possible subsequences of length k according to the stochastic process. 
     176     * </p> 
     177     *  
     178     * @return number of possible subsequences 
     179     */ 
     180    public int getNumPossible() { 
     181        if (allPossibleSubSeqs == null) { 
     182            allPossibleSubSeqs = process.generateSequences(length); 
     183        } 
     184        return allPossibleSubSeqs.size(); 
     185    } 
     186 
     187    /** 
     188     * <p> 
     189     * Sets a new collection of sequences for which the coverage is analyzed. 
     190     * </p> 
     191     *  
     192     * @param newSequences 
     193     *            new collection of sequences 
     194     * @throws InvalidParameterException 
     195     *             thrown is newSequences is null 
     196     */ 
     197    public void setSequences(Collection<List<Event>> newSequences) { 
     198        if (newSequences == null) { 
     199            throw new InvalidParameterException("sequences must not be null"); 
     200        } 
     201        this.sequences = newSequences; 
     202        containedSubSeqs = null; 
     203    } 
    217204 
    218205} 

  • trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/SequenceTools.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.coverage; 
    23 
    … …  
    2223 */ 
    2324public class SequenceTools { 
    24          
    25         /** 
    26          * <p> 
    27          * Private constructor to prevent initializing of the class. 
    28          * </p> 
    29          */ 
    30         private SequenceTools() { 
    31                  
    32         } 
    3325 
    34         /** 
    35          * <p> 
    36          * Calculates the weights for all sequences passed to this function as 
    37          * defined by the stochastic process and stores them in a {@link Map}. The 
    38          * weights are normalized, i.e., the sum of all weights contained in this 
    39          * map is 1. 
    40          * </p> 
    41          *  
    42          * @param process 
    43          *            process used for weight calculation 
    44          * @param sequences 
    45          *            sequences for which the weights are calculated 
    46          * @return {@link Map} of weights 
    47          */ 
    48         public static Map<List<Event>, Double> generateWeights( 
    49                         IStochasticProcess process, 
    50                         Collection<List<Event>> sequences) { 
    51                 Map<List<Event>, Double> subSeqWeights = new LinkedHashMap<List<Event>, Double>(); 
    52                 if (sequences != null && !sequences.isEmpty()) { 
    53                         if (process != null) { 
    54                                 double sum = 0.0; 
    55                                 for (List<Event> sequence : sequences) { 
    56                                         double prob = process.getProbability(sequence); 
    57                                         subSeqWeights.put(sequence, prob); 
    58                                         sum += prob; 
    59                                 } 
    60                                 if (sum < 1.0) { 
    61                                         for (Map.Entry<List<Event>, Double> entry : subSeqWeights 
    62                                                         .entrySet()) { 
    63                                                 entry.setValue(entry.getValue() / sum); 
    64                                         } 
    65                                 } 
    66                         } else { 
    67                                 for( List<Event> sequence : sequences ) { 
    68                                         subSeqWeights.put(sequence, 0.0d); 
    69                                 } 
    70                         } 
    71                 } 
    72                 return subSeqWeights; 
    73         } 
     26    /** 
     27     * <p> 
     28     * Private constructor to prevent initializing of the class. 
     29     * </p> 
     30     */ 
     31    private SequenceTools() { 
    7432 
    75         /** 
    76          * <p> 
    77          * Calculates the number of all existing sequences of a given length, 
    78          * regardless whether they are possible or not. 
    79          * </p> 
    80          *  
    81          * @param process 
    82          *            stochastic process whose symbols are the basis for this 
    83          *            calculation 
    84          * @param length 
    85          *            lenght of the sequences 
    86          * @return numStates^length 
    87          * @throws InvalidParameterException 
    88          *             thrown if length less or equal to 0 
    89          */ 
    90         public static long numSequences(IStochasticProcess process, int length) { 
    91                 if (length <= 0) { 
    92                         throw new InvalidParameterException( 
    93                                         "length must be a positive integer"); 
    94                 } 
    95                 long result = 0; 
    96                 if (process != null) { 
    97                         result = (long) Math.pow(process.getNumSymbols(), length); 
    98                 } 
    99                 return result; 
    100         } 
     33    } 
    10134 
    102         /** 
    103          * <p> 
    104          * Creates a {@link Set} of all subsequences of a given length that are 
    105          * contained in a sequence collection. 
    106          * </p> 
    107          *  
    108          * @param sequences 
    109          *            sequences from which the subsequences are extracted 
    110          * @param length 
    111          *            length of the subsequences 
    112          * @return {@link Set} of all subsequences 
    113          * @throws InvalidParameterException 
    114          *             thrown if length less or equal to 0 
    115          */ 
    116         public static Set<List<Event>> containedSubSequences( 
    117                         Collection<List<Event>> sequences, int length) { 
    118                 if (length <= 0) { 
    119                         throw new InvalidParameterException( 
    120                                         "length must be a positive integer"); 
    121                 } 
    122                 Set<List<Event>> containedSubSeqs = new LinkedHashSet<List<Event>>(); 
    123                 if (sequences != null) { 
    124                         for (List<Event> sequence : sequences) { 
    125                                 List<Event> subSeq = new LinkedList<Event>(); 
    126                                 boolean minLengthReached = false; 
    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>( 
    139                                                                         subSeq)); 
    140                                                 } 
    141                                         } 
    142                                 } 
    143                         } 
    144                 } 
    145                 return containedSubSeqs; 
    146         } 
     35    /** 
     36     * <p> 
     37     * Calculates the weights for all sequences passed to this function as defined by the stochastic 
     38     * process and stores them in a {@link Map}. The weights are normalized, i.e., the sum of all 
     39     * weights contained in this map is 1. 
     40     * </p> 
     41     *  
     42     * @param process 
     43     *            process used for weight calculation 
     44     * @param sequences 
     45     *            sequences for which the weights are calculated 
     46     * @return {@link Map} of weights 
     47     */ 
     48    public static Map<List<Event>, Double> generateWeights(IStochasticProcess process, 
     49                                                           Collection<List<Event>> sequences) 
     50    { 
     51        Map<List<Event>, Double> subSeqWeights = new LinkedHashMap<List<Event>, Double>(); 
     52        if (sequences != null && !sequences.isEmpty()) { 
     53            if (process != null) { 
     54                double sum = 0.0; 
     55                for (List<Event> sequence : sequences) { 
     56                    double prob = process.getProbability(sequence); 
     57                    subSeqWeights.put(sequence, prob); 
     58                    sum += prob; 
     59                } 
     60                if (sum < 1.0) { 
     61                    for (Map.Entry<List<Event>, Double> entry : subSeqWeights.entrySet()) { 
     62                        entry.setValue(entry.getValue() / sum); 
     63                    } 
     64                } 
     65            } 
     66            else { 
     67                for (List<Event> sequence : sequences) { 
     68                    subSeqWeights.put(sequence, 0.0d); 
     69                } 
     70            } 
     71        } 
     72        return subSeqWeights; 
     73    } 
     74 
     75    /** 
     76     * <p> 
     77     * Calculates the number of all existing sequences of a given length, regardless whether they 
     78     * are possible or not. 
     79     * </p> 
     80     *  
     81     * @param process 
     82     *            stochastic process whose symbols are the basis for this calculation 
     83     * @param length 
     84     *            lenght of the sequences 
     85     * @return numStates^length 
     86     * @throws InvalidParameterException 
     87     *             thrown if length less or equal to 0 
     88     */ 
     89    public static long numSequences(IStochasticProcess process, int length) { 
     90        if (length <= 0) { 
     91            throw new InvalidParameterException("length must be a positive integer"); 
     92        } 
     93        long result = 0; 
     94        if (process != null) { 
     95            result = (long) Math.pow(process.getNumSymbols(), length); 
     96        } 
     97        return result; 
     98    } 
     99 
     100    /** 
     101     * <p> 
     102     * Creates a {@link Set} of all subsequences of a given length that are contained in a sequence 
     103     * collection. 
     104     * </p> 
     105     *  
     106     * @param sequences 
     107     *            sequences from which the subsequences are extracted 
     108     * @param length 
     109     *            length of the subsequences 
     110     * @return {@link Set} of all subsequences 
     111     * @throws InvalidParameterException 
     112     *             thrown if length less or equal to 0 
     113     */ 
     114    public static Set<List<Event>> containedSubSequences(Collection<List<Event>> sequences, 
     115                                                         int length) 
     116    { 
     117        if (length <= 0) { 
     118            throw new InvalidParameterException("length must be a positive integer"); 
     119        } 
     120        Set<List<Event>> containedSubSeqs = new LinkedHashSet<List<Event>>(); 
     121        if (sequences != null) { 
     122            for (List<Event> sequence : sequences) { 
     123                List<Event> subSeq = new LinkedList<Event>(); 
     124                boolean minLengthReached = false; 
     125                for (Event event : sequence) { 
     126                    subSeq.add(event); 
     127                    if (!minLengthReached) { 
     128                        if (subSeq.size() == length) { 
     129                            minLengthReached = true; 
     130                        } 
     131                    } 
     132                    else { 
     133                        subSeq.remove(0); 
     134                    } 
     135                    if (minLengthReached) { 
     136                        if (!containedSubSeqs.contains(subSeq)) { 
     137                            containedSubSeqs.add(new LinkedList<Event>(subSeq)); 
     138                        } 
     139                    } 
     140                } 
     141            } 
     142        } 
     143        return containedSubSeqs; 
     144    } 
    147145} 

  • trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/DrawFromAllSequencesGenerator.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.testgeneration; 
    23 
    … …  
    1718/** 
    1819 * <p> 
    19  * Generates a test suite by drawing from all possible sequences of a fixed 
    20  * length according to the probabilities of the sequences in a 
    21  * {@link IStochasticProcess}. 
     20 * Generates a test suite by drawing from all possible sequences of a fixed length according to the 
     21 * probabilities of the sequences in a {@link IStochasticProcess}. 
    2222 * </p> 
    2323 *  
    … …  
    2727public class DrawFromAllSequencesGenerator { 
    2828 
    29         /** 
    30         * <p> 
    31         * Number of sequences in the test suite. 
    32         * </p> 
    33         */ 
    34         private final int numSequences; 
     29    /** 
     30    * <p> 
     31    * Number of sequences in the test suite. 
     32    * </p> 
     33    */ 
     34    private final int numSequences; 
    3535 
    36         /** 
    37         * <p> 
    38         * Minimal length of a test sequence. 
    39         * </p> 
    40         */ 
    41         private final int minLength; 
     36    /** 
     37    * <p> 
     38    * Minimal length of a test sequence. 
     39    * </p> 
     40    */ 
     41    private final int minLength; 
    4242 
    43         /** 
    44         * <p> 
    45         * Maximal length of a test sequence. 
    46         * </p> 
    47         */ 
    48         private final int maxLength; 
     43    /** 
     44    * <p> 
     45    * Maximal length of a test sequence. 
     46    * </p> 
     47    */ 
     48    private final int maxLength; 
    4949 
    50         /** 
    51          * <p> 
    52          * In case this member is true, only test cases that end in the global end 
    53          * event {@link Event#ENDEVENT} are generated. If it is false, the end event 
    54          * can be any event. 
    55          * </p> 
    56          */ 
    57         private final boolean validEnd; 
     50    /** 
     51     * <p> 
     52     * In case this member is true, only test cases that end in the global end event 
     53     * {@link Event#ENDEVENT} are generated. If it is false, the end event can be any event. 
     54     * </p> 
     55     */ 
     56    private final boolean validEnd; 
    5857 
    59         /** 
    60         * <p> 
    61          * If this member is true, the generated test suite contains all possible 
    62          * sequences and {@link #numSequences} is ignored. 
    63         * </p> 
    64         */ 
    65         private final boolean generateAll; 
     58    /** 
     59    * <p> 
     60     * If this member is true, the generated test suite contains all possible sequences and 
     61     * {@link #numSequences} is ignored. 
     62    * </p> 
     63    */ 
     64    private final boolean generateAll; 
    6665 
    67         /** 
    68          * <p> 
    69          * Constructor. Creates a new DrawFromAllSequencesGenerator and ensures the 
    70          * validity of the parameters: 
    71          * <ul> 
    72          * <li>numSequences must at least be 1 
    73          * <li>maxLength must at least be 1 
    74          * <li>minLength must be less than or equal to maxLength 
    75          * </ul> 
    76          * If one of these conditions is violated an 
    77          * {@link InvalidParameterException} is thrown. 
    78          * </p> 
    79          *  
    80          * @param numSequences 
    81          *            number of sequences desired for the test suite 
    82          * @param minLength 
    83          *            minimal length of a test sequence 
    84          * @param maxLength 
    85          *            maximal length of a test sequence 
    86          * @param validEnd 
    87          *            defines if test cases have to end with the global end event 
    88          *            {@link Event#ENDEVENT} (see {@link #validEnd}) 
    89          * @param generateAll 
    90          *            if this parameter is true, the test suite contains all 
    91          *            possible sequences and numSequences is ignored 
    92          */ 
    93         public DrawFromAllSequencesGenerator(int numSequences, int minLength, 
    94                         int maxLength, boolean validEnd, boolean generateAll) { 
    95                 // check validity of the parameters 
    96                 if (numSequences < 1) { 
    97                         throw new InvalidParameterException( 
    98                                         "number of sequences must be at least 1 but is " 
    99                                                         + numSequences); 
    100                 } 
    101                 if (maxLength < 1) { 
    102                         throw new InvalidParameterException( 
    103                                         "maximal allowed length of test cases must be at least 1 but is " 
    104                                                         + maxLength); 
    105                 } 
    106                 if (minLength > maxLength) { 
    107                         throw new InvalidParameterException( 
    108                                         "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " 
    109                                                         + minLength + " ; max length: " + maxLength + ")"); 
    110                 } 
    111                 this.numSequences = numSequences; 
    112                 this.minLength = minLength; 
    113                 this.maxLength = maxLength; 
    114                 this.validEnd = validEnd; 
    115                 this.generateAll = generateAll; 
    116         } 
     66    /** 
     67     * <p> 
     68     * Constructor. Creates a new DrawFromAllSequencesGenerator and ensures the validity of the 
     69     * parameters: 
     70     * <ul> 
     71     * <li>numSequences must at least be 1 
     72     * <li>maxLength must at least be 1 
     73     * <li>minLength must be less than or equal to maxLength 
     74     * </ul> 
     75     * If one of these conditions is violated an {@link InvalidParameterException} is thrown. 
     76     * </p> 
     77     *  
     78     * @param numSequences 
     79     *            number of sequences desired for the test suite 
     80     * @param minLength 
     81     *            minimal length of a test sequence 
     82     * @param maxLength 
     83     *            maximal length of a test sequence 
     84     * @param validEnd 
     85     *            defines if test cases have to end with the global end event {@link Event#ENDEVENT} 
     86     *            (see {@link #validEnd}) 
     87     * @param generateAll 
     88     *            if this parameter is true, the test suite contains all possible sequences and 
     89     *            numSequences is ignored 
     90     */ 
     91    public DrawFromAllSequencesGenerator(int numSequences, 
     92                                         int minLength, 
     93                                         int maxLength, 
     94                                         boolean validEnd, 
     95                                         boolean generateAll) 
     96    { 
     97        // check validity of the parameters 
     98        if (numSequences < 1) { 
     99            throw new InvalidParameterException("number of sequences must be at least 1 but is " + 
     100                numSequences); 
     101        } 
     102        if (maxLength < 1) { 
     103            throw new InvalidParameterException( 
     104                                                "maximal allowed length of test cases must be at least 1 but is " + 
     105                                                    maxLength); 
     106        } 
     107        if (minLength > maxLength) { 
     108            throw new InvalidParameterException( 
     109                                                "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " + 
     110                                                    minLength + " ; max length: " + maxLength + ")"); 
     111        } 
     112        this.numSequences = numSequences; 
     113        this.minLength = minLength; 
     114        this.maxLength = maxLength; 
     115        this.validEnd = validEnd; 
     116        this.generateAll = generateAll; 
     117    } 
    117118 
    118         /** 
    119          * <p> 
    120          * Generates a test suite by drawing from all possible sequences with valid 
    121          * lengths. 
    122          * </p> 
    123          *  
    124          * @param model 
    125          *            model used to determine the probability of each possible 
    126          *            sequence 
    127          * @return the test suite 
    128          */ 
    129         public Collection<List<Event>> generateTestSuite( 
    130                         IStochasticProcess model) { 
    131                 if (model == null) { 
    132                         throw new InvalidParameterException("model must not be null!"); 
    133                 } 
     119    /** 
     120     * <p> 
     121     * Generates a test suite by drawing from all possible sequences with valid lengths. 
     122     * </p> 
     123     *  
     124     * @param model 
     125     *            model used to determine the probability of each possible sequence 
     126     * @return the test suite 
     127     */ 
     128    public Collection<List<Event>> generateTestSuite(IStochasticProcess model) { 
     129        if (model == null) { 
     130            throw new InvalidParameterException("model must not be null!"); 
     131        } 
    134132 
    135                 Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
    136                 for (int length = minLength; length <= maxLength; length++) { 
    137                         if (validEnd) { 
    138                                 sequences.addAll(model.generateValidSequences(length + 2)); 
    139                         } else { 
    140                                 sequences.addAll(model.generateSequences(length + 1, true)); 
    141                         } 
    142                 } 
    143                 Console.traceln("" + sequences.size() + " possible"); 
    144                 if (!generateAll && numSequences < sequences.size()) { 
    145                         List<Double> probabilities = new ArrayList<Double>(sequences.size()); 
    146                         double probSum = 0.0; 
    147                         for (List<Event> sequence : sequences) { 
    148                                 double prob = model.getProbability(sequence); 
    149                                 probabilities.add(prob); 
    150                                 probSum += prob; 
    151                         } 
    152                         Set<Integer> drawnSequences = new HashSet<Integer>(numSequences); 
    153                         Random r = new Random(); 
    154                         while (drawnSequences.size() < numSequences) { 
    155                                 double randVal = r.nextDouble() * probSum; 
    156                                 double sum = 0.0d; 
    157                                 int index = -1; 
    158                                 while (sum < randVal) { 
    159                                         index++; 
    160                                         double currentProb = probabilities.get(index); 
    161                                         sum += currentProb; 
    162                                 } 
    163                                 if (!drawnSequences.contains(index)) { 
    164                                         drawnSequences.add(index); 
    165                                         probSum -= probabilities.get(index); 
    166                                         probabilities.set(index, 0.0d); 
    167                                 } 
    168                         } 
    169                         Collection<List<Event>> retainedSequences = new LinkedList<List<Event>>(); 
    170                         int index = 0; 
    171                         for (List<Event> sequence : sequences) { 
    172                                 if (drawnSequences.contains(index)) { 
    173                                         retainedSequences.add(sequence); 
    174                                 } 
    175                                 index++; 
    176                         } 
    177                         sequences = retainedSequences; 
    178                 } 
    179                 return sequences; 
    180         } 
     133        Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
     134        for (int length = minLength; length <= maxLength; length++) { 
     135            if (validEnd) { 
     136                sequences.addAll(model.generateValidSequences(length + 2)); 
     137            } 
     138            else { 
     139                sequences.addAll(model.generateSequences(length + 1, true)); 
     140            } 
     141        } 
     142        Console.traceln("" + sequences.size() + " possible"); 
     143        if (!generateAll && numSequences < sequences.size()) { 
     144            List<Double> probabilities = new ArrayList<Double>(sequences.size()); 
     145            double probSum = 0.0; 
     146            for (List<Event> sequence : sequences) { 
     147                double prob = model.getProbability(sequence); 
     148                probabilities.add(prob); 
     149                probSum += prob; 
     150            } 
     151            Set<Integer> drawnSequences = new HashSet<Integer>(numSequences); 
     152            Random r = new Random(); 
     153            while (drawnSequences.size() < numSequences) { 
     154                double randVal = r.nextDouble() * probSum; 
     155                double sum = 0.0d; 
     156                int index = -1; 
     157                while (sum < randVal) { 
     158                    index++; 
     159                    double currentProb = probabilities.get(index); 
     160                    sum += currentProb; 
     161                } 
     162                if (!drawnSequences.contains(index)) { 
     163                    drawnSequences.add(index); 
     164                    probSum -= probabilities.get(index); 
     165                    probabilities.set(index, 0.0d); 
     166                } 
     167            } 
     168            Collection<List<Event>> retainedSequences = new LinkedList<List<Event>>(); 
     169            int index = 0; 
     170            for (List<Event> sequence : sequences) { 
     171                if (drawnSequences.contains(index)) { 
     172                    retainedSequences.add(sequence); 
     173                } 
     174                index++; 
     175            } 
     176            sequences = retainedSequences; 
     177        } 
     178        return sequences; 
     179    } 
    181180 
    182181} 

  • trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.testgeneration; 
    23 
    … …  
    1516/** 
    1617 * <p> 
    17  * Generates a test suite with a hybrid approach that is a mixture of random 
    18  * walks and drawing from all possible sequences. 
     18 * Generates a test suite with a hybrid approach that is a mixture of random walks and drawing from 
     19 * all possible sequences. 
    1920 * </p> 
    2021 *  
    … …  
    2425public class HybridGenerator { 
    2526 
    26         /** 
    27          * <p> 
    28          * Number of sequences in the test suite. 
    29          * </p> 
    30          */ 
    31         private final int numSequences; 
    32  
    33         /** 
    34          * <p> 
    35          * Length of a test sequence. 
    36          * </p> 
    37          */ 
    38         private final int length; 
    39  
    40         /** 
    41          * <p> 
    42          * Maximal length where it is possible to generate all sequences and draw 
    43          * from them. 
    44          * </p> 
    45          */ 
    46         private final int maxLengthAll; 
    47  
    48         /** 
    49          * <p> 
    50          * In case this member is true, only test cases that end in the global end 
    51          * event {@link Event#ENDEVENT} are generated. If it is false, the end event 
    52          * can be any event. 
    53          * </p> 
    54          */ 
    55         private final boolean validEnd; 
    56  
    57         /** 
    58          * <p> 
    59          * Constructor. Creates a new HybridGenerator and ensures the validity of 
    60          * the parameters: 
    61          * <ul> 
    62          * <li>numSequences must at least be 1 
    63          * <li>length must be at least 1 
    64          * </ul> 
    65          * If one of these conditions is violated an 
    66          * {@link InvalidParameterException} is thrown. 
    67          * </p> 
    68          *  
    69          * @param numSequences 
    70          *            number of sequences desired for the test suite 
    71          * @param length 
    72          *            length of a test sequence 
    73          * @param maxLengthAll 
    74          *            maximal length where it is possible to generate all sequences 
    75          *            and draw from them 
    76          * @param validEnd 
    77          *            defines if test cases have to end with the global end event 
    78          *            {@link Event#ENDEVENT} (see {@link #validEnd}) 
    79          */ 
    80         public HybridGenerator(int numSequences, int length, int maxLengthAll, 
    81                         boolean validEnd) { 
    82                 // check validity of the parameters 
    83                 if (numSequences < 1) { 
    84                         throw new InvalidParameterException( 
    85                                         "number of sequences must be at least 1 but is " 
    86                                                         + numSequences); 
    87                 } 
    88                 if (length < 1) { 
    89                         throw new InvalidParameterException( 
    90                                         "length of test cases must be at least 1 but is " + length); 
    91                 } 
    92                 this.numSequences = numSequences; 
    93                 this.length = length; 
    94                 this.maxLengthAll = maxLengthAll; 
    95                 this.validEnd = validEnd; 
    96         } 
    97  
    98         /** 
    99          * <p> 
    100          * Generates a test suite with a hybrid approach that is a mixture of random 
    101          * walks and drawing from all possible sequences 
    102          * </p> 
    103          *  
    104          * @param model 
    105          *            model used to determine the probability of each possible 
    106          *            sequence 
    107          * @return the test suite 
    108          */ 
    109         public Collection<List<Event>> generateTestSuite( 
    110                         IStochasticProcess model) { 
    111                 if (model == null) { 
    112                         throw new InvalidParameterException("model must not be null!"); 
    113                 } 
    114                  
    115                 Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
    116  
    117                 List<List<Event>> seqsTmp = new ArrayList<List<Event>>( 
    118                                 model.generateSequences(maxLengthAll + 1, true)); 
    119  
    120                 Console.traceln("" + seqsTmp.size() + " of length " + maxLengthAll 
    121                                 + " possible"); 
    122                 List<Double> probabilities = new ArrayList<Double>(seqsTmp.size()); 
    123                 double probSum = 0.0; 
    124                 for (List<Event> sequence : seqsTmp) { 
    125                         double prob = model.getProbability(sequence); 
    126                         probabilities.add(prob); 
    127                         probSum += prob; 
    128                 } 
    129  
    130                 Random r = new Random(); 
    131                 int j = 0; 
    132                 while (sequences.size() < numSequences && j <= numSequences * 100) { 
    133                         j++; 
    134                         double randVal = r.nextDouble() * probSum; 
    135                         double sum = 0.0d; 
    136                         int index = -1; 
    137                         while (sum < randVal) { 
    138                                 index++; 
    139                                 double currentProb = probabilities.get(index); 
    140                                 sum += currentProb; 
    141                         } 
    142                         List<Event> seqTmp = seqsTmp.get(index); 
    143                         if (!Event.ENDEVENT.equals(seqTmp.get(seqTmp.size() - 1))) { 
    144                                 List<Event> sequence; 
    145                                 if (validEnd) { 
    146                                         sequence = finishSequence(seqTmp, model, length + 2, 
    147                                                         validEnd); 
    148                                         if( sequence!= null && sequence.size()!=length+2 ) { 
    149                                                 sequence = null; 
    150                                         } 
    151                                 } else { 
    152                                         sequence = finishSequence(seqTmp, model, length + 1, 
    153                                                         validEnd); 
    154                                         if( sequence!= null && sequence.size()!=length+1 ) { 
    155                                                 sequence = null; 
    156                                         } 
    157                                 } 
    158                                 if( sequence!=null ) { 
    159                                         sequences.add(sequence); 
    160                                 } 
    161                         } 
    162                 } 
    163                  
    164                 return sequences; 
    165         } 
    166  
    167         /** 
    168          * <p> 
    169          * Finishes a sequence with a random walk. 
    170          * </p> 
    171          *  
    172          * @param sequence 
    173          *            sequence to be finished 
    174          * @param model 
    175          *            model used for the random walk 
    176          * @param length 
    177          *            desired length of the sequence 
    178          * @param validEnd 
    179          *            if the sequence should end in {@link Event#ENDEVENT}. 
    180          * @return finished sequence of the desired length 
    181          */ 
    182         private List<Event> finishSequence( 
    183                         List<Event> sequence, IStochasticProcess model, 
    184                         int length, boolean validEnd) { 
    185                 Random r = new Random(); 
    186                 boolean endFound = false; 
    187                 List<Event> sequenceCopy = new LinkedList<Event>(sequence); 
    188                 final int maxIter = 30000; 
    189                 int iter = 0; 
    190                 while (!endFound && iter < maxIter) { 
    191                         iter++; 
    192                         sequenceCopy = new LinkedList<Event>(sequence); 
    193                         while (!endFound && sequenceCopy.size() <= length) { 
    194                                 double randVal = r.nextDouble(); 
    195                                 double probSum = 0.0; 
    196                                 for (Event symbol : model.getEvents()) { 
    197                                         probSum += model.getProbability(sequenceCopy, symbol); 
    198                                         if (probSum >= randVal) { 
    199                                                 if (!(Event.STARTEVENT.equals(symbol) || (!validEnd && Event.ENDEVENT 
    200                                                                 .equals(symbol)))) { 
    201                                                         // only add the symbol the sequence if it is not 
    202                                                         // START 
    203                                                         // or END 
    204                                                         sequenceCopy.add(symbol); 
    205                                                 } 
    206                                                 endFound = Event.ENDEVENT.equals(symbol) 
    207                                                                 || (!validEnd && sequenceCopy.size() == length); 
    208                                                 break; 
    209                                         } 
    210                                 } 
    211                         } 
    212                 } 
    213                 if (iter == maxIter) { 
    214                         return null; 
    215                 } 
    216                 return sequenceCopy; 
    217         } 
     27    /** 
     28     * <p> 
     29     * Number of sequences in the test suite. 
     30     * </p> 
     31     */ 
     32    private final int numSequences; 
     33 
     34    /** 
     35     * <p> 
     36     * Length of a test sequence. 
     37     * </p> 
     38     */ 
     39    private final int length; 
     40 
     41    /** 
     42     * <p> 
     43     * Maximal length where it is possible to generate all sequences and draw from them. 
     44     * </p> 
     45     */ 
     46    private final int maxLengthAll; 
     47 
     48    /** 
     49     * <p> 
     50     * In case this member is true, only test cases that end in the global end event 
     51     * {@link Event#ENDEVENT} are generated. If it is false, the end event can be any event. 
     52     * </p> 
     53     */ 
     54    private final boolean validEnd; 
     55 
     56    /** 
     57     * <p> 
     58     * Constructor. Creates a new HybridGenerator and ensures the validity of the parameters: 
     59     * <ul> 
     60     * <li>numSequences must at least be 1 
     61     * <li>length must be at least 1 
     62     * </ul> 
     63     * If one of these conditions is violated an {@link InvalidParameterException} is thrown. 
     64     * </p> 
     65     *  
     66     * @param numSequences 
     67     *            number of sequences desired for the test suite 
     68     * @param length 
     69     *            length of a test sequence 
     70     * @param maxLengthAll 
     71     *            maximal length where it is possible to generate all sequences and draw from them 
     72     * @param validEnd 
     73     *            defines if test cases have to end with the global end event {@link Event#ENDEVENT} 
     74     *            (see {@link #validEnd}) 
     75     */ 
     76    public HybridGenerator(int numSequences, int length, int maxLengthAll, boolean validEnd) { 
     77        // check validity of the parameters 
     78        if (numSequences < 1) { 
     79            throw new InvalidParameterException("number of sequences must be at least 1 but is " + 
     80                numSequences); 
     81        } 
     82        if (length < 1) { 
     83            throw new InvalidParameterException("length of test cases must be at least 1 but is " + 
     84                length); 
     85        } 
     86        this.numSequences = numSequences; 
     87        this.length = length; 
     88        this.maxLengthAll = maxLengthAll; 
     89        this.validEnd = validEnd; 
     90    } 
     91 
     92    /** 
     93     * <p> 
     94     * Generates a test suite with a hybrid approach that is a mixture of random walks and drawing 
     95     * from all possible sequences 
     96     * </p> 
     97     *  
     98     * @param model 
     99     *            model used to determine the probability of each possible sequence 
     100     * @return the test suite 
     101     */ 
     102    public Collection<List<Event>> generateTestSuite(IStochasticProcess model) { 
     103        if (model == null) { 
     104            throw new InvalidParameterException("model must not be null!"); 
     105        } 
     106 
     107        Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
     108 
     109        List<List<Event>> seqsTmp = 
     110            new ArrayList<List<Event>>(model.generateSequences(maxLengthAll + 1, true)); 
     111 
     112        Console.traceln("" + seqsTmp.size() + " of length " + maxLengthAll + " possible"); 
     113        List<Double> probabilities = new ArrayList<Double>(seqsTmp.size()); 
     114        double probSum = 0.0; 
     115        for (List<Event> sequence : seqsTmp) { 
     116            double prob = model.getProbability(sequence); 
     117            probabilities.add(prob); 
     118            probSum += prob; 
     119        } 
     120 
     121        Random r = new Random(); 
     122        int j = 0; 
     123        while (sequences.size() < numSequences && j <= numSequences * 100) { 
     124            j++; 
     125            double randVal = r.nextDouble() * probSum; 
     126            double sum = 0.0d; 
     127            int index = -1; 
     128            while (sum < randVal) { 
     129                index++; 
     130                double currentProb = probabilities.get(index); 
     131                sum += currentProb; 
     132            } 
     133            List<Event> seqTmp = seqsTmp.get(index); 
     134            if (!Event.ENDEVENT.equals(seqTmp.get(seqTmp.size() - 1))) { 
     135                List<Event> sequence; 
     136                if (validEnd) { 
     137                    sequence = finishSequence(seqTmp, model, length + 2, validEnd); 
     138                    if (sequence != null && sequence.size() != length + 2) { 
     139                        sequence = null; 
     140                    } 
     141                } 
     142                else { 
     143                    sequence = finishSequence(seqTmp, model, length + 1, validEnd); 
     144                    if (sequence != null && sequence.size() != length + 1) { 
     145                        sequence = null; 
     146                    } 
     147                } 
     148                if (sequence != null) { 
     149                    sequences.add(sequence); 
     150                } 
     151            } 
     152        } 
     153 
     154        return sequences; 
     155    } 
     156 
     157    /** 
     158     * <p> 
     159     * Finishes a sequence with a random walk. 
     160     * </p> 
     161     *  
     162     * @param sequence 
     163     *            sequence to be finished 
     164     * @param model 
     165     *            model used for the random walk 
     166     * @param length 
     167     *            desired length of the sequence 
     168     * @param validEnd 
     169     *            if the sequence should end in {@link Event#ENDEVENT}. 
     170     * @return finished sequence of the desired length 
     171     */ 
     172    private List<Event> finishSequence(List<Event> sequence, 
     173                                       IStochasticProcess model, 
     174                                       int length, 
     175                                       boolean validEnd) 
     176    { 
     177        Random r = new Random(); 
     178        boolean endFound = false; 
     179        List<Event> sequenceCopy = new LinkedList<Event>(sequence); 
     180        final int maxIter = 30000; 
     181        int iter = 0; 
     182        while (!endFound && iter < maxIter) { 
     183            iter++; 
     184            sequenceCopy = new LinkedList<Event>(sequence); 
     185            while (!endFound && sequenceCopy.size() <= length) { 
     186                double randVal = r.nextDouble(); 
     187                double probSum = 0.0; 
     188                for (Event symbol : model.getEvents()) { 
     189                    probSum += model.getProbability(sequenceCopy, symbol); 
     190                    if (probSum >= randVal) { 
     191                        if (!(Event.STARTEVENT.equals(symbol) || (!validEnd && Event.ENDEVENT 
     192                            .equals(symbol)))) 
     193                        { 
     194                            // only add the symbol the sequence if it is not 
     195                            // START 
     196                            // or END 
     197                            sequenceCopy.add(symbol); 
     198                        } 
     199                        endFound = 
     200                            Event.ENDEVENT.equals(symbol) || 
     201                                (!validEnd && sequenceCopy.size() == length); 
     202                        break; 
     203                    } 
     204                } 
     205            } 
     206        } 
     207        if (iter == maxIter) { 
     208            return null; 
     209        } 
     210        return sequenceCopy; 
     211    } 
    218212 
    219213} 

  • trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.testgeneration; 
    23 
    … …  
    2021public class RandomWalkGenerator { 
    2122 
    22         /** 
    23         * <p> 
    24         * Number of sequences in the test suite. 
    25         * </p> 
    26         */ 
    27         private final int numSequences; 
     23    /** 
     24    * <p> 
     25    * Number of sequences in the test suite. 
     26    * </p> 
     27    */ 
     28    private final int numSequences; 
    2829 
    29         /** 
    30         * <p> 
    31         * Minimal length of a test sequence. 
    32         * </p> 
    33         */ 
    34         private final int minLength; 
     30    /** 
     31    * <p> 
     32    * Minimal length of a test sequence. 
     33    * </p> 
     34    */ 
     35    private final int minLength; 
    3536 
    36         /** 
    37         * <p> 
    38         * Maximal length of a test sequence. 
    39         * </p> 
    40         */ 
    41         private final int maxLength; 
     37    /** 
     38    * <p> 
     39    * Maximal length of a test sequence. 
     40    * </p> 
     41    */ 
     42    private final int maxLength; 
    4243 
    43         /** 
    44          * <p> 
    45          * In case this member is true, only test cases that end in the global end 
    46          * event {@link Event#ENDEVENT} are generated. If it is false, the end event 
    47          * can be any event. 
    48          * </p> 
    49          */ 
    50         private final boolean validEnd; 
     44    /** 
     45     * <p> 
     46     * In case this member is true, only test cases that end in the global end event 
     47     * {@link Event#ENDEVENT} are generated. If it is false, the end event can be any event. 
     48     * </p> 
     49     */ 
     50    private final boolean validEnd; 
    5151 
    52         /** 
    53          * <p> 
    54          * Maximal number of random walks performed before aborting the test case 
    55          * generation and returning a test suite with less than 
    56          * {@link #numSequences} test cases. This can happen if too many generated 
    57          * random walks have to be discarded because their length is not between 
    58          * {@link #minLength} and {@link #maxLength}. 
    59          * </p> 
    60          */ 
    61         private final long maxIter; 
     52    /** 
     53     * <p> 
     54     * Maximal number of random walks performed before aborting the test case generation and 
     55     * returning a test suite with less than {@link #numSequences} test cases. This can happen if 
     56     * too many generated random walks have to be discarded because their length is not between 
     57     * {@link #minLength} and {@link #maxLength}. 
     58     * </p> 
     59     */ 
     60    private final long maxIter; 
    6261 
    63         /** 
    64         * <p> 
    65         * Actual number of random walks performed to generate the test suite. 
    66         * </p> 
    67         */ 
    68         private long actualIter = -1; 
     62    /** 
     63    * <p> 
     64    * Actual number of random walks performed to generate the test suite. 
     65    * </p> 
     66    */ 
     67    private long actualIter = -1; 
    6968 
    70         /** 
    71          * <p> 
    72          * Constructor. Creates a new RandomWalkGenerator and ensures the validity 
    73          * of the parameters: 
    74          * <ul> 
    75          * <li>numSequences must at least be 1 
    76          * <li>maxLength must at least be 1 
    77          * <li>minLength must be less than or equal to maxLength 
    78          * <li>maxIter must be greater than or equal to numSequences 
    79          * </ul> 
    80          * If one of these conditions is violated an 
    81          * {@link InvalidParameterException} is thrown. 
    82          * </p> 
    83          *  
    84          * @param numSequences 
    85          *            number of sequences desired for the test suite 
    86          * @param minLength 
    87          *            minimal length of a test sequence 
    88          * @param maxLength 
    89          *            maximal length of a test sequence 
    90          * @param validEnd 
    91          *            defines if test cases have to end with the global end event 
    92          *            {@link Event#ENDEVENT} (see {@link #validEnd}) 
    93          * @param maxIter 
    94          *            maximal number of random walks before aborting the test case 
    95          *            generation (see {@link #maxIter}) 
    96          */ 
    97         public RandomWalkGenerator(int numSequences, int minLength, int maxLength, 
    98                         boolean validEnd, long maxIter) { 
    99                 // check validity of the parameters 
    100                 if (numSequences < 1) { 
    101                         throw new InvalidParameterException( 
    102                                         "number of sequences must be at least 1 but is " 
    103                                                         + numSequences); 
    104                 } 
    105                 if (maxLength < 1) { 
    106                         throw new InvalidParameterException( 
    107                                         "maximal allowed length of test cases must be at least 1 but is " 
    108                                                         + maxLength); 
    109                 } 
    110                 if (minLength > maxLength) { 
    111                         throw new InvalidParameterException( 
    112                                         "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " 
    113                                                         + minLength + " ; max length: " + maxLength + ")"); 
    114                 } 
    115                 if (maxIter < numSequences) { 
    116                         throw new InvalidParameterException( 
    117                                         "maximal number of iterations must greater than or equal to the number of sequences (number of sequences: " 
    118                                                         + numSequences 
    119                                                         + " ; max iterations: " 
    120                                                         + maxIter 
    121                                                         + ")"); 
    122                 } 
    123                 this.numSequences = numSequences; 
    124                 this.minLength = minLength; 
    125                 this.maxLength = maxLength; 
    126                 this.validEnd = validEnd; 
    127                 this.maxIter = maxIter; 
    128         } 
     69    /** 
     70     * <p> 
     71     * Constructor. Creates a new RandomWalkGenerator and ensures the validity of the parameters: 
     72     * <ul> 
     73     * <li>numSequences must at least be 1 
     74     * <li>maxLength must at least be 1 
     75     * <li>minLength must be less than or equal to maxLength 
     76     * <li>maxIter must be greater than or equal to numSequences 
     77     * </ul> 
     78     * If one of these conditions is violated an {@link InvalidParameterException} is thrown. 
     79     * </p> 
     80     *  
     81     * @param numSequences 
     82     *            number of sequences desired for the test suite 
     83     * @param minLength 
     84     *            minimal length of a test sequence 
     85     * @param maxLength 
     86     *            maximal length of a test sequence 
     87     * @param validEnd 
     88     *            defines if test cases have to end with the global end event {@link Event#ENDEVENT} 
     89     *            (see {@link #validEnd}) 
     90     * @param maxIter 
     91     *            maximal number of random walks before aborting the test case generation (see 
     92     *            {@link #maxIter}) 
     93     */ 
     94    public RandomWalkGenerator(int numSequences, 
     95                               int minLength, 
     96                               int maxLength, 
     97                               boolean validEnd, 
     98                               long maxIter) 
     99    { 
     100        // check validity of the parameters 
     101        if (numSequences < 1) { 
     102            throw new InvalidParameterException("number of sequences must be at least 1 but is " + 
     103                numSequences); 
     104        } 
     105        if (maxLength < 1) { 
     106            throw new InvalidParameterException( 
     107                                                "maximal allowed length of test cases must be at least 1 but is " + 
     108                                                    maxLength); 
     109        } 
     110        if (minLength > maxLength) { 
     111            throw new InvalidParameterException( 
     112                                                "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " + 
     113                                                    minLength + " ; max length: " + maxLength + ")"); 
     114        } 
     115        if (maxIter < numSequences) { 
     116            throw new InvalidParameterException( 
     117                                                "maximal number of iterations must greater than or equal to the number of sequences (number of sequences: " + 
     118                                                    numSequences + 
     119                                                    " ; max iterations: " + 
     120                                                    maxIter + 
     121                                                    ")"); 
     122        } 
     123        this.numSequences = numSequences; 
     124        this.minLength = minLength; 
     125        this.maxLength = maxLength; 
     126        this.validEnd = validEnd; 
     127        this.maxIter = maxIter; 
     128    } 
    129129 
    130         /** 
    131          * <p> 
    132          * Generates a test suite by repeatedly randomly walking a stochastic 
    133          * process. 
    134          * </p> 
    135          *  
    136          * @param model 
    137          *            stochastic process which performs the random walks 
    138          * @return the test suite 
    139          */ 
    140         public Collection<List<Event>> generateTestSuite( 
    141                         IStochasticProcess model) { 
    142                 if (model == null) { 
    143                         throw new InvalidParameterException("model must not be null!"); 
    144                 } 
     130    /** 
     131     * <p> 
     132     * Generates a test suite by repeatedly randomly walking a stochastic process. 
     133     * </p> 
     134     *  
     135     * @param model 
     136     *            stochastic process which performs the random walks 
     137     * @return the test suite 
     138     */ 
     139    public Collection<List<Event>> generateTestSuite(IStochasticProcess model) { 
     140        if (model == null) { 
     141            throw new InvalidParameterException("model must not be null!"); 
     142        } 
    145143 
    146                 Set<List<Event>> sequences = new HashSet<List<Event>>( 
    147                                 numSequences); 
    148                 actualIter = 0; 
    149                 while (sequences.size() < numSequences && actualIter < maxIter) { 
    150                         List<Event> generatedSequence = model.randomSequence( 
    151                                         maxLength, validEnd); 
    152                         if (generatedSequence.size() >= minLength 
    153                                         && generatedSequence.size() <= maxLength) { 
    154                                 ((List<Event>) generatedSequence).add(0, Event.STARTEVENT); 
    155                                 if (validEnd) { 
    156                                         ((List<Event>) generatedSequence).add(Event.ENDEVENT); 
    157                                 } 
    158                                 sequences.add(generatedSequence); 
    159                         } 
    160                         actualIter++; 
    161                 } 
     144        Set<List<Event>> sequences = new HashSet<List<Event>>(numSequences); 
     145        actualIter = 0; 
     146        while (sequences.size() < numSequences && actualIter < maxIter) { 
     147            List<Event> generatedSequence = model.randomSequence(maxLength, validEnd); 
     148            if (generatedSequence.size() >= minLength && generatedSequence.size() <= maxLength) { 
     149                ((List<Event>) generatedSequence).add(0, Event.STARTEVENT); 
     150                if (validEnd) { 
     151                    ((List<Event>) generatedSequence).add(Event.ENDEVENT); 
     152                } 
     153                sequences.add(generatedSequence); 
     154            } 
     155            actualIter++; 
     156        } 
    162157 
    163                 return sequences; 
    164         } 
     158        return sequences; 
     159    } 
    165160 
    166         /** 
    167          * <p> 
    168          * Returns the actual number of random walks performed during the last call 
    169          * of {@link #generateTestSuite(IStochasticProcess)} or -1 if 
    170          * {@link #generateTestSuite(IStochasticProcess)} has not been called yet. 
    171          * </p> 
    172          *  
    173          * @return actual number of random walks or -1 if 
    174          *         {@link #generateTestSuite(IStochasticProcess)} has not been 
    175          *         called 
    176          */ 
    177         public long getActualIter() { 
    178                 return actualIter; 
    179         } 
     161    /** 
     162     * <p> 
     163     * Returns the actual number of random walks performed during the last call of 
     164     * {@link #generateTestSuite(IStochasticProcess)} or -1 if 
     165     * {@link #generateTestSuite(IStochasticProcess)} has not been called yet. 
     166     * </p> 
     167     *  
     168     * @return actual number of random walks or -1 if {@link #generateTestSuite(IStochasticProcess)} 
     169     *         has not been called 
     170     */ 
     171    public long getActualIter() { 
     172        return actualIter; 
     173    } 
    180174} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1112/** 
    1213 * <p> 
    13  * Implements a Deterministic Finite Automata (DFA) capable of random session 
    14  * generation. It is a special case of a first-order Markov model, where the 
    15  * transition probability is equally high for all following states. 
     14 * Implements a Deterministic Finite Automata (DFA) capable of random session generation. It is a 
     15 * special case of a first-order Markov model, where the transition probability is equally high for 
     16 * all following states. 
    1617 * </p> 
    1718 *  
    … …  
    2122public class DeterministicFiniteAutomaton extends FirstOrderMarkovModel { 
    2223 
    23         /** 
    24         * <p> 
    25         * Id for object serialization. 
    26         * </p> 
    27         */ 
    28         private static final long serialVersionUID = 1L; 
     24    /** 
     25    * <p> 
     26    * Id for object serialization. 
     27    * </p> 
     28    */ 
     29    private static final long serialVersionUID = 1L; 
    2930 
    30         /** 
    31          * <p> 
    32          * Constructor. Creates a new DeterministicFiniteAutomaton. 
    33          * </p> 
    34          *  
    35          * @param r 
    36          *            random number generator used by probabilistic methods of the 
    37          *            class 
    38          */ 
    39         public DeterministicFiniteAutomaton(Random r) { 
    40                 super(r); 
    41         } 
     31    /** 
     32     * <p> 
     33     * Constructor. Creates a new DeterministicFiniteAutomaton. 
     34     * </p> 
     35     *  
     36     * @param r 
     37     *            random number generator used by probabilistic methods of the class 
     38     */ 
     39    public DeterministicFiniteAutomaton(Random r) { 
     40        super(r); 
     41    } 
    4242 
    43         /** 
    44          * <p> 
    45          * Calculates the proability of the next state. Each of the following states 
    46          * in the automaton is equally probable. 
    47          * </p> 
    48          *  
    49          * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
    50          *      de.ugoe.cs.quest.eventcore.Event) 
    51          */ 
    52         @Override 
    53         public double getProbability(List<Event> context, 
    54                         Event symbol) { 
    55                 if( context==null ) { 
    56                         throw new InvalidParameterException("context must not be null"); 
    57                 } 
    58                 if( symbol==null ) { 
    59                         throw new InvalidParameterException("symbol must not be null"); 
    60                 } 
    61                 double result = 0.0d; 
     43    /** 
     44     * <p> 
     45     * Calculates the proability of the next state. Each of the following states in the automaton is 
     46     * equally probable. 
     47     * </p> 
     48     *  
     49     * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
     50     *      de.ugoe.cs.quest.eventcore.Event) 
     51     */ 
     52    @Override 
     53    public double getProbability(List<Event> context, Event symbol) { 
     54        if (context == null) { 
     55            throw new InvalidParameterException("context must not be null"); 
     56        } 
     57        if (symbol == null) { 
     58            throw new InvalidParameterException("symbol must not be null"); 
     59        } 
     60        double result = 0.0d; 
    6261 
    63                 List<Event> contextCopy; 
    64                 if (context.size() >= trieOrder) { 
    65                         contextCopy = new LinkedList<Event>(context.subList( 
    66                                         context.size() - trieOrder + 1, context.size())); 
    67                 } else { 
    68                         contextCopy = new LinkedList<Event>(context); 
    69                 } 
     62        List<Event> contextCopy; 
     63        if (context.size() >= trieOrder) { 
     64            contextCopy = 
     65                new LinkedList<Event>(context.subList(context.size() - trieOrder + 1, 
     66                                                      context.size())); 
     67        } 
     68        else { 
     69            contextCopy = new LinkedList<Event>(context); 
     70        } 
    7071 
    71                 Collection<Event> followers = trie.getFollowingSymbols(contextCopy); 
     72        Collection<Event> followers = trie.getFollowingSymbols(contextCopy); 
    7273 
    73                 if (followers.size() != 0 && followers.contains(symbol)) { 
    74                         result = 1.0d / followers.size(); 
    75                 } 
     74        if (followers.size() != 0 && followers.contains(symbol)) { 
     75            result = 1.0d / followers.size(); 
     76        } 
    7677 
    77                 return result; 
    78         } 
     78        return result; 
     79    } 
    7980 
    8081} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java

    r553 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1819/** 
    1920 * <p> 
    20  * Implements first-order Markov models. The implementation is based on 
    21  * {@link HighOrderMarkovModel} and restricts the Markov order to 1. In 
    22  * comparison to {@link HighOrderMarkovModel}, more calculations are possible 
    23  * with first-order models, e.g., the calculation of the entropy ( 
     21 * Implements first-order Markov models. The implementation is based on {@link HighOrderMarkovModel} 
     22 * and restricts the Markov order to 1. In comparison to {@link HighOrderMarkovModel}, more 
     23 * calculations are possible with first-order models, e.g., the calculation of the entropy ( 
    2424 * {@link #calcEntropy()}). 
    2525 * </p> 
    … …  
    2828 * @version 1.0 
    2929 */ 
    30 public class FirstOrderMarkovModel extends HighOrderMarkovModel implements 
    31                 IDotCompatible { 
    32  
    33         /** 
    34          * <p> 
    35          * Id for object serialization. 
    36          * </p> 
    37          */ 
    38         private static final long serialVersionUID = 1L; 
    39  
    40         /** 
    41          * <p> 
    42          * Maximum number of iterations when calculating the stationary distribution 
    43          * as the limit of multiplying the transmission matrix with itself. 
    44          * </p> 
    45          */ 
    46         final static int MAX_STATDIST_ITERATIONS = 1000; 
    47  
    48         /** 
    49          * <p> 
    50          * Constructor. Creates a new FirstOrderMarkovModel. 
    51          * </p> 
    52          *  
    53          * @param r 
    54          *            random number generator used by probabilistic methods of the 
    55          *            class 
    56          */ 
    57         public FirstOrderMarkovModel(Random r) { 
    58                 super(1, r); 
    59         } 
    60  
    61         /** 
    62          * <p> 
    63          * Generates the transmission matrix of the Markov model. 
    64          * </p> 
    65          *  
    66          * @return transmission matrix 
    67          */ 
    68         private Matrix getTransmissionMatrix() { 
    69                 List<Event> knownSymbols = new ArrayList<Event>( 
    70                                 trie.getKnownSymbols()); 
    71                 int numStates = knownSymbols.size(); 
    72                 Matrix transmissionMatrix = new Matrix(numStates, numStates); 
    73  
    74                 for (int i = 0; i < numStates; i++) { 
    75                         Event currentSymbol = knownSymbols.get(i); 
    76                         List<Event> context = new ArrayList<Event>(); 
    77                         context.add(currentSymbol); 
    78                         for (int j = 0; j < numStates; j++) { 
    79                                 Event follower = knownSymbols.get(j); 
    80                                 double prob = getProbability(context, follower); 
    81                                 transmissionMatrix.set(i, j, prob); 
    82                         } 
    83                 } 
    84                 return transmissionMatrix; 
    85         } 
    86  
    87         /** 
    88          * <p> 
    89          * Calculates the entropy of the model. To make it possible that the model 
    90          * is stationary, a transition from {@link Event#ENDEVENT} to 
    91          * {@link Event#STARTEVENT} is added. 
    92          * </p> 
    93          *  
    94          * @return entropy of the model or NaN if it could not be calculated 
    95          */ 
    96         public double calcEntropy() { 
    97                 Matrix transmissionMatrix = getTransmissionMatrix(); 
    98                 List<Event> knownSymbols = new ArrayList<Event>( 
    99                                 trie.getKnownSymbols()); 
    100                 int numStates = knownSymbols.size(); 
    101  
    102                 List<Integer> startIndexList = new LinkedList<Integer>(); 
    103                 List<Integer> endIndexList = new LinkedList<Integer>(); 
    104                 for( int i=0 ; i<knownSymbols.size() ; i++ ) { 
    105                         String id = knownSymbols.get(i).getId(); 
    106                         if( id.equals(Event.STARTEVENT.getId()) || id.contains(Event.STARTEVENT.getId()+"-=-") ) { 
    107                                 startIndexList.add(i); 
    108                         } 
    109                         if( id.equals(Event.ENDEVENT.getId()) || id.contains("-=-"+Event.ENDEVENT.getId()) ) { 
    110                                 endIndexList.add(i); 
    111                         } 
    112                 } 
    113                  
    114                 if (startIndexList.isEmpty()) {  
    115                         Console.printerrln("Error calculating entropy. Initial state of markov chain not found."); 
    116                         return Double.NaN; 
    117                 } 
    118                 if (endIndexList.isEmpty()) { 
    119                         Console.printerrln("Error calculating entropy. End state of markov chain not found."); 
    120                         return Double.NaN; 
    121                 } 
    122                 for( Integer i : endIndexList ) { 
    123                         for(Integer j : startIndexList ) { 
    124                                 transmissionMatrix.set(i, j, 1); 
    125                         } 
    126                 } 
    127  
    128                 // Calculate stationary distribution by raising the power of the 
    129                 // transmission matrix. 
    130                 // The rank of the matrix should fall to 1 and each two should be the 
    131                 // vector of the stationory distribution. 
    132                 int iter = 0; 
    133                 int rank = transmissionMatrix.rank(); 
    134                 Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone(); 
    135                 while (iter < MAX_STATDIST_ITERATIONS && rank > 1) { 
    136                         stationaryMatrix = stationaryMatrix.times(stationaryMatrix); 
    137                         rank = stationaryMatrix.rank(); 
    138                         iter++; 
    139                 } 
    140  
    141                 if (rank != 1) { 
    142                         Console.traceln("rank: " + rank); 
    143                         Console.printerrln("Unable to calculate stationary distribution."); 
    144                         return Double.NaN; 
    145                 } 
    146  
    147                 double entropy = 0.0; 
    148                 for (int i = 0; i < numStates; i++) { 
    149                         for (int j = 0; j < numStates; j++) { 
    150                                 if (transmissionMatrix.get(i, j) != 0 && transmissionMatrix.get(i, j)!=1) { 
    151                                         double tmp = stationaryMatrix.get(0, i); 
    152                                         tmp *= transmissionMatrix.get(i, j); 
    153                                         tmp *= Math.log(transmissionMatrix.get(i, j)) / Math.log(2); 
    154                                         entropy -= tmp; 
    155                                 } 
    156                         } 
    157                 } 
    158                 return entropy; 
    159         } 
    160  
    161         /** 
    162          * <p> 
    163          * The dot represenation of {@link FirstOrderMarkovModel}s is its graph 
    164          * representation with the states as nodes and directed edges weighted with 
    165          * transition probabilities. 
    166          * </p> 
    167          *  
    168          * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() 
    169          */ 
    170         @Override 
    171         public String getDotRepresentation() { 
    172                 StringBuilder stringBuilder = new StringBuilder(); 
    173                 stringBuilder.append("digraph model {" + StringTools.ENDLINE); 
    174  
    175                 List<Event> knownSymbols = new ArrayList<Event>( 
    176                                 trie.getKnownSymbols()); 
    177                 for (Event symbol : knownSymbols) { 
    178                         final String thisSaneId = symbol.getId().replace("\"", "\\\"") 
    179                                         .replaceAll("[\r\n]", ""); 
    180                         stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " [label=\"" 
    181                                         + thisSaneId + "\"];" + StringTools.ENDLINE); 
    182                         List<Event> context = new ArrayList<Event>(); 
    183                         context.add(symbol); 
    184                         Collection<Event> followers = trie.getFollowingSymbols(context); 
    185                         for (Event follower : followers) { 
    186                                 stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " -> " 
    187                                                 + knownSymbols.indexOf(follower) + " "); 
    188                                 stringBuilder.append("[label=\"" 
    189                                                 + getProbability(context, follower) + "\"];" 
    190                                                 + StringTools.ENDLINE); 
    191                         } 
    192                 } 
    193                 stringBuilder.append('}' + StringTools.ENDLINE); 
    194                 return stringBuilder.toString(); 
    195         } 
    196  
    197         /** 
    198          * <p> 
    199          * Returns a {@link Graph} representation of the model with the states as 
    200          * nodes and directed edges weighted with transition probabilities. 
    201          * </p> 
    202          *  
    203          * @return {@link Graph} of the model 
    204          */ 
    205         public Graph<String, MarkovEdge> getGraph() { 
    206                 Graph<String, MarkovEdge> graph = new SparseMultigraph<String, MarkovEdge>(); 
    207  
    208                 List<Event> knownSymbols = new ArrayList<Event>( 
    209                                 trie.getKnownSymbols()); 
    210  
    211                 for (Event symbol : knownSymbols) { 
    212                         String from = symbol.getId(); 
    213                         List<Event> context = new ArrayList<Event>(); 
    214                         context.add(symbol); 
    215  
    216                         Collection<Event> followers = trie.getFollowingSymbols(context); 
    217  
    218                         for (Event follower : followers) { 
    219                                 String to = follower.getId(); 
    220                                 MarkovEdge prob = new MarkovEdge(getProbability(context, 
    221                                                 follower)); 
    222                                 graph.addEdge(prob, from, to, EdgeType.DIRECTED); 
    223                         } 
    224                 } 
    225                 return graph; 
    226         } 
    227  
    228         /** 
    229          * Inner class used for the {@link Graph} representation of the model. 
    230          *  
    231          * @author Steffen Herbold 
    232          * @version 1.0 
    233          */ 
    234         static public class MarkovEdge { 
    235                 /** 
    236                  * <p> 
    237                  * Weight of the edge, i.e., its transition probability. 
    238                  * </p> 
    239                  */ 
    240                 double weight; 
    241  
    242                 /** 
    243                  * <p> 
    244                  * Constructor. Creates a new MarkovEdge. 
    245                  * </p> 
    246                  *  
    247                  * @param weight 
    248                  *            weight of the edge, i.e., its transition probability 
    249                  */ 
    250                 MarkovEdge(double weight) { 
    251                         this.weight = weight; 
    252                 } 
    253  
    254                 /** 
    255                  * <p> 
    256                  * The weight of the edge as {@link String}. 
    257                  * </p> 
    258                  */ 
    259                 public String toString() { 
    260                         return "" + weight; 
    261                 } 
    262         } 
     30public class FirstOrderMarkovModel extends HighOrderMarkovModel implements IDotCompatible { 
     31 
     32    /** 
     33     * <p> 
     34     * Id for object serialization. 
     35     * </p> 
     36     */ 
     37    private static final long serialVersionUID = 1L; 
     38 
     39    /** 
     40     * <p> 
     41     * Maximum number of iterations when calculating the stationary distribution as the limit of 
     42     * multiplying the transmission matrix with itself. 
     43     * </p> 
     44     */ 
     45    final static int MAX_STATDIST_ITERATIONS = 1000; 
     46 
     47    /** 
     48     * <p> 
     49     * Constructor. Creates a new FirstOrderMarkovModel. 
     50     * </p> 
     51     *  
     52     * @param r 
     53     *            random number generator used by probabilistic methods of the class 
     54     */ 
     55    public FirstOrderMarkovModel(Random r) { 
     56        super(1, r); 
     57    } 
     58 
     59    /** 
     60     * <p> 
     61     * Generates the transmission matrix of the Markov model. 
     62     * </p> 
     63     *  
     64     * @return transmission matrix 
     65     */ 
     66    private Matrix getTransmissionMatrix() { 
     67        List<Event> knownSymbols = new ArrayList<Event>(trie.getKnownSymbols()); 
     68        int numStates = knownSymbols.size(); 
     69        Matrix transmissionMatrix = new Matrix(numStates, numStates); 
     70 
     71        for (int i = 0; i < numStates; i++) { 
     72            Event currentSymbol = knownSymbols.get(i); 
     73            List<Event> context = new ArrayList<Event>(); 
     74            context.add(currentSymbol); 
     75            for (int j = 0; j < numStates; j++) { 
     76                Event follower = knownSymbols.get(j); 
     77                double prob = getProbability(context, follower); 
     78                transmissionMatrix.set(i, j, prob); 
     79            } 
     80        } 
     81        return transmissionMatrix; 
     82    } 
     83 
     84    /** 
     85     * <p> 
     86     * Calculates the entropy of the model. To make it possible that the model is stationary, a 
     87     * transition from {@link Event#ENDEVENT} to {@link Event#STARTEVENT} is added. 
     88     * </p> 
     89     *  
     90     * @return entropy of the model or NaN if it could not be calculated 
     91     */ 
     92    public double calcEntropy() { 
     93        Matrix transmissionMatrix = getTransmissionMatrix(); 
     94        List<Event> knownSymbols = new ArrayList<Event>(trie.getKnownSymbols()); 
     95        int numStates = knownSymbols.size(); 
     96 
     97        List<Integer> startIndexList = new LinkedList<Integer>(); 
     98        List<Integer> endIndexList = new LinkedList<Integer>(); 
     99        for (int i = 0; i < knownSymbols.size(); i++) { 
     100            String id = knownSymbols.get(i).getId(); 
     101            if (id.equals(Event.STARTEVENT.getId()) || 
     102                id.contains(Event.STARTEVENT.getId() + "-=-")) 
     103            { 
     104                startIndexList.add(i); 
     105            } 
     106            if (id.equals(Event.ENDEVENT.getId()) || id.contains("-=-" + Event.ENDEVENT.getId())) { 
     107                endIndexList.add(i); 
     108            } 
     109        } 
     110 
     111        if (startIndexList.isEmpty()) { 
     112            Console 
     113                .printerrln("Error calculating entropy. Initial state of markov chain not found."); 
     114            return Double.NaN; 
     115        } 
     116        if (endIndexList.isEmpty()) { 
     117            Console.printerrln("Error calculating entropy. End state of markov chain not found."); 
     118            return Double.NaN; 
     119        } 
     120        for (Integer i : endIndexList) { 
     121            for (Integer j : startIndexList) { 
     122                transmissionMatrix.set(i, j, 1); 
     123            } 
     124        } 
     125 
     126        // Calculate stationary distribution by raising the power of the 
     127        // transmission matrix. 
     128        // The rank of the matrix should fall to 1 and each two should be the 
     129        // vector of the stationory distribution. 
     130        int iter = 0; 
     131        int rank = transmissionMatrix.rank(); 
     132        Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone(); 
     133        while (iter < MAX_STATDIST_ITERATIONS && rank > 1) { 
     134            stationaryMatrix = stationaryMatrix.times(stationaryMatrix); 
     135            rank = stationaryMatrix.rank(); 
     136            iter++; 
     137        } 
     138 
     139        if (rank != 1) { 
     140            Console.traceln("rank: " + rank); 
     141            Console.printerrln("Unable to calculate stationary distribution."); 
     142            return Double.NaN; 
     143        } 
     144 
     145        double entropy = 0.0; 
     146        for (int i = 0; i < numStates; i++) { 
     147            for (int j = 0; j < numStates; j++) { 
     148                if (transmissionMatrix.get(i, j) != 0 && transmissionMatrix.get(i, j) != 1) { 
     149                    double tmp = stationaryMatrix.get(0, i); 
     150                    tmp *= transmissionMatrix.get(i, j); 
     151                    tmp *= Math.log(transmissionMatrix.get(i, j)) / Math.log(2); 
     152                    entropy -= tmp; 
     153                } 
     154            } 
     155        } 
     156        return entropy; 
     157    } 
     158 
     159    /** 
     160     * <p> 
     161     * The dot represenation of {@link FirstOrderMarkovModel}s is its graph representation with the 
     162     * states as nodes and directed edges weighted with transition probabilities. 
     163     * </p> 
     164     *  
     165     * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() 
     166     */ 
     167    @Override 
     168    public String getDotRepresentation() { 
     169        StringBuilder stringBuilder = new StringBuilder(); 
     170        stringBuilder.append("digraph model {" + StringTools.ENDLINE); 
     171 
     172        List<Event> knownSymbols = new ArrayList<Event>(trie.getKnownSymbols()); 
     173        for (Event symbol : knownSymbols) { 
     174            final String thisSaneId = symbol.getId().replace("\"", "\\\"").replaceAll("[\r\n]", ""); 
     175            stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " [label=\"" + thisSaneId + 
     176                "\"];" + StringTools.ENDLINE); 
     177            List<Event> context = new ArrayList<Event>(); 
     178            context.add(symbol); 
     179            Collection<Event> followers = trie.getFollowingSymbols(context); 
     180            for (Event follower : followers) { 
     181                stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " -> " + 
     182                    knownSymbols.indexOf(follower) + " "); 
     183                stringBuilder.append("[label=\"" + getProbability(context, follower) + "\"];" + 
     184                    StringTools.ENDLINE); 
     185            } 
     186        } 
     187        stringBuilder.append('}' + StringTools.ENDLINE); 
     188        return stringBuilder.toString(); 
     189    } 
     190 
     191    /** 
     192     * <p> 
     193     * Returns a {@link Graph} representation of the model with the states as nodes and directed 
     194     * edges weighted with transition probabilities. 
     195     * </p> 
     196     *  
     197     * @return {@link Graph} of the model 
     198     */ 
     199    public Graph<String, MarkovEdge> getGraph() { 
     200        Graph<String, MarkovEdge> graph = new SparseMultigraph<String, MarkovEdge>(); 
     201 
     202        List<Event> knownSymbols = new ArrayList<Event>(trie.getKnownSymbols()); 
     203 
     204        for (Event symbol : knownSymbols) { 
     205            String from = symbol.getId(); 
     206            List<Event> context = new ArrayList<Event>(); 
     207            context.add(symbol); 
     208 
     209            Collection<Event> followers = trie.getFollowingSymbols(context); 
     210 
     211            for (Event follower : followers) { 
     212                String to = follower.getId(); 
     213                MarkovEdge prob = new MarkovEdge(getProbability(context, follower)); 
     214                graph.addEdge(prob, from, to, EdgeType.DIRECTED); 
     215            } 
     216        } 
     217        return graph; 
     218    } 
     219 
     220    /** 
     221     * Inner class used for the {@link Graph} representation of the model. 
     222     *  
     223     * @author Steffen Herbold 
     224     * @version 1.0 
     225     */ 
     226    static public class MarkovEdge { 
     227        /** 
     228         * <p> 
     229         * Weight of the edge, i.e., its transition probability. 
     230         * </p> 
     231         */ 
     232        double weight; 
     233 
     234        /** 
     235         * <p> 
     236         * Constructor. Creates a new MarkovEdge. 
     237         * </p> 
     238         *  
     239         * @param weight 
     240         *            weight of the edge, i.e., its transition probability 
     241         */ 
     242        MarkovEdge(double weight) { 
     243            this.weight = weight; 
     244        } 
     245 
     246        /** 
     247         * <p> 
     248         * The weight of the edge as {@link String}. 
     249         * </p> 
     250         */ 
     251        public String toString() { 
     252            return "" + weight; 
     253        } 
     254    } 
    263255 
    264256} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1920public class HighOrderMarkovModel extends TrieBasedModel { 
    2021 
    21         /** 
    22         * <p> 
    23         * Id for object serialization. 
    24         * </p> 
    25         */ 
    26         private static final long serialVersionUID = 1L; 
     22    /** 
     23    * <p> 
     24    * Id for object serialization. 
     25    * </p> 
     26    */ 
     27    private static final long serialVersionUID = 1L; 
    2728 
    28         /** 
    29          * <p> 
    30          * Constructor. Creates a new HighOrderMarkovModel with a defined Markov 
    31          * order. 
    32          * </p> 
    33          *  
    34          * @param maxOrder 
    35          *            Markov order of the model 
    36          * @param r 
    37          *            random number generator used by probabilistic methods of the 
    38          *            class 
    39          */ 
    40         public HighOrderMarkovModel(int maxOrder, Random r) { 
    41                 super(maxOrder, r); 
    42         } 
     29    /** 
     30     * <p> 
     31     * Constructor. Creates a new HighOrderMarkovModel with a defined Markov order. 
     32     * </p> 
     33     *  
     34     * @param maxOrder 
     35     *            Markov order of the model 
     36     * @param r 
     37     *            random number generator used by probabilistic methods of the class 
     38     */ 
     39    public HighOrderMarkovModel(int maxOrder, Random r) { 
     40        super(maxOrder, r); 
     41    } 
    4342 
    44         /** 
    45          * <p> 
    46          * Calculates the probability of the next Event being symbol based on the 
    47          * order of the Markov model. The order is defined in the constructor 
    48          * {@link #HighOrderMarkovModel(int, Random)}. 
    49          * </p> 
    50          *  
    51          * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
    52          *      de.ugoe.cs.quest.eventcore.Event) 
    53          */ 
    54         @Override 
    55         public double getProbability(List<Event> context, 
    56                         Event symbol) { 
    57                 if (context == null) { 
    58                         throw new InvalidParameterException("context must not be null"); 
    59                 } 
    60                 if (symbol == null) { 
    61                         throw new InvalidParameterException("symbol must not be null"); 
    62                 } 
    63                 double result = 0.0d; 
     43    /** 
     44     * <p> 
     45     * Calculates the probability of the next Event being symbol based on the order of the Markov 
     46     * model. The order is defined in the constructor {@link #HighOrderMarkovModel(int, Random)}. 
     47     * </p> 
     48     *  
     49     * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
     50     *      de.ugoe.cs.quest.eventcore.Event) 
     51     */ 
     52    @Override 
     53    public double getProbability(List<Event> context, Event symbol) { 
     54        if (context == null) { 
     55            throw new InvalidParameterException("context must not be null"); 
     56        } 
     57        if (symbol == null) { 
     58            throw new InvalidParameterException("symbol must not be null"); 
     59        } 
     60        double result = 0.0d; 
    6461 
    65                 List<Event> contextCopy; 
    66                 if (context.size() >= trieOrder) { 
    67                         contextCopy = new LinkedList<Event>(context.subList( 
    68                                         context.size() - trieOrder + 1, context.size())); 
    69                 } else { 
    70                         contextCopy = new LinkedList<Event>(context); 
    71                 } 
     62        List<Event> contextCopy; 
     63        if (context.size() >= trieOrder) { 
     64            contextCopy = 
     65                new LinkedList<Event>(context.subList(context.size() - trieOrder + 1, 
     66                                                      context.size())); 
     67        } 
     68        else { 
     69            contextCopy = new LinkedList<Event>(context); 
     70        } 
    7271 
    73                 Collection<Event> followers = trie.getFollowingSymbols(contextCopy); 
    74                 int sumCountFollowers = 0; // N(s\sigma') 
    75                 for (Event follower : followers) { 
    76                         sumCountFollowers += trie.getCount(contextCopy, follower); 
    77                 } 
     72        Collection<Event> followers = trie.getFollowingSymbols(contextCopy); 
     73        int sumCountFollowers = 0; // N(s\sigma') 
     74        for (Event follower : followers) { 
     75            sumCountFollowers += trie.getCount(contextCopy, follower); 
     76        } 
    7877 
    79                 int countSymbol = trie.getCount(contextCopy, symbol); 
    80                 if (sumCountFollowers != 0) { 
    81                         result = ((double) countSymbol / sumCountFollowers); 
    82                 } 
     78        int countSymbol = trie.getCount(contextCopy, symbol); 
     79        if (sumCountFollowers != 0) { 
     80            result = ((double) countSymbol / sumCountFollowers); 
     81        } 
    8382 
    84                 return result; 
    85         } 
     83        return result; 
     84    } 
    8685 
    8786} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java

    r518 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    34/** 
    45 * <p> 
    5  * Models implementing this interface provide a graph representation of 
    6  * themselves as a {@link String} with Dot syntax. 
     6 * Models implementing this interface provide a graph representation of themselves as a 
     7 * {@link String} with Dot syntax. 
    78 * </p> 
    89 *  
    … …  
    1213public interface IDotCompatible { 
    1314 
    14         /** 
    15         * <p> 
    16         * Returns a Dot representation of the model. 
    17         * </p> 
    18         *  
    19         * @return string with Dot syntax that describes the model. 
    20         */ 
    21         public abstract String getDotRepresentation(); 
     15    /** 
     16    * <p> 
     17    * Returns a Dot representation of the model. 
     18    * </p> 
     19    *  
     20    * @return string with Dot syntax that describes the model. 
     21    */ 
     22    public abstract String getDotRepresentation(); 
    2223} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java

    r518 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    56/** 
    67 * <p> 
    7  * This interface defines basic functions for classes that implement a memory 
    8  * about the recent events of a sequences. 
     8 * This interface defines basic functions for classes that implement a memory about the recent 
     9 * events of a sequences. 
    910 * </p> 
    1011 *  
    … …  
    1718public interface IMemory<T> { 
    1819 
    19         /** 
    20         * Adds an element to the end of the memory. 
    21         *  
    22         * @param element 
    23         *            Element to be added. 
    24         */ 
    25         public void add(T element); 
     20    /** 
     21    * Adds an element to the end of the memory. 
     22    *  
     23    * @param element 
     24    *            Element to be added. 
     25    */ 
     26    public void add(T element); 
    2627 
    27         /** 
    28         * <p> 
    29          * Returns the last <code>num</code> memorized elements. If the history is 
    30          * shorter than <code>num</code>, the length of the returned 
    31          * {@link java.util.List} may be less than <code>num</code>. 
    32         * </p> 
    33         *  
    34         * @param num 
    35         *            Number of states from the end of the memory to be returned. 
    36         * @return {@link java.util.List} of memorized elements. 
    37         */ 
    38         public List<T> getLast(int num); 
     28    /** 
     29    * <p> 
     30     * Returns the last <code>num</code> memorized elements. If the history is shorter than 
     31     * <code>num</code>, the length of the returned {@link java.util.List} may be less than 
     32     * <code>num</code>. 
     33    * </p> 
     34    *  
     35    * @param num 
     36    *            Number of states from the end of the memory to be returned. 
     37    * @return {@link java.util.List} of memorized elements. 
     38    */ 
     39    public List<T> getLast(int num); 
    3940 
    4041} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1819public interface IStochasticProcess extends Serializable { 
    1920 
    20         /** 
    21         * <p> 
    22          * Returns the probability, that the next event is {@code symbol} given the 
    23          * last events are {@code context}. The last element of {@code context} is 
    24          * the most recent in the history, the first element is the oldest. 
    25         * </p> 
    26         *  
    27         * @param context 
    28         *            recently observed symbols 
    29         * @param symbol 
    30         *            event for which the probability is calculated 
    31          * @return probabilty the {@code symbol} is the next event, given the last 
    32          *         events {@code context} 
    33         * @throws InvalidParameterException 
    34         *             thrown if context or symbol is null 
    35         */ 
    36         double getProbability(List<Event> context, Event symbol); 
     21    /** 
     22    * <p> 
     23     * Returns the probability, that the next event is {@code symbol} given the last events are 
     24     * {@code context}. The last element of {@code context} is the most recent in the history, the 
     25     * first element is the oldest. 
     26    * </p> 
     27    *  
     28    * @param context 
     29    *            recently observed symbols 
     30    * @param symbol 
     31    *            event for which the probability is calculated 
     32     * @return probabilty the {@code symbol} is the next event, given the last events 
     33     *        {@code context} 
     34    * @throws InvalidParameterException 
     35    *             thrown if context or symbol is null 
     36    */ 
     37    double getProbability(List<Event> context, Event symbol); 
    3738 
    38         /** 
    39          * <p> 
    40          * Returns the probabilitiy that a given sequence is generated by the 
    41          * stochastic process. 
    42          * </p> 
    43          *  
    44          * @param sequence 
    45          *            sequences of which the probability is calculated 
    46          * @return probability of the sequences; 1.0 if sequence is empty or null 
    47          * @throws InvalidParameterException 
    48          *             thrown if sequence is null 
    49          */ 
    50         double getProbability(List<Event> sequence); 
     39    /** 
     40     * <p> 
     41     * Returns the probabilitiy that a given sequence is generated by the stochastic process. 
     42     * </p> 
     43     *  
     44     * @param sequence 
     45     *            sequences of which the probability is calculated 
     46     * @return probability of the sequences; 1.0 if sequence is empty or null 
     47     * @throws InvalidParameterException 
     48     *             thrown if sequence is null 
     49     */ 
     50    double getProbability(List<Event> sequence); 
    5151 
    52         /** 
    53         * <p> 
    54          * Generates a random sequence of events. The sequence starts with 
    55          * {@link Event#STARTEVENT} and finishes with {@link Event#ENDEVENT}. 
    56         * </p> 
    57         *  
    58         * @return randomly generated sequence 
    59         */ 
    60         public List<Event> randomSequence(); 
     52    /** 
     53    * <p> 
     54     * Generates a random sequence of events. The sequence starts with {@link Event#STARTEVENT} and 
     55     * finishes with {@link Event#ENDEVENT}. 
     56    * </p> 
     57    *  
     58    * @return randomly generated sequence 
     59    */ 
     60    public List<Event> randomSequence(); 
    6161 
    62         /** 
    63          * <p> 
    64          * Generates a random sequence of events. The sequence starts with 
    65          * {@link Event#STARTEVENT} and finishes with 
    66          * <ul> 
    67          * <li>{@link Event#ENDEVENT} if validEnd==true.</li> 
    68          * <li>b) if a generated sequences reaches {@link Event#ENDEVENT} before 
    69          * maxLength, the sequence finishes and is shorter than maxLenght. 
    70          * Otherwise, the sequence finishes as soon as maxLength is reached and the 
    71          * final event of the sequence must not be {@link Event#ENDEVENT}.</li> 
    72          * </ul> 
    73          * </p> 
    74          *  
    75          * @param maxLength 
    76          *            maximum length of the generated sequence 
    77          * @param validEnd 
    78          *            if true, only sequences that finish with 
    79          *            {@link Event#ENDEVENT} are generated 
    80          * @return randomly generated sequence 
    81          *  
    82          */ 
    83         public List<Event> randomSequence(int maxLength, 
    84                         boolean validEnd); 
     62    /** 
     63     * <p> 
     64     * Generates a random sequence of events. The sequence starts with {@link Event#STARTEVENT} and 
     65     * finishes with 
     66     * <ul> 
     67     * <li>{@link Event#ENDEVENT} if validEnd==true.</li> 
     68     * <li>b) if a generated sequences reaches {@link Event#ENDEVENT} before maxLength, the sequence 
     69     * finishes and is shorter than maxLenght. Otherwise, the sequence finishes as soon as maxLength 
     70     * is reached and the final event of the sequence must not be {@link Event#ENDEVENT}.</li> 
     71     * </ul> 
     72     * </p> 
     73     *  
     74     * @param maxLength 
     75     *            maximum length of the generated sequence 
     76     * @param validEnd 
     77     *            if true, only sequences that finish with {@link Event#ENDEVENT} are generated 
     78     * @return randomly generated sequence 
     79     *  
     80     */ 
     81    public List<Event> randomSequence(int maxLength, boolean validEnd); 
    8582 
    86         /** 
    87          * <p> 
    88          * Generates all sequences of a given length are possible, i.e., have a 
    89          * positive probability.<br> 
    90          * All states are used as possible starting states. 
    91          * </p> 
    92          *  
    93          * @param length 
    94          *            length of the generated sequences 
    95          * @return generated sequences 
    96          * @see #generateSequences(int, boolean) 
    97          * @throws InvalidParameterException 
    98          *             thrown if length is less than or equal to 0 
    99          */ 
    100         public Collection<List<Event>> generateSequences(int length); 
     83    /** 
     84     * <p> 
     85     * Generates all sequences of a given length are possible, i.e., have a positive probability.<br> 
     86     * All states are used as possible starting states. 
     87     * </p> 
     88     *  
     89     * @param length 
     90     *            length of the generated sequences 
     91     * @return generated sequences 
     92     * @see #generateSequences(int, boolean) 
     93     * @throws InvalidParameterException 
     94     *             thrown if length is less than or equal to 0 
     95     */ 
     96    public Collection<List<Event>> generateSequences(int length); 
    10197 
    102         /** 
    103          * <p> 
    104          * Generates all sequences of given length that can are possible, i.e., have 
    105          * positive probability.<br> 
    106          * If {@code fromStart==true}, all generated sequences start in 
    107          * {@link Event#STARTEVENT}. Otherwise this method is the same as 
    108          * {@link #generateSequences(int)}. 
    109          * </p> 
    110          *  
    111          * @param length 
    112          *            length of the generated sequences 
    113          * @param fromStart 
    114          *            if true, all generated sequences start with 
    115          *            {@link Event#STARTEVENT} 
    116          * @return generated sequences 
    117          * @throws InvalidParameterException 
    118          *             thrown if length is less than or equal to 0 
    119          */ 
    120         public Collection<List<Event>> generateSequences(int length, 
    121                         boolean fromStart); 
     98    /** 
     99     * <p> 
     100     * Generates all sequences of given length that can are possible, i.e., have positive 
     101     * probability.<br> 
     102     * If {@code fromStart==true}, all generated sequences start in {@link Event#STARTEVENT}. 
     103     * Otherwise this method is the same as {@link #generateSequences(int)}. 
     104     * </p> 
     105     *  
     106     * @param length 
     107     *            length of the generated sequences 
     108     * @param fromStart 
     109     *            if true, all generated sequences start with {@link Event#STARTEVENT} 
     110     * @return generated sequences 
     111     * @throws InvalidParameterException 
     112     *             thrown if length is less than or equal to 0 
     113     */ 
     114    public Collection<List<Event>> generateSequences(int length, boolean fromStart); 
    122115 
    123         /** 
    124          * <p> 
    125          * Generates all sequences starting with {@link Event#STARTEVENT} and 
    126          * finishing with {@link Event#ENDEVENT} of a given length. It is possible 
    127          * that no such sequence exists with the defined length and the returned set 
    128          * is empty. If {@code length} is less than 2 the returned set is always 
    129          * empty. 
    130          * </p> 
    131          *  
    132          * @param length 
    133          * @return generated sequences 
    134          * @throws InvalidParameterException 
    135          *             thrown if length is less than or equal to 0 
    136          */ 
    137         public Collection<List<Event>> generateValidSequences( 
    138                         int length); 
     116    /** 
     117     * <p> 
     118     * Generates all sequences starting with {@link Event#STARTEVENT} and finishing with 
     119     * {@link Event#ENDEVENT} of a given length. It is possible that no such sequence exists with 
     120     * the defined length and the returned set is empty. If {@code length} is less than 2 the 
     121     * returned set is always empty. 
     122     * </p> 
     123     *  
     124     * @param length 
     125     * @return generated sequences 
     126     * @throws InvalidParameterException 
     127     *             thrown if length is less than or equal to 0 
     128     */ 
     129    public Collection<List<Event>> generateValidSequences(int length); 
    139130 
    140         /** 
    141          * <p> 
    142          * Returns the number of states known by the stochastic process, i.e., the 
    143          * size of its alphabet. 
    144          * </p> 
    145          *  
    146          * @return number of states 
    147          */ 
    148         public int getNumSymbols(); 
     131    /** 
     132     * <p> 
     133     * Returns the number of states known by the stochastic process, i.e., the size of its alphabet. 
     134     * </p> 
     135     *  
     136     * @return number of states 
     137     */ 
     138    public int getNumSymbols(); 
    149139 
    150         /** 
    151         * <p> 
    152         * Returns a string representation of all known states. 
    153         * </p> 
    154         *  
    155         * @return string representation for all known states 
    156         */ 
    157         public String[] getSymbolStrings(); 
     140    /** 
     141    * <p> 
     142    * Returns a string representation of all known states. 
     143    * </p> 
     144    *  
     145    * @return string representation for all known states 
     146    */ 
     147    public String[] getSymbolStrings(); 
    158148 
    159         /** 
    160          * <p> 
    161          * Returns the number of states the process would have if it would be 
    162          * flattened through state-splitting to a first-order Markov model. 
    163          * </p> 
    164          * <p> 
    165          * If it is not possible to flatten the model, -1 is returned. 
    166          * </p> 
    167          *  
    168          * @return number of states an equivalent FOM would have; -1 if not 
    169          *         available 
    170          */ 
    171         public int getNumFOMStates(); 
     149    /** 
     150     * <p> 
     151     * Returns the number of states the process would have if it would be flattened through 
     152     * state-splitting to a first-order Markov model. 
     153     * </p> 
     154     * <p> 
     155     * If it is not possible to flatten the model, -1 is returned. 
     156     * </p> 
     157     *  
     158     * @return number of states an equivalent FOM would have; -1 if not available 
     159     */ 
     160    public int getNumFOMStates(); 
    172161 
    173         /** 
    174          * <p> 
    175          * Returns the number of transitions the process would have if it would be 
    176          * flattened through state-splitting to a first-order Markov model. 
    177          * </p> 
    178          *  
    179          * @return number of transitions an equivalent FOM would have; -1 if not 
    180          *         available 
    181          */ 
    182         public int getNumTransitions(); 
     162    /** 
     163     * <p> 
     164     * Returns the number of transitions the process would have if it would be flattened through 
     165     * state-splitting to a first-order Markov model. 
     166     * </p> 
     167     *  
     168     * @return number of transitions an equivalent FOM would have; -1 if not available 
     169     */ 
     170    public int getNumTransitions(); 
    183171 
    184         /** 
    185          * <p> 
    186          * Returns all states known by the stochastic process, i.e., its 
    187          * {@link Event}s. 
    188          * </p> 
    189          *  
    190          * @return events known by the process 
    191          */ 
    192         public Collection<Event> getEvents(); 
     172    /** 
     173     * <p> 
     174     * Returns all states known by the stochastic process, i.e., its {@link Event}s. 
     175     * </p> 
     176     *  
     177     * @return events known by the process 
     178     */ 
     179    public Collection<Event> getEvents(); 
    193180 
    194181} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java

    r518 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    78/** 
    89 * <p> 
    9  * Implements a round-trip buffered memory of a specified length that can be 
    10  * used to remember the recent history. Every event that happend longer ago than 
    11  * the length of the memory is forgotten, hence the memory is incomplete. 
     10 * Implements a round-trip buffered memory of a specified length that can be used to remember the 
     11 * recent history. Every event that happend longer ago than the length of the memory is forgotten, 
     12 * hence the memory is incomplete. 
    1213 * </p> 
    1314 *  
    … …  
    2021public class IncompleteMemory<T> implements IMemory<T> { 
    2122 
    22         /** 
    23         * <p> 
    24         * Maximum length of the memory. 
    25         * </p> 
    26         */ 
    27         private int length; 
     23    /** 
     24    * <p> 
     25    * Maximum length of the memory. 
     26    * </p> 
     27    */ 
     28    private int length; 
    2829 
    29         /** 
    30         * <p> 
    31         * Internal storage of the history. 
    32         * </p> 
    33         */ 
    34         private List<T> history; 
     30    /** 
     31    * <p> 
     32    * Internal storage of the history. 
     33    * </p> 
     34    */ 
     35    private List<T> history; 
    3536 
    36         /** 
    37          * <p> 
    38          * Constructor. Creates a new IncompleteMemory. 
    39          * </p> 
    40          *  
    41          * @param length 
    42          *            number of recent events that are remembered 
    43          * @throws InvalidParameterException 
    44          *             This exception is thrown if the length is smaller than 1 
    45          */ 
    46         public IncompleteMemory(int length) { 
    47                 if (length < 1) { 
    48                         throw new InvalidParameterException( 
    49                                         "Length of IncompleteMemory must be at least 1."); 
    50                 } 
    51                 this.length = length; 
    52                 history = new LinkedList<T>(); 
    53         } 
     37    /** 
     38     * <p> 
     39     * Constructor. Creates a new IncompleteMemory. 
     40     * </p> 
     41     *  
     42     * @param length 
     43     *            number of recent events that are remembered 
     44     * @throws InvalidParameterException 
     45     *             This exception is thrown if the length is smaller than 1 
     46     */ 
     47    public IncompleteMemory(int length) { 
     48        if (length < 1) { 
     49            throw new InvalidParameterException("Length of IncompleteMemory must be at least 1."); 
     50        } 
     51        this.length = length; 
     52        history = new LinkedList<T>(); 
     53    } 
    5454 
    55         /* 
    56         * (non-Javadoc) 
    57         *  
    58         * @see de.ugoe.cs.quest.usageprofiles.IMemory#add(java.lang.Object) 
    59         */ 
    60         @Override 
    61         public void add(T state) { 
    62                 if (history.size() == length) { 
    63                         history.remove(0); 
    64                 } 
    65                 history.add(state); 
    66         } 
     55    /* 
     56    * (non-Javadoc) 
     57    *  
     58    * @see de.ugoe.cs.quest.usageprofiles.IMemory#add(java.lang.Object) 
     59    */ 
     60    @Override 
     61    public void add(T state) { 
     62        if (history.size() == length) { 
     63            history.remove(0); 
     64        } 
     65        history.add(state); 
     66    } 
    6767 
    68         /* 
    69         * (non-Javadoc) 
    70         *  
    71         * @see de.ugoe.cs.quest.usageprofiles.IMemory#getLast(int) 
    72         */ 
    73         @Override 
    74         public List<T> getLast(int num) { 
    75                 if( num<1 ) { 
    76                         return new LinkedList<T>(); 
    77                 } else { 
    78                 return new LinkedList<T>(history.subList( 
    79                                 Math.max(0, history.size() - num), 
    80                                 history.size())); // defensive copy 
    81                 } 
    82         } 
     68    /* 
     69    * (non-Javadoc) 
     70    *  
     71    * @see de.ugoe.cs.quest.usageprofiles.IMemory#getLast(int) 
     72    */ 
     73    @Override 
     74    public List<T> getLast(int num) { 
     75        if (num < 1) { 
     76            return new LinkedList<T>(); 
     77        } 
     78        else { 
     79            return new LinkedList<T>(history.subList(Math.max(0, history.size() - num), 
     80                                                     history.size())); // defensive copy 
     81        } 
     82    } 
    8383 
    84         /** 
    85         * <p> 
    86          * Returns the current length of the memory. This can be less than 
    87          * {@link #length}, if the overall history is less than {@link #length}. 
    88         * </p> 
    89         *  
    90         * @return length of the current memory 
    91         */ 
    92         public int getLength() { 
    93                 return history.size(); 
    94         } 
     84    /** 
     85    * <p> 
     86     * Returns the current length of the memory. This can be less than {@link #length}, if the 
     87     * overall history is less than {@link #length}. 
     88    * </p> 
     89    *  
     90    * @return length of the current memory 
     91    */ 
     92    public int getLength() { 
     93        return history.size(); 
     94    } 
    9595} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java

    r553 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1011/** 
    1112 * <p> 
    12  * This class provides functions to create flattened first-order Markov models 
    13  * from {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch} 
    14  * models through state splitting. 
     13 * This class provides functions to create flattened first-order Markov models from 
     14 * {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch} models through state 
     15 * splitting. 
    1516 * </p> 
    1617 * <p> 
    17  * If possible, the normal high-order markov model should be used, as the Events 
    18  * may be broken by the flattener, as, e.g., the information 
    19  * {@link ReplayableEvent}s contain is not preserved. 
     18 * If possible, the normal high-order markov model should be used, as the Events may be broken by 
     19 * the flattener, as, e.g., the information {@link ReplayableEvent}s contain is not preserved. 
    2020 * </p> 
    2121 *  
    … …  
    2525public class ModelFlattener { 
    2626 
    27         private static final String EVENT_SEPARATOR = "-=-"; 
     27    private static final String EVENT_SEPARATOR = "-=-"; 
    2828 
    29         Trie<Event> firstOrderTrie; 
     29    Trie<Event> firstOrderTrie; 
    3030 
    31         /** 
    32          * <p> 
    33          * Takes a {@link HighOrderMarkovModel} and returns a 
    34          * {@link FirstOrderMarkovModel} that conserves the high-order memory 
    35          * through state splitting. 
    36          * </p> 
    37          *  
    38          * @param model 
    39          *            model that is flattened 
    40          * @return flattened first-order Markov model 
    41          */ 
    42         public FirstOrderMarkovModel flattenHighOrderMarkovModel( 
    43                         HighOrderMarkovModel model) { 
    44                 int markovOrder = model.trieOrder - 1; 
    45                 FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel( 
    46                                 new Random()); 
    47                 firstOrderModel.trieOrder = 2; 
    48                 if (markovOrder == 1) { 
    49                         firstOrderModel.trie = new Trie<Event>(model.trie); 
    50                         firstOrderModel.trieOrder = 2; 
    51                 } else { 
    52                         firstOrderTrie = new Trie<Event>(); 
    53                         TrieNode<Event> rootNode = model.trie.find(null); 
    54                         generateFirstOrderTrie(rootNode, new LinkedList<String>(), markovOrder); 
    55                         firstOrderTrie.updateKnownSymbols(); 
    56                         firstOrderModel.trie = firstOrderTrie; 
    57                 } 
     31    /** 
     32     * <p> 
     33     * Takes a {@link HighOrderMarkovModel} and returns a {@link FirstOrderMarkovModel} that 
     34     * conserves the high-order memory through state splitting. 
     35     * </p> 
     36     *  
     37     * @param model 
     38     *            model that is flattened 
     39     * @return flattened first-order Markov model 
     40     */ 
     41    public FirstOrderMarkovModel flattenHighOrderMarkovModel(HighOrderMarkovModel model) { 
     42        int markovOrder = model.trieOrder - 1; 
     43        FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel(new Random()); 
     44        firstOrderModel.trieOrder = 2; 
     45        if (markovOrder == 1) { 
     46            firstOrderModel.trie = new Trie<Event>(model.trie); 
     47            firstOrderModel.trieOrder = 2; 
     48        } 
     49        else { 
     50            firstOrderTrie = new Trie<Event>(); 
     51            TrieNode<Event> rootNode = model.trie.find(null); 
     52            generateFirstOrderTrie(rootNode, new LinkedList<String>(), markovOrder); 
     53            firstOrderTrie.updateKnownSymbols(); 
     54            firstOrderModel.trie = firstOrderTrie; 
     55        } 
    5856 
    59                 return firstOrderModel; 
    60         } 
     57        return firstOrderModel; 
     58    } 
    6159 
    62         /** 
    63          * <p> 
    64          * <b>This method is not available yet and always return null!</b> 
    65          * </p> 
    66          * <p> 
    67          * Takes a {@link PredictionByPartialMatch} model and returns a 
    68          * {@link FirstOrderMarkovModel} that conserves the high-order memory 
    69          * through state splitting. 
    70          * </p> 
    71          *  
    72          * @param model 
    73          *            model that is flattened 
    74          * @return flattened first-order Markov model 
    75          */ 
    76         public FirstOrderMarkovModel flattenPredictionByPartialMatch( 
    77                         PredictionByPartialMatch model) { 
    78                 // TODO implement method 
    79                 return null; 
    80         } 
     60    /** 
     61     * <p> 
     62     * <b>This method is not available yet and always return null!</b> 
     63     * </p> 
     64     * <p> 
     65     * Takes a {@link PredictionByPartialMatch} model and returns a {@link FirstOrderMarkovModel} 
     66     * that conserves the high-order memory through state splitting. 
     67     * </p> 
     68     *  
     69     * @param model 
     70     *            model that is flattened 
     71     * @return flattened first-order Markov model 
     72     */ 
     73    public FirstOrderMarkovModel flattenPredictionByPartialMatch(PredictionByPartialMatch model) { 
     74        // TODO implement method 
     75        return null; 
     76    } 
    8177 
    82         /** 
    83          * <p> 
    84          * Converts all nodes of the given depth into first-order node through 
    85          * state-splitting. For each node at the given depth a new node is created 
    86          * and appropriate transitions will be added. 
    87          * </p> 
    88          * <p> 
    89          * This method traverses through the tree recursively. If the recursion 
    90          * reaches the desired depth in the tree, node are added. 
    91          * </p> 
    92          *  
    93          * @param currentNode 
    94          *            node whose sub-trie is currently traversed 
    95          * @param parentIDs 
    96          *            ID strings of the ancestors of the currentNode 
    97          * @param depth 
    98          *            depth to go - NOT the current depth. 
    99          */ 
    100         private void generateFirstOrderTrie(TrieNode<Event> currentNode, 
    101                         List<String> parentIDs, int depth) { 
    102                 for (TrieNode<Event> child : currentNode.getChildren()) { 
    103                         String currentId = child.getSymbol().getId(); 
    104                         if (depth > 1) { 
    105                                 List<String> childParentIDs = new LinkedList<String>(parentIDs); 
    106                                 childParentIDs.add(currentId); 
    107                                 generateFirstOrderTrie(child, childParentIDs, depth - 1); 
     78    /** 
     79     * <p> 
     80     * Converts all nodes of the given depth into first-order node through state-splitting. For each 
     81     * node at the given depth a new node is created and appropriate transitions will be added. 
     82     * </p> 
     83     * <p> 
     84     * This method traverses through the tree recursively. If the recursion reaches the desired 
     85     * depth in the tree, node are added. 
     86     * </p> 
     87     *  
     88     * @param currentNode 
     89     *            node whose sub-trie is currently traversed 
     90     * @param parentIDs 
     91     *            ID strings of the ancestors of the currentNode 
     92     * @param depth 
     93     *            depth to go - NOT the current depth. 
     94     */ 
     95    private void generateFirstOrderTrie(TrieNode<Event> currentNode, 
     96                                        List<String> parentIDs, 
     97                                        int depth) 
     98    { 
     99        for (TrieNode<Event> child : currentNode.getChildren()) { 
     100            String currentId = child.getSymbol().getId(); 
     101            if (depth > 1) { 
     102                List<String> childParentIDs = new LinkedList<String>(parentIDs); 
     103                childParentIDs.add(currentId); 
     104                generateFirstOrderTrie(child, childParentIDs, depth - 1); 
    108105 
    109                         } else { 
    110                                 StringBuilder firstOrderID = new StringBuilder(); 
    111                                 for (String parentID : parentIDs) { 
    112                                         firstOrderID.append(parentID + EVENT_SEPARATOR); 
    113                                 } 
    114                                 firstOrderID.append(currentId); 
    115                                 TrieNode<Event> firstOrderNode = firstOrderTrie 
    116                                                 .getChildCreate(new Event(new StringEventType(firstOrderID 
    117                                                                 .toString()))); 
    118                                 firstOrderNode.setCount(child.getCount()); 
    119                                 for (TrieNode<Event> transitionChild : child.getChildren()) { 
    120                                         StringBuilder transitionID = new StringBuilder(); 
    121                                         for (String parentID : parentIDs.subList(1, 
    122                                                         parentIDs.size())) { 
    123                                                 transitionID.append(parentID + EVENT_SEPARATOR); 
    124                                         } 
    125                                         transitionID.append(currentId + EVENT_SEPARATOR); 
    126                                         transitionID.append(transitionChild.getSymbol() 
    127                                                         .getId()); 
    128                                         TrieNode<Event> firstOrderTransitionChild = firstOrderNode 
    129                                                         .getChildCreate(new Event(new StringEventType(transitionID 
    130                                                                         .toString()))); 
    131                                         firstOrderTransitionChild.setCount(transitionChild 
    132                                                         .getCount()); 
    133                                 } 
    134                         } 
    135                 } 
    136         } 
     106            } 
     107            else { 
     108                StringBuilder firstOrderID = new StringBuilder(); 
     109                for (String parentID : parentIDs) { 
     110                    firstOrderID.append(parentID + EVENT_SEPARATOR); 
     111                } 
     112                firstOrderID.append(currentId); 
     113                TrieNode<Event> firstOrderNode = 
     114                    firstOrderTrie.getChildCreate(new Event(new StringEventType(firstOrderID 
     115                        .toString()))); 
     116                firstOrderNode.setCount(child.getCount()); 
     117                for (TrieNode<Event> transitionChild : child.getChildren()) { 
     118                    StringBuilder transitionID = new StringBuilder(); 
     119                    for (String parentID : parentIDs.subList(1, parentIDs.size())) { 
     120                        transitionID.append(parentID + EVENT_SEPARATOR); 
     121                    } 
     122                    transitionID.append(currentId + EVENT_SEPARATOR); 
     123                    transitionID.append(transitionChild.getSymbol().getId()); 
     124                    TrieNode<Event> firstOrderTransitionChild = 
     125                        firstOrderNode.getChildCreate(new Event(new StringEventType(transitionID 
     126                            .toString()))); 
     127                    firstOrderTransitionChild.setCount(transitionChild.getCount()); 
     128                } 
     129            } 
     130        } 
     131    } 
    137132} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1112/** 
    1213 * <p> 
    13  * Implements Prediction by Partial Match (PPM) based on the following formula 
    14  * (LaTeX-style notation):<br> 
     14 * Implements Prediction by Partial Match (PPM) based on the following formula (LaTeX-style 
     15 * notation):<br> 
    1516 * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n 
    1617 * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})<br> 
    … …  
    2324public class PredictionByPartialMatch extends TrieBasedModel { 
    2425 
    25         /** 
    26          * <p> 
    27          * Id for object serialization. 
    28          * </p> 
    29          */ 
    30         private static final long serialVersionUID = 1L; 
    31  
    32         /** 
    33          * <p> 
    34          * Minimum order of the Markov model. 
    35          * </p> 
    36          */ 
    37         protected int minOrder; 
    38  
    39         /** 
    40          * <p> 
    41          * Probability to use a lower-order Markov model 
    42          * </p> 
    43          */ 
    44         protected double probEscape; 
    45  
    46         /** 
    47          * <p> 
    48          * Constructor. Creates a new PredictionByPartialMatch model with a given 
    49          * Markov order and a default escape probability of 0.1. 
    50          * </p> 
    51          *  
    52          * @param markovOrder 
    53          *            Markov order of the model 
    54          * @param r 
    55          *            random number generator used by probabilistic methods of the 
    56          *            class 
    57          */ 
    58         public PredictionByPartialMatch(int markovOrder, Random r) { 
    59                 this(markovOrder, r, 0.1); 
    60         } 
    61  
    62         /** 
    63          * <p> 
    64          * Creates a new PredictionByPartialMatch model with a given Markov order 
    65          * and escape probability. 
    66          * </p> 
    67          *  
    68          * @param markovOrder 
    69          *            Markov order of the model 
    70          * @param r 
    71          *            random number generator used by probabilistic methods of the 
    72          *            class 
    73          * @param probEscape 
    74          *            escape probability used by the model 
    75          */ 
    76         public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) { 
    77                 this(markovOrder, 0, r, probEscape); 
    78         } 
    79  
    80         /** 
    81          * <p> 
    82          * Creates a new PredictionByPartialMatch model with a given Markov order 
    83          * and escape probability. 
    84          * </p> 
    85          *  
    86          * @param markovOrder 
    87          *            Markov order of the model 
    88          * @param minOrder 
    89          *            minimum order of the model; if this order is reached, there is 
    90          *            no escape 
    91          * @param r 
    92          *            random number generator used by probabilistic methods of the 
    93          *            class 
    94          * @param probEscape 
    95          *            escape probability used by the model 
    96          * @throws InvalidParameterException thrown if minOrder is less than 0 or greater than markovOrder or probEscape is not in the interval (0,1) 
    97          */ 
    98         public PredictionByPartialMatch(int markovOrder, int minOrder, Random r, 
    99                         double probEscape) { 
    100                 super(markovOrder, r); 
    101                 if( minOrder< 0 ) { 
    102                         throw new InvalidParameterException("minOrder must be greather than or equal to 0"); 
    103                 } 
    104                 if( minOrder>markovOrder) { 
    105                         throw new InvalidParameterException("minOrder must be less than or equal to markovOrder"); 
    106                 } 
    107                 if( probEscape<=0.0 || probEscape>=1.0) { 
    108                         throw new InvalidParameterException("probEscape must be in the interval (0,1)"); 
    109                 } 
    110                 this.probEscape = probEscape; 
    111                 this.minOrder = minOrder; 
    112         } 
    113  
    114         /** 
    115          * <p> 
    116          * Sets the escape probability of the model. 
    117          * </p> 
    118          *  
    119          * @param probEscape 
    120          *            new escape probability 
    121          */ 
    122         public void setProbEscape(double probEscape) { 
    123                 this.probEscape = probEscape; 
    124         } 
    125  
    126         /** 
    127          * <p> 
    128          * Returns the escape probability of the model. 
    129          * </p> 
    130          *  
    131          * @return escape probability of the model 
    132          */ 
    133         public double getProbEscape() { 
    134                 return probEscape; 
    135         } 
    136  
    137         /** 
    138          * <p> 
    139          * Calculates the probability of the next event based on the formula:<br> 
    140          * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} 
    141          * P_{MM^i}(X_n 
    142          * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... 
    143          * ,X_{n-min})<br> 
    144          * P_{MM^i} denotes the probability in an i-th order Markov model. 
    145          * </p> 
    146          *  
    147          * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
    148          *      de.ugoe.cs.quest.eventcore.Event) 
    149          */ 
    150         @Override 
    151         public double getProbability(List<Event> context, 
    152                         Event symbol) { 
    153                 if (context == null) { 
    154                         throw new InvalidParameterException("context must not be null"); 
    155                 } 
    156                 if (symbol == null) { 
    157                         throw new InvalidParameterException("symbol must not be null"); 
    158                 } 
    159                 double result = 0.0d; 
    160                 double resultCurrentContex = 0.0d; 
    161                 double resultShorterContex = 0.0d; 
    162  
    163                 List<Event> contextCopy; 
    164                 if (context.size() >= trieOrder) { 
    165                         contextCopy = new LinkedList<Event>(context.subList( 
    166                                         context.size() - trieOrder + 1, context.size())); 
    167                 } else { 
    168                         contextCopy = new LinkedList<Event>(context); 
    169                 } 
    170  
    171                 Collection<Event> followers = trie.getFollowingSymbols(contextCopy); // \Sigma' 
    172                 int sumCountFollowers = 0; // N(s\sigma') 
    173                 for (Event follower : followers) { 
    174                         sumCountFollowers += trie.getCount(contextCopy, follower); 
    175                 } 
    176  
    177                 int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) 
    178                 if (sumCountFollowers == 0) { 
    179                         resultCurrentContex = 0.0; 
    180                 } else { 
    181                         resultCurrentContex = (double) countSymbol / sumCountFollowers; 
    182                 } 
    183                 if (contextCopy.size() > minOrder) { 
    184                         resultCurrentContex *= (1 - probEscape); 
    185                         contextCopy.remove(0); 
    186                         if (contextCopy.size() >= minOrder) { 
    187                                 double probSuffix = getProbability(contextCopy, symbol); 
    188  
    189                                 if (followers.size() == 0) { 
    190                                         resultShorterContex = probSuffix; 
    191                                 } else { 
    192                                         resultShorterContex = probEscape * probSuffix; 
    193                                 } 
    194                         } 
    195                 } 
    196                 result = resultCurrentContex + resultShorterContex; 
    197  
    198                 return result; 
    199         } 
     26    /** 
     27     * <p> 
     28     * Id for object serialization. 
     29     * </p> 
     30     */ 
     31    private static final long serialVersionUID = 1L; 
     32 
     33    /** 
     34     * <p> 
     35     * Minimum order of the Markov model. 
     36     * </p> 
     37     */ 
     38    protected int minOrder; 
     39 
     40    /** 
     41     * <p> 
     42     * Probability to use a lower-order Markov model 
     43     * </p> 
     44     */ 
     45    protected double probEscape; 
     46 
     47    /** 
     48     * <p> 
     49     * Constructor. Creates a new PredictionByPartialMatch model with a given Markov order and a 
     50     * default escape probability of 0.1. 
     51     * </p> 
     52     *  
     53     * @param markovOrder 
     54     *            Markov order of the model 
     55     * @param r 
     56     *            random number generator used by probabilistic methods of the class 
     57     */ 
     58    public PredictionByPartialMatch(int markovOrder, Random r) { 
     59        this(markovOrder, r, 0.1); 
     60    } 
     61 
     62    /** 
     63     * <p> 
     64     * Creates a new PredictionByPartialMatch model with a given Markov order and escape 
     65     * probability. 
     66     * </p> 
     67     *  
     68     * @param markovOrder 
     69     *            Markov order of the model 
     70     * @param r 
     71     *            random number generator used by probabilistic methods of the class 
     72     * @param probEscape 
     73     *            escape probability used by the model 
     74     */ 
     75    public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) { 
     76        this(markovOrder, 0, r, probEscape); 
     77    } 
     78 
     79    /** 
     80     * <p> 
     81     * Creates a new PredictionByPartialMatch model with a given Markov order and escape 
     82     * probability. 
     83     * </p> 
     84     *  
     85     * @param markovOrder 
     86     *            Markov order of the model 
     87     * @param minOrder 
     88     *            minimum order of the model; if this order is reached, there is no escape 
     89     * @param r 
     90     *            random number generator used by probabilistic methods of the class 
     91     * @param probEscape 
     92     *            escape probability used by the model 
     93     * @throws InvalidParameterException 
     94     *             thrown if minOrder is less than 0 or greater than markovOrder or probEscape is 
     95     *             not in the interval (0,1) 
     96     */ 
     97    public PredictionByPartialMatch(int markovOrder, int minOrder, Random r, double probEscape) { 
     98        super(markovOrder, r); 
     99        if (minOrder < 0) { 
     100            throw new InvalidParameterException("minOrder must be greather than or equal to 0"); 
     101        } 
     102        if (minOrder > markovOrder) { 
     103            throw new InvalidParameterException( 
     104                                                "minOrder must be less than or equal to markovOrder"); 
     105        } 
     106        if (probEscape <= 0.0 || probEscape >= 1.0) { 
     107            throw new InvalidParameterException("probEscape must be in the interval (0,1)"); 
     108        } 
     109        this.probEscape = probEscape; 
     110        this.minOrder = minOrder; 
     111    } 
     112 
     113    /** 
     114     * <p> 
     115     * Sets the escape probability of the model. 
     116     * </p> 
     117     *  
     118     * @param probEscape 
     119     *            new escape probability 
     120     */ 
     121    public void setProbEscape(double probEscape) { 
     122        this.probEscape = probEscape; 
     123    } 
     124 
     125    /** 
     126     * <p> 
     127     * Returns the escape probability of the model. 
     128     * </p> 
     129     *  
     130     * @return escape probability of the model 
     131     */ 
     132    public double getProbEscape() { 
     133        return probEscape; 
     134    } 
     135 
     136    /** 
     137     * <p> 
     138     * Calculates the probability of the next event based on the formula:<br> 
     139     * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n 
     140     * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})<br> 
     141     * P_{MM^i} denotes the probability in an i-th order Markov model. 
     142     * </p> 
     143     *  
     144     * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
     145     *      de.ugoe.cs.quest.eventcore.Event) 
     146     */ 
     147    @Override 
     148    public double getProbability(List<Event> context, Event symbol) { 
     149        if (context == null) { 
     150            throw new InvalidParameterException("context must not be null"); 
     151        } 
     152        if (symbol == null) { 
     153            throw new InvalidParameterException("symbol must not be null"); 
     154        } 
     155        double result = 0.0d; 
     156        double resultCurrentContex = 0.0d; 
     157        double resultShorterContex = 0.0d; 
     158 
     159        List<Event> contextCopy; 
     160        if (context.size() >= trieOrder) { 
     161            contextCopy = 
     162                new LinkedList<Event>(context.subList(context.size() - trieOrder + 1, 
     163                                                      context.size())); 
     164        } 
     165        else { 
     166            contextCopy = new LinkedList<Event>(context); 
     167        } 
     168 
     169        Collection<Event> followers = trie.getFollowingSymbols(contextCopy); // \Sigma' 
     170        int sumCountFollowers = 0; // N(s\sigma') 
     171        for (Event follower : followers) { 
     172            sumCountFollowers += trie.getCount(contextCopy, follower); 
     173        } 
     174 
     175        int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) 
     176        if (sumCountFollowers == 0) { 
     177            resultCurrentContex = 0.0; 
     178        } 
     179        else { 
     180            resultCurrentContex = (double) countSymbol / sumCountFollowers; 
     181        } 
     182        if (contextCopy.size() > minOrder) { 
     183            resultCurrentContex *= (1 - probEscape); 
     184            contextCopy.remove(0); 
     185            if (contextCopy.size() >= minOrder) { 
     186                double probSuffix = getProbability(contextCopy, symbol); 
     187 
     188                if (followers.size() == 0) { 
     189                    resultShorterContex = probSuffix; 
     190                } 
     191                else { 
     192                    resultShorterContex = probEscape * probSuffix; 
     193                } 
     194            } 
     195        } 
     196        result = resultCurrentContex + resultShorterContex; 
     197 
     198        return result; 
     199    } 
    200200} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java

    r518 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1718/** 
    1819 * <p> 
    19  * This class implements a <it>trie</it>, i.e., a tree of sequences that the 
    20  * occurence of subsequences up to a predefined length. This length is the trie 
    21  * order. 
     20 * This class implements a <it>trie</it>, i.e., a tree of sequences that the occurence of 
     21 * subsequences up to a predefined length. This length is the trie order. 
    2222 * </p> 
    2323 *  
    … …  
    3131public class Trie<T> implements IDotCompatible, Serializable { 
    3232 
    33         /** 
    34          * <p> 
    35          * Id for object serialization. 
    36          * </p> 
    37          */ 
    38         private static final long serialVersionUID = 1L; 
    39  
    40         /** 
    41          * <p> 
    42          * Collection of all symbols occuring in the trie. 
    43          * </p> 
    44          */ 
    45         private Collection<T> knownSymbols; 
    46  
    47         /** 
    48          * <p> 
    49          * Reference to the root of the trie. 
    50          * </p> 
    51          */ 
    52         private final TrieNode<T> rootNode; 
    53  
    54         /** 
    55          * <p> 
    56          * Contructor. Creates a new Trie. 
    57          * </p> 
    58          */ 
    59         public Trie() { 
    60                 rootNode = new TrieNode<T>(); 
    61                 knownSymbols = new LinkedHashSet<T>(); 
    62         } 
    63  
    64         /** 
    65          * <p> 
    66          * Copy-Constructor. Creates a new Trie as the copy of other. The other trie 
    67          * must noch be null. 
    68          * </p> 
    69          *  
    70          * @param other 
    71          *            Trie that is copied 
    72          */ 
    73         public Trie(Trie<T> other) { 
    74                 if (other == null) { 
    75                         throw new InvalidParameterException("other trie must not be null"); 
    76                 } 
    77                 rootNode = new TrieNode<T>(other.rootNode); 
    78                 knownSymbols = new LinkedHashSet<T>(other.knownSymbols); 
    79         } 
    80  
    81         /** 
    82          * <p> 
    83          * Returns a collection of all symbols occuring in the trie. 
    84          * </p> 
    85          *  
    86          * @return symbols occuring in the trie 
    87          */ 
    88         public Collection<T> getKnownSymbols() { 
    89                 return new LinkedHashSet<T>(knownSymbols); 
    90         } 
    91  
    92         /** 
    93          * <p> 
    94          * Trains the current trie using the given sequence and adds all subsequence 
    95          * of length {@code maxOrder}. 
    96          * </p> 
    97          *  
    98          * @param sequence 
    99          *            sequence whose subsequences are added to the trie 
    100          * @param maxOrder 
    101          *            maximum length of the subsequences added to the trie 
    102          */ 
    103         public void train(List<T> sequence, int maxOrder) { 
    104                 if (maxOrder < 1) { 
    105                         return; 
    106                 } 
    107                 IncompleteMemory<T> latestActions = new IncompleteMemory<T>(maxOrder); 
    108                 int i = 0; 
    109                 for (T currentEvent : sequence) { 
    110                         latestActions.add(currentEvent); 
    111                         knownSymbols.add(currentEvent); 
    112                         i++; 
    113                         if (i >= maxOrder) { 
    114                                 add(latestActions.getLast(maxOrder)); 
    115                         } 
    116                 } 
    117                 int sequenceLength = sequence.size(); 
    118                 for (int j = maxOrder - 1; j > 0; j--) { 
    119                         add(sequence.subList(sequenceLength - j, sequenceLength)); 
    120                 } 
    121         } 
    122  
    123         /** 
    124          * <p> 
    125          * Adds a given subsequence to the trie and increases the counters 
    126          * accordingly. 
    127          * </p> 
    128          *  
    129          * @param subsequence 
    130          *            subsequence whose counters are increased 
    131          * @see TrieNode#add(List) 
    132          */ 
    133         protected void add(List<T> subsequence) { 
    134                 if (subsequence != null && !subsequence.isEmpty()) { 
    135                         knownSymbols.addAll(subsequence); 
    136                         subsequence = new LinkedList<T>(subsequence); // defensive copy! 
    137                         T firstSymbol = subsequence.get(0); 
    138                         TrieNode<T> node = getChildCreate(firstSymbol); 
    139                         node.add(subsequence); 
    140                 } 
    141         } 
    142  
    143         /** 
    144          * <p> 
    145          * Returns the child of the root node associated with the given symbol or 
    146          * creates it if it does not exist yet. 
    147          * </p> 
    148          *  
    149          * @param symbol 
    150          *            symbol whose node is required 
    151          * @return node associated with the symbol 
    152          * @see TrieNode#getChildCreate(Object) 
    153          */ 
    154         protected TrieNode<T> getChildCreate(T symbol) { 
    155                 return rootNode.getChildCreate(symbol); 
    156         } 
    157  
    158         /** 
    159          * <p> 
    160          * Returns the child of the root node associated with the given symbol or 
    161          * null if it does not exist. 
    162          * </p> 
    163          *  
    164          * @param symbol 
    165          *            symbol whose node is required 
    166          * @return node associated with the symbol; null if no such node exists 
    167          * @see TrieNode#getChild(Object) 
    168          */ 
    169         protected TrieNode<T> getChild(T symbol) { 
    170                 return rootNode.getChild(symbol); 
    171         } 
    172  
    173         /** 
    174          * <p> 
    175          * Returns the number of occurences of the given sequence. 
    176          * </p> 
    177          *  
    178          * @param sequence 
    179          *            sequence whose number of occurences is required 
    180          * @return number of occurences of the sequence 
    181          */ 
    182         public int getCount(List<T> sequence) { 
    183                 int count = 0; 
    184                 TrieNode<T> node = find(sequence); 
    185                 if (node != null) { 
    186                         count = node.getCount(); 
    187                 } 
    188                 return count; 
    189         } 
    190  
    191         /** 
    192          * <p> 
    193          * Returns the number of occurences of the given prefix and a symbol that 
    194          * follows it.<br> 
    195          * Convenience function to simplify usage of {@link #getCount(List)}. 
    196          * </p> 
    197          *  
    198          * @param sequence 
    199          *            prefix of the sequence 
    200          * @param follower 
    201          *            suffix of the sequence 
    202          * @return number of occurences of the sequence 
    203          * @see #getCount(List) 
    204          */ 
    205         public int getCount(List<T> sequence, T follower) { 
    206                 List<T> tmpSequence = new LinkedList<T>(sequence); 
    207                 tmpSequence.add(follower); 
    208                 return getCount(tmpSequence); 
    209  
    210         } 
    211  
    212         /** 
    213          * <p> 
    214          * Searches the trie for a given sequence and returns the node associated 
    215          * with the sequence or null if no such node is found. 
    216          * </p> 
    217          *  
    218          * @param sequence 
    219          *            sequence that is searched for 
    220          * @return node associated with the sequence 
    221          * @see TrieNode#find(List) 
    222          */ 
    223         public TrieNode<T> find(List<T> sequence) { 
    224                 if (sequence == null || sequence.isEmpty()) { 
    225                         return rootNode; 
    226                 } 
    227                 List<T> sequenceCopy = new LinkedList<T>(sequence); 
    228                 TrieNode<T> result = null; 
    229                 TrieNode<T> node = getChild(sequenceCopy.get(0)); 
    230                 if (node != null) { 
    231                         sequenceCopy.remove(0); 
    232                         result = node.find(sequenceCopy); 
    233                 } 
    234                 return result; 
    235         } 
    236  
    237         /** 
    238          * <p> 
    239          * Returns a collection of all symbols that follow a given sequence in the 
    240          * trie. In case the sequence is not found or no symbols follow the sequence 
    241          * the result will be empty. 
    242          * </p> 
    243          *  
    244          * @param sequence 
    245          *            sequence whose followers are returned 
    246          * @return symbols following the given sequence 
    247          * @see TrieNode#getFollowingSymbols() 
    248          */ 
    249         public Collection<T> getFollowingSymbols(List<T> sequence) { 
    250                 Collection<T> result = new LinkedList<T>(); 
    251                 TrieNode<T> node = find(sequence); 
    252                 if (node != null) { 
    253                         result = node.getFollowingSymbols(); 
    254                 } 
    255                 return result; 
    256         } 
    257  
    258         /** 
    259          * <p> 
    260          * Returns the longest suffix of the given context that is contained in the 
    261          * tree and whose children are leaves. 
    262          * </p> 
    263          *  
    264          * @param context 
    265          *            context whose suffix is searched for 
    266          * @return longest suffix of the context 
    267          */ 
    268         public List<T> getContextSuffix(List<T> context) { 
    269                 List<T> contextSuffix; 
    270                 if (context != null) { 
    271                         contextSuffix = new LinkedList<T>(context); // defensive copy 
    272                 } else { 
    273                         contextSuffix = new LinkedList<T>(); 
    274                 } 
    275                 boolean suffixFound = false; 
    276  
    277                 while (!suffixFound) { 
    278                         if (contextSuffix.isEmpty()) { 
    279                                 suffixFound = true; // suffix is the empty word 
    280                         } else { 
    281                                 TrieNode<T> node = find(contextSuffix); 
    282                                 if (node != null) { 
    283                                         if (!node.getFollowingSymbols().isEmpty()) { 
    284                                                 suffixFound = true; 
    285                                         } 
    286                                 } 
    287                                 if (!suffixFound) { 
    288                                         contextSuffix.remove(0); 
    289                                 } 
    290                         } 
    291                 } 
    292  
    293                 return contextSuffix; 
    294         } 
    295  
    296         /** 
    297          * <p> 
    298          * Helper class for graph visualization of a trie. 
    299          * </p> 
    300          *  
    301          * @author Steffen Herbold 
    302          * @version 1.0 
    303          */ 
    304         static public class Edge { 
    305         } 
    306  
    307         /** 
    308          * <p> 
    309          * Helper class for graph visualization of a trie. 
    310          * </p> 
    311          *  
    312          * @author Steffen Herbold 
    313          * @version 1.0 
    314          */ 
    315         static public class TrieVertex { 
    316  
    317                 /** 
    318                  * <p> 
    319                  * Id of the vertex. 
    320                  * </p> 
    321                  */ 
    322                 private String id; 
    323  
    324                 /** 
    325                  * <p> 
    326                  * Contructor. Creates a new TrieVertex. 
    327                  * </p> 
    328                  *  
    329                  * @param id 
    330                  *            id of the vertex 
    331                  */ 
    332                 protected TrieVertex(String id) { 
    333                         this.id = id; 
    334                 } 
    335  
    336                 /** 
    337                  * <p> 
    338                  * Returns the id of the vertex. 
    339                  * </p> 
    340                  *  
    341                  * @see java.lang.Object#toString() 
    342                  */ 
    343                 @Override 
    344                 public String toString() { 
    345                         return id; 
    346                 } 
    347         } 
    348  
    349         /** 
    350          * <p> 
    351          * Returns a {@link Graph} representation of the trie. 
    352          * </p> 
    353          *  
    354          * @return {@link Graph} representation of the trie 
    355          */ 
    356         protected Tree<TrieVertex, Edge> getGraph() { 
    357                 DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>(); 
    358                 rootNode.getGraph(null, graph); 
    359                 return graph; 
    360         } 
    361  
    362         /* 
    363          * (non-Javadoc) 
    364          *  
    365          * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() 
    366          */ 
    367         public String getDotRepresentation() { 
    368                 StringBuilder stringBuilder = new StringBuilder(); 
    369                 stringBuilder.append("digraph model {" + StringTools.ENDLINE); 
    370                 rootNode.appendDotRepresentation(stringBuilder); 
    371                 stringBuilder.append('}' + StringTools.ENDLINE); 
    372                 return stringBuilder.toString(); 
    373         } 
    374  
    375         /** 
    376          * <p> 
    377          * Returns the string representation of the root node. 
    378          * </p> 
    379          *  
    380          * @see TrieNode#toString() 
    381          * @see java.lang.Object#toString() 
    382          */ 
    383         @Override 
    384         public String toString() { 
    385                 return rootNode.toString(); 
    386         } 
    387  
    388         /** 
    389          * <p> 
    390          * Returns the number of symbols contained in the trie. 
    391          * </p> 
    392          *  
    393          * @return number of symbols contained in the trie 
    394          */ 
    395         public int getNumSymbols() { 
    396                 return knownSymbols.size(); 
    397         } 
    398  
    399         /** 
    400          * <p> 
    401          * Returns the number of trie nodes that are ancestors of a leaf. This is 
    402          * the equivalent to the number of states a first-order markov model would 
    403          * have. 
    404          * <p> 
    405          *  
    406          * @return number of trie nodes that are ancestors of leafs. 
    407          */ 
    408         public int getNumLeafAncestors() { 
    409                 List<TrieNode<T>> ancestors = new LinkedList<TrieNode<T>>(); 
    410                 rootNode.getLeafAncestors(ancestors); 
    411                 return ancestors.size(); 
    412         } 
    413  
    414         /** 
    415          * <p> 
    416          * Returns the number of trie nodes that are leafs. 
    417          * </p> 
    418          *  
    419          * @return number of leafs in the trie 
    420          */ 
    421         public int getNumLeafs() { 
    422                 return rootNode.getNumLeafs(); 
    423         } 
    424  
    425         /** 
    426          * <p> 
    427          * Updates the list of known symbols by replacing it with all symbols that 
    428          * are found in the child nodes of the root node. This should be the same as 
    429          * all symbols that are contained in the trie. 
    430          * </p> 
    431          */ 
    432         public void updateKnownSymbols() { 
    433                 knownSymbols = new HashSet<T>(); 
    434                 for (TrieNode<T> node : rootNode.getChildren()) { 
    435                         knownSymbols.add(node.getSymbol()); 
    436                 } 
    437         } 
    438  
    439         /** 
    440          * <p> 
    441          * Two Tries are defined as equal, if their {@link #rootNode} are equal. 
    442          * </p> 
    443          *  
    444          * @see java.lang.Object#equals(java.lang.Object) 
    445          */ 
    446         @SuppressWarnings("rawtypes") 
    447         @Override 
    448         public boolean equals(Object other) { 
    449                 if (other == this) { 
    450                         return true; 
    451                 } 
    452                 if (other instanceof Trie) { 
    453                         return rootNode.equals(((Trie) other).rootNode); 
    454                 } 
    455                 return false; 
    456         } 
    457          
    458         /* 
    459          * (non-Javadoc) 
    460          *  
    461          * @see java.lang.Object#hashCode() 
    462          */ 
    463         @Override 
    464         public int hashCode() { 
    465                 int multiplier = 17; 
    466                 int hash = 42; 
    467                 if (rootNode != null) { 
    468                         hash = multiplier * hash + rootNode.hashCode(); 
    469                 } 
    470                 return hash; 
    471         } 
     33    /** 
     34     * <p> 
     35     * Id for object serialization. 
     36     * </p> 
     37     */ 
     38    private static final long serialVersionUID = 1L; 
     39 
     40    /** 
     41     * <p> 
     42     * Collection of all symbols occuring in the trie. 
     43     * </p> 
     44     */ 
     45    private Collection<T> knownSymbols; 
     46 
     47    /** 
     48     * <p> 
     49     * Reference to the root of the trie. 
     50     * </p> 
     51     */ 
     52    private final TrieNode<T> rootNode; 
     53 
     54    /** 
     55     * <p> 
     56     * Contructor. Creates a new Trie. 
     57     * </p> 
     58     */ 
     59    public Trie() { 
     60        rootNode = new TrieNode<T>(); 
     61        knownSymbols = new LinkedHashSet<T>(); 
     62    } 
     63 
     64    /** 
     65     * <p> 
     66     * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must noch be null. 
     67     * </p> 
     68     *  
     69     * @param other 
     70     *            Trie that is copied 
     71     */ 
     72    public Trie(Trie<T> other) { 
     73        if (other == null) { 
     74            throw new InvalidParameterException("other trie must not be null"); 
     75        } 
     76        rootNode = new TrieNode<T>(other.rootNode); 
     77        knownSymbols = new LinkedHashSet<T>(other.knownSymbols); 
     78    } 
     79 
     80    /** 
     81     * <p> 
     82     * Returns a collection of all symbols occuring in the trie. 
     83     * </p> 
     84     *  
     85     * @return symbols occuring in the trie 
     86     */ 
     87    public Collection<T> getKnownSymbols() { 
     88        return new LinkedHashSet<T>(knownSymbols); 
     89    } 
     90 
     91    /** 
     92     * <p> 
     93     * Trains the current trie using the given sequence and adds all subsequence of length 
     94     * {@code maxOrder}. 
     95     * </p> 
     96     *  
     97     * @param sequence 
     98     *            sequence whose subsequences are added to the trie 
     99     * @param maxOrder 
     100     *            maximum length of the subsequences added to the trie 
     101     */ 
     102    public void train(List<T> sequence, int maxOrder) { 
     103        if (maxOrder < 1) { 
     104            return; 
     105        } 
     106        IncompleteMemory<T> latestActions = new IncompleteMemory<T>(maxOrder); 
     107        int i = 0; 
     108        for (T currentEvent : sequence) { 
     109            latestActions.add(currentEvent); 
     110            knownSymbols.add(currentEvent); 
     111            i++; 
     112            if (i >= maxOrder) { 
     113                add(latestActions.getLast(maxOrder)); 
     114            } 
     115        } 
     116        int sequenceLength = sequence.size(); 
     117        for (int j = maxOrder - 1; j > 0; j--) { 
     118            add(sequence.subList(sequenceLength - j, sequenceLength)); 
     119        } 
     120    } 
     121 
     122    /** 
     123     * <p> 
     124     * Adds a given subsequence to the trie and increases the counters accordingly. 
     125     * </p> 
     126     *  
     127     * @param subsequence 
     128     *            subsequence whose counters are increased 
     129     * @see TrieNode#add(List) 
     130     */ 
     131    protected void add(List<T> subsequence) { 
     132        if (subsequence != null && !subsequence.isEmpty()) { 
     133            knownSymbols.addAll(subsequence); 
     134            subsequence = new LinkedList<T>(subsequence); // defensive copy! 
     135            T firstSymbol = subsequence.get(0); 
     136            TrieNode<T> node = getChildCreate(firstSymbol); 
     137            node.add(subsequence); 
     138        } 
     139    } 
     140 
     141    /** 
     142     * <p> 
     143     * Returns the child of the root node associated with the given symbol or creates it if it does 
     144     * not exist yet. 
     145     * </p> 
     146     *  
     147     * @param symbol 
     148     *            symbol whose node is required 
     149     * @return node associated with the symbol 
     150     * @see TrieNode#getChildCreate(Object) 
     151     */ 
     152    protected TrieNode<T> getChildCreate(T symbol) { 
     153        return rootNode.getChildCreate(symbol); 
     154    } 
     155 
     156    /** 
     157     * <p> 
     158     * Returns the child of the root node associated with the given symbol or null if it does not 
     159     * exist. 
     160     * </p> 
     161     *  
     162     * @param symbol 
     163     *            symbol whose node is required 
     164     * @return node associated with the symbol; null if no such node exists 
     165     * @see TrieNode#getChild(Object) 
     166     */ 
     167    protected TrieNode<T> getChild(T symbol) { 
     168        return rootNode.getChild(symbol); 
     169    } 
     170 
     171    /** 
     172     * <p> 
     173     * Returns the number of occurences of the given sequence. 
     174     * </p> 
     175     *  
     176     * @param sequence 
     177     *            sequence whose number of occurences is required 
     178     * @return number of occurences of the sequence 
     179     */ 
     180    public int getCount(List<T> sequence) { 
     181        int count = 0; 
     182        TrieNode<T> node = find(sequence); 
     183        if (node != null) { 
     184            count = node.getCount(); 
     185        } 
     186        return count; 
     187    } 
     188 
     189    /** 
     190     * <p> 
     191     * Returns the number of occurences of the given prefix and a symbol that follows it.<br> 
     192     * Convenience function to simplify usage of {@link #getCount(List)}. 
     193     * </p> 
     194     *  
     195     * @param sequence 
     196     *            prefix of the sequence 
     197     * @param follower 
     198     *            suffix of the sequence 
     199     * @return number of occurences of the sequence 
     200     * @see #getCount(List) 
     201     */ 
     202    public int getCount(List<T> sequence, T follower) { 
     203        List<T> tmpSequence = new LinkedList<T>(sequence); 
     204        tmpSequence.add(follower); 
     205        return getCount(tmpSequence); 
     206 
     207    } 
     208 
     209    /** 
     210     * <p> 
     211     * Searches the trie for a given sequence and returns the node associated with the sequence or 
     212     * null if no such node is found. 
     213     * </p> 
     214     *  
     215     * @param sequence 
     216     *            sequence that is searched for 
     217     * @return node associated with the sequence 
     218     * @see TrieNode#find(List) 
     219     */ 
     220    public TrieNode<T> find(List<T> sequence) { 
     221        if (sequence == null || sequence.isEmpty()) { 
     222            return rootNode; 
     223        } 
     224        List<T> sequenceCopy = new LinkedList<T>(sequence); 
     225        TrieNode<T> result = null; 
     226        TrieNode<T> node = getChild(sequenceCopy.get(0)); 
     227        if (node != null) { 
     228            sequenceCopy.remove(0); 
     229            result = node.find(sequenceCopy); 
     230        } 
     231        return result; 
     232    } 
     233 
     234    /** 
     235     * <p> 
     236     * Returns a collection of all symbols that follow a given sequence in the trie. In case the 
     237     * sequence is not found or no symbols follow the sequence the result will be empty. 
     238     * </p> 
     239     *  
     240     * @param sequence 
     241     *            sequence whose followers are returned 
     242     * @return symbols following the given sequence 
     243     * @see TrieNode#getFollowingSymbols() 
     244     */ 
     245    public Collection<T> getFollowingSymbols(List<T> sequence) { 
     246        Collection<T> result = new LinkedList<T>(); 
     247        TrieNode<T> node = find(sequence); 
     248        if (node != null) { 
     249            result = node.getFollowingSymbols(); 
     250        } 
     251        return result; 
     252    } 
     253 
     254    /** 
     255     * <p> 
     256     * Returns the longest suffix of the given context that is contained in the tree and whose 
     257     * children are leaves. 
     258     * </p> 
     259     *  
     260     * @param context 
     261     *            context whose suffix is searched for 
     262     * @return longest suffix of the context 
     263     */ 
     264    public List<T> getContextSuffix(List<T> context) { 
     265        List<T> contextSuffix; 
     266        if (context != null) { 
     267            contextSuffix = new LinkedList<T>(context); // defensive copy 
     268        } 
     269        else { 
     270            contextSuffix = new LinkedList<T>(); 
     271        } 
     272        boolean suffixFound = false; 
     273 
     274        while (!suffixFound) { 
     275            if (contextSuffix.isEmpty()) { 
     276                suffixFound = true; // suffix is the empty word 
     277            } 
     278            else { 
     279                TrieNode<T> node = find(contextSuffix); 
     280                if (node != null) { 
     281                    if (!node.getFollowingSymbols().isEmpty()) { 
     282                        suffixFound = true; 
     283                    } 
     284                } 
     285                if (!suffixFound) { 
     286                    contextSuffix.remove(0); 
     287                } 
     288            } 
     289        } 
     290 
     291        return contextSuffix; 
     292    } 
     293 
     294    /** 
     295     * <p> 
     296     * Helper class for graph visualization of a trie. 
     297     * </p> 
     298     *  
     299     * @author Steffen Herbold 
     300     * @version 1.0 
     301     */ 
     302    static public class Edge {} 
     303 
     304    /** 
     305     * <p> 
     306     * Helper class for graph visualization of a trie. 
     307     * </p> 
     308     *  
     309     * @author Steffen Herbold 
     310     * @version 1.0 
     311     */ 
     312    static public class TrieVertex { 
     313 
     314        /** 
     315         * <p> 
     316         * Id of the vertex. 
     317         * </p> 
     318         */ 
     319        private String id; 
     320 
     321        /** 
     322         * <p> 
     323         * Contructor. Creates a new TrieVertex. 
     324         * </p> 
     325         *  
     326         * @param id 
     327         *            id of the vertex 
     328         */ 
     329        protected TrieVertex(String id) { 
     330            this.id = id; 
     331        } 
     332 
     333        /** 
     334         * <p> 
     335         * Returns the id of the vertex. 
     336         * </p> 
     337         *  
     338         * @see java.lang.Object#toString() 
     339         */ 
     340        @Override 
     341        public String toString() { 
     342            return id; 
     343        } 
     344    } 
     345 
     346    /** 
     347     * <p> 
     348     * Returns a {@link Graph} representation of the trie. 
     349     * </p> 
     350     *  
     351     * @return {@link Graph} representation of the trie 
     352     */ 
     353    protected Tree<TrieVertex, Edge> getGraph() { 
     354        DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>(); 
     355        rootNode.getGraph(null, graph); 
     356        return graph; 
     357    } 
     358 
     359    /* 
     360     * (non-Javadoc) 
     361     *  
     362     * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() 
     363     */ 
     364    public String getDotRepresentation() { 
     365        StringBuilder stringBuilder = new StringBuilder(); 
     366        stringBuilder.append("digraph model {" + StringTools.ENDLINE); 
     367        rootNode.appendDotRepresentation(stringBuilder); 
     368        stringBuilder.append('}' + StringTools.ENDLINE); 
     369        return stringBuilder.toString(); 
     370    } 
     371 
     372    /** 
     373     * <p> 
     374     * Returns the string representation of the root node. 
     375     * </p> 
     376     *  
     377     * @see TrieNode#toString() 
     378     * @see java.lang.Object#toString() 
     379     */ 
     380    @Override 
     381    public String toString() { 
     382        return rootNode.toString(); 
     383    } 
     384 
     385    /** 
     386     * <p> 
     387     * Returns the number of symbols contained in the trie. 
     388     * </p> 
     389     *  
     390     * @return number of symbols contained in the trie 
     391     */ 
     392    public int getNumSymbols() { 
     393        return knownSymbols.size(); 
     394    } 
     395 
     396    /** 
     397     * <p> 
     398     * Returns the number of trie nodes that are ancestors of a leaf. This is the equivalent to the 
     399     * number of states a first-order markov model would have. 
     400     * <p> 
     401     *  
     402     * @return number of trie nodes that are ancestors of leafs. 
     403     */ 
     404    public int getNumLeafAncestors() { 
     405        List<TrieNode<T>> ancestors = new LinkedList<TrieNode<T>>(); 
     406        rootNode.getLeafAncestors(ancestors); 
     407        return ancestors.size(); 
     408    } 
     409 
     410    /** 
     411     * <p> 
     412     * Returns the number of trie nodes that are leafs. 
     413     * </p> 
     414     *  
     415     * @return number of leafs in the trie 
     416     */ 
     417    public int getNumLeafs() { 
     418        return rootNode.getNumLeafs(); 
     419    } 
     420 
     421    /** 
     422     * <p> 
     423     * Updates the list of known symbols by replacing it with all symbols that are found in the 
     424     * child nodes of the root node. This should be the same as all symbols that are contained in 
     425     * the trie. 
     426     * </p> 
     427     */ 
     428    public void updateKnownSymbols() { 
     429        knownSymbols = new HashSet<T>(); 
     430        for (TrieNode<T> node : rootNode.getChildren()) { 
     431            knownSymbols.add(node.getSymbol()); 
     432        } 
     433    } 
     434 
     435    /** 
     436     * <p> 
     437     * Two Tries are defined as equal, if their {@link #rootNode} are equal. 
     438     * </p> 
     439     *  
     440     * @see java.lang.Object#equals(java.lang.Object) 
     441     */ 
     442    @SuppressWarnings("rawtypes") 
     443    @Override 
     444    public boolean equals(Object other) { 
     445        if (other == this) { 
     446            return true; 
     447        } 
     448        if (other instanceof Trie) { 
     449            return rootNode.equals(((Trie) other).rootNode); 
     450        } 
     451        return false; 
     452    } 
     453 
     454    /* 
     455     * (non-Javadoc) 
     456     *  
     457     * @see java.lang.Object#hashCode() 
     458     */ 
     459    @Override 
     460    public int hashCode() { 
     461        int multiplier = 17; 
     462        int hash = 42; 
     463        if (rootNode != null) { 
     464            hash = multiplier * hash + rootNode.hashCode(); 
     465        } 
     466        return hash; 
     467    } 
    472468} 

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java

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

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java

    r518 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1516/** 
    1617 * <p> 
    17  * This class implements a node of a trie. Each node is associated with a symbol 
    18  * and has a counter. The counter marks the number of occurences of the sequence 
    19  * defined by the path from the root of the trie to this node. 
     18 * This class implements a node of a trie. Each node is associated with a symbol and has a counter. 
     19 * The counter marks the number of occurences of the sequence defined by the path from the root of 
     20 * the trie to this node. 
    2021 * </p> 
    2122 *  
    … …  
    2829class TrieNode<T> implements Serializable { 
    2930 
    30         /** 
    31          * <p> 
    32          * Id for object serialization. 
    33          * </p> 
    34          */ 
    35         private static final long serialVersionUID = 1L; 
    36  
    37         /** 
    38          * <p> 
    39          * Counter for the number of occurences of the sequence. 
    40          * </p> 
    41          */ 
    42         private int count; 
    43  
    44         /** 
    45          * <p> 
    46          * Symbol associated with the node. 
    47          * </p> 
    48          */ 
    49         private final T symbol; 
    50  
    51         /** 
    52          * <p> 
    53          * Child nodes of this node. If the node is a leaf this collection is empty. 
    54          * </p> 
    55          */ 
    56         private Collection<TrieNode<T>> children; 
    57  
    58         /** 
    59          * <p> 
    60          * Constructor. Creates a new TrieNode without a symbol associated.<br> 
    61          * <b>This constructor should only be used to create the root node of the 
    62          * trie!</b> 
    63          * </p> 
    64          */ 
    65         TrieNode() { 
    66                 this.symbol = null; 
    67                 count = 0; 
    68                 children = new LinkedList<TrieNode<T>>(); 
    69         } 
    70  
    71         /** 
    72          * <p> 
    73          * Constructor. Creates a new TrieNode. The symbol must not be null. 
    74          * </p> 
    75          *  
    76          * @param symbol 
    77          *            symbol associated with the trie node 
    78          */ 
    79         TrieNode(T symbol) { 
    80                 if (symbol == null) { 
    81                         throw new InvalidParameterException( 
    82                                         "symbol must not be null. null is reserved for root node!"); 
    83                 } 
    84                 this.symbol = symbol; 
    85                 count = 0; 
    86                 children = new LinkedList<TrieNode<T>>(); 
    87         } 
    88  
    89         /** 
    90          * <p> 
    91          * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not 
    92          * be null. 
    93          * </p> 
    94          *  
    95          * @param other 
    96          */ 
    97         TrieNode(TrieNode<T> other) { 
    98                 if (other == null) { 
    99                         throw new InvalidParameterException("other must not be null"); 
    100                 } 
    101                 symbol = other.symbol; 
    102                 count = other.count; 
    103                 children = new LinkedList<TrieNode<T>>(); 
    104                 for (TrieNode<T> child : other.children) { 
    105                         children.add(new TrieNode<T>(child)); 
    106                 } 
    107         } 
    108  
    109         /** 
    110          * <p> 
    111          * Adds a given subsequence to the trie and increases the counters 
    112          * accordingly. 
    113          * </p> 
    114          *  
    115          * @param subsequence 
    116          *            subsequence whose counters are increased 
    117          * @see Trie#add(List) 
    118          */ 
    119         public void add(List<T> subsequence) { 
    120                 if (!subsequence.isEmpty()) { 
    121                         if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by 
    122                                                                                                                 // the 
    123                                                                                                                 // recursion/TrieRoot! 
    124                                 throw new AssertionError("Invalid trie operation!"); 
    125                         } 
    126                         count++; 
    127                         subsequence.remove(0); 
    128                         if (!subsequence.isEmpty()) { 
    129                                 T nextSymbol = subsequence.get(0); 
    130                                 getChildCreate(nextSymbol).add(subsequence); 
    131                         } 
    132                 } 
    133         } 
    134  
    135         /** 
    136          * <p> 
    137          * Returns the symbol associated with the node. 
    138          * </p> 
    139          *  
    140          * @return symbol associated with the node 
    141          */ 
    142         public T getSymbol() { 
    143                 return symbol; 
    144         } 
    145  
    146         /** 
    147          * <p> 
    148          * Returns the number of occurences of the sequence represented by the node. 
    149          * </p> 
    150          *  
    151          * @return number of occurences of the sequence represented by the node 
    152          */ 
    153         public int getCount() { 
    154                 return count; 
    155         } 
    156  
    157         /** 
    158          * <p> 
    159          * Returns the child of the node associated with the given symbol or creates 
    160          * it if it does not exist yet. 
    161          * </p> 
    162          *  
    163          * @param symbol 
    164          *            symbol whose node is required 
    165          * @return node associated with the symbol 
    166          * @see Trie#getChildCreate(Object) 
    167          */ 
    168         protected TrieNode<T> getChildCreate(T symbol) { 
    169                 TrieNode<T> node = getChild(symbol); 
    170                 if (node == null) { 
    171                         node = new TrieNode<T>(symbol); 
    172                         children.add(node); 
    173                 } 
    174                 return node; 
    175         } 
    176  
    177         /** 
    178          * <p> 
    179          * Returns the child of the node associated with the given symbol or null if 
    180          * it does not exist. 
    181          * </p> 
    182          *  
    183          * @param symbol 
    184          *            symbol whose node is required 
    185          * @return node associated with the symbol; null if no such node exists 
    186          * @see Trie#getChild(Object) 
    187          */ 
    188         protected TrieNode<T> getChild(T symbol) { 
    189                 for (TrieNode<T> child : children) { 
    190                         if (child.getSymbol().equals(symbol)) { 
    191                                 return child; 
    192                         } 
    193                 } 
    194                 return null; 
    195         } 
    196  
    197         /** 
    198          * <p> 
    199          * Returns all children of this node. 
    200          * </p> 
    201          *  
    202          * @return children of this node 
    203          */ 
    204         protected Collection<TrieNode<T>> getChildren() { 
    205                 return children; 
    206         } 
    207  
    208         /** 
    209          * <p> 
    210          * Searches the sub-trie of this trie node for a given sequence and returns 
    211          * the node associated with the sequence or null if no such node is found. 
    212          * </p> 
    213          *  
    214          * @param sequence 
    215          *            sequence that is searched for 
    216          * @return node associated with the sequence 
    217          * @see Trie#find(List) 
    218          */ 
    219         public TrieNode<T> find(List<T> subsequence) { 
    220                 TrieNode<T> result = null; 
    221                 if (subsequence.isEmpty()) { 
    222                         result = this; 
    223                 } else { 
    224                         TrieNode<T> node = getChild(subsequence.get(0)); 
    225                         if (node != null) { 
    226                                 subsequence.remove(0); 
    227                                 result = node.find(subsequence); 
    228                         } 
    229                 } 
    230                 return result; 
    231         } 
    232  
    233         /** 
    234          * <p> 
    235          * Returns a collection of all symbols that follow a this node, i.e., the 
    236          * symbols associated with the children of this node. 
    237          * </p> 
    238          *  
    239          * @return symbols follow this node 
    240          * @see TrieNode#getFollowingSymbols() 
    241          */ 
    242         public Collection<T> getFollowingSymbols() { 
    243                 Collection<T> followingSymbols = new LinkedList<T>(); 
    244                 for (TrieNode<T> child : children) { 
    245                         followingSymbols.add(child.getSymbol()); 
    246                 } 
    247                 return followingSymbols; 
    248         } 
    249  
    250         /** 
    251          * <p> 
    252          * The string representation of a node is {@code symbol.toString()#count} 
    253          * </p> 
    254          *  
    255          * @see java.lang.Object#toString() 
    256          */ 
    257         @Override 
    258         public String toString() { 
    259                 String str = symbol.toString() + " #" + count; 
    260                 if (!children.isEmpty()) { 
    261                         str += StringTools.ENDLINE + children.toString(); 
    262                 } 
    263                 return str; 
    264         } 
    265  
    266         /** 
    267          * <p> 
    268          * Generates a {@link Tree} represenation of the trie. 
    269          * </p> 
    270          *  
    271          * @param parent 
    272          *            parent vertex in the generated tree 
    273          * @param graph 
    274          *            complete tree 
    275          */ 
    276         void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) { 
    277                 TrieVertex currentVertex; 
    278                 if (isRoot()) { 
    279                         currentVertex = new TrieVertex("root"); 
    280                         graph.addVertex(currentVertex); 
    281                 } else { 
    282                         currentVertex = new TrieVertex(getSymbol().toString() + "#" 
    283                                         + getCount()); 
    284                         graph.addChild(new Edge(), parent, currentVertex); 
    285                 } 
    286                 for (TrieNode<T> node : children) { 
    287                         node.getGraph(currentVertex, graph); 
    288                 } 
    289         } 
    290  
    291         /** 
    292          * <p> 
    293          * Appends the current node to the dot representation of the trie. 
    294          * </p> 
    295          *  
    296          * @param stringBuilder 
    297          *            {@link StringBuilder} to which the dot representation is 
    298          *            appended 
    299          */ 
    300         void appendDotRepresentation(StringBuilder stringBuilder) { 
    301                 String thisSaneId; 
    302                 if (isRoot()) { 
    303                         thisSaneId = "root"; 
    304                 } else { 
    305                         thisSaneId = symbol.toString().replace("\"", "\\\"") 
    306                                         .replaceAll("[\r\n]", "") 
    307                                         + "#" + count; 
    308                 } 
    309                 stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId 
    310                                 + "\"];" + StringTools.ENDLINE); 
    311                 for (TrieNode<T> childNode : children) { 
    312                         stringBuilder.append(" " + hashCode() + " -> " 
    313                                         + childNode.hashCode() + ";" + StringTools.ENDLINE); 
    314                 } 
    315                 for (TrieNode<T> childNode : children) { 
    316                         childNode.appendDotRepresentation(stringBuilder); 
    317                 } 
    318         } 
    319  
    320         /** 
    321          * <p> 
    322          * Checks if the node is a leaf. 
    323          * </p> 
    324          *  
    325          * @return true if the node is a leaf, false otherwise. 
    326          */ 
    327         protected boolean isLeaf() { 
    328                 return children.isEmpty(); 
    329         } 
    330  
    331         /** 
    332          * <p> 
    333          * Checks if the node is the root. 
    334          * </p> 
    335          *  
    336          * @return true if the node is the root of the trie, false otherwise 
    337          */ 
    338         protected boolean isRoot() { 
    339                 return symbol == null; 
    340         } 
    341  
    342         /** 
    343          * <p> 
    344          * Recursive methods that collects all nodes that are ancestors of leafs and 
    345          * stores them in the set. 
    346          * </p> 
    347          *  
    348          * @param ancestors 
    349          *            set of all ancestors of leafs 
    350          */ 
    351         protected void getLeafAncestors(List<TrieNode<T>> ancestors) { 
    352                 boolean isAncestor = false; 
    353                 for (TrieNode<T> child : children) { 
    354                         child.getLeafAncestors(ancestors); 
    355                         isAncestor |= child.isLeaf(); 
    356                 } 
    357                 if (isAncestor) { 
    358                         ancestors.add(this); 
    359                 } 
    360         } 
    361  
    362         /** 
    363          * <p> 
    364          * Returns the number of descendants of this node that are leafs. This does 
    365          * not only include direct children of this node, but all leafs in the 
    366          * sub-trie with this node as root. 
    367          * </p> 
    368          *  
    369          * @return number of leafs in this sub-trie 
    370          */ 
    371         protected int getNumLeafs() { 
    372                 int numLeafs = 0; 
    373                 for (TrieNode<T> child : children) { 
    374                         if (child.isLeaf()) { 
    375                                 numLeafs++; 
    376                         } else { 
    377                                 numLeafs += child.getNumLeafs(); 
    378                         } 
    379                 } 
    380                 return numLeafs; 
    381         } 
    382  
    383         /** 
    384          * <p> 
    385          * Sets the {@link #count} of this node. 
    386          * </p> 
    387          * <p> 
    388          * This function should only be used sparingly and very carefully! The count 
    389          * is usually maintained automatically by the training procedures. 
    390          * </p> 
    391          *  
    392          * @param count 
    393          *            new count 
    394          */ 
    395         protected void setCount(int count) { 
    396                 this.count = count; 
    397         } 
    398  
    399         /** 
    400          * <p> 
    401          * Two TrieNodes are defined as equal, if their {@link #count}, 
    402          * {@link #symbol}, and {@link #children} are equal. 
    403          * </p> 
    404          *  
    405          * @see java.lang.Object#equals(java.lang.Object) 
    406          */ 
    407         @SuppressWarnings("rawtypes") 
    408         @Override 
    409         public boolean equals(Object other) { 
    410                 if (other == this) { 
    411                         return true; 
    412                 } 
    413                 if (other instanceof TrieNode) { 
    414                         TrieNode otherNode = (TrieNode) other; 
    415                         if (symbol == null) { 
    416                                 return count == otherNode.count && otherNode.symbol == null 
    417                                                 && children.equals(otherNode.children); 
    418                         } else { 
    419                                 return count == otherNode.count 
    420                                                 && symbol.equals(((TrieNode) other).symbol) 
    421                                                 && children.equals(((TrieNode) other).children); 
    422                         } 
    423                 } 
    424                 return false; 
    425         } 
    426  
    427         /* 
    428          * (non-Javadoc) 
    429          *  
    430          * @see java.lang.Object#hashCode() 
    431          */ 
    432         @Override 
    433         public int hashCode() { 
    434                 int multiplier = 17; 
    435                 int hash = 42; 
    436                 if (symbol != null) { 
    437                         hash = multiplier * hash + symbol.hashCode(); 
    438                 } 
    439                 hash = multiplier * hash + count; 
    440                 hash = multiplier * hash + children.hashCode(); 
    441                 return hash; 
    442         } 
     31    /** 
     32     * <p> 
     33     * Id for object serialization. 
     34     * </p> 
     35     */ 
     36    private static final long serialVersionUID = 1L; 
     37 
     38    /** 
     39     * <p> 
     40     * Counter for the number of occurences of the sequence. 
     41     * </p> 
     42     */ 
     43    private int count; 
     44 
     45    /** 
     46     * <p> 
     47     * Symbol associated with the node. 
     48     * </p> 
     49     */ 
     50    private final T symbol; 
     51 
     52    /** 
     53     * <p> 
     54     * Child nodes of this node. If the node is a leaf this collection is empty. 
     55     * </p> 
     56     */ 
     57    private Collection<TrieNode<T>> children; 
     58 
     59    /** 
     60     * <p> 
     61     * Constructor. Creates a new TrieNode without a symbol associated.<br> 
     62     * <b>This constructor should only be used to create the root node of the trie!</b> 
     63     * </p> 
     64     */ 
     65    TrieNode() { 
     66        this.symbol = null; 
     67        count = 0; 
     68        children = new LinkedList<TrieNode<T>>(); 
     69    } 
     70 
     71    /** 
     72     * <p> 
     73     * Constructor. Creates a new TrieNode. The symbol must not be null. 
     74     * </p> 
     75     *  
     76     * @param symbol 
     77     *            symbol associated with the trie node 
     78     */ 
     79    TrieNode(T symbol) { 
     80        if (symbol == null) { 
     81            throw new InvalidParameterException( 
     82                                                "symbol must not be null. null is reserved for root node!"); 
     83        } 
     84        this.symbol = symbol; 
     85        count = 0; 
     86        children = new LinkedList<TrieNode<T>>(); 
     87    } 
     88 
     89    /** 
     90     * <p> 
     91     * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not be null. 
     92     * </p> 
     93     *  
     94     * @param other 
     95     */ 
     96    TrieNode(TrieNode<T> other) { 
     97        if (other == null) { 
     98            throw new InvalidParameterException("other must not be null"); 
     99        } 
     100        symbol = other.symbol; 
     101        count = other.count; 
     102        children = new LinkedList<TrieNode<T>>(); 
     103        for (TrieNode<T> child : other.children) { 
     104            children.add(new TrieNode<T>(child)); 
     105        } 
     106    } 
     107 
     108    /** 
     109     * <p> 
     110     * Adds a given subsequence to the trie and increases the counters accordingly. 
     111     * </p> 
     112     *  
     113     * @param subsequence 
     114     *            subsequence whose counters are increased 
     115     * @see Trie#add(List) 
     116     */ 
     117    public void add(List<T> subsequence) { 
     118        if (!subsequence.isEmpty()) { 
     119            if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by 
     120                                                      // the 
     121                                                      // recursion/TrieRoot! 
     122                throw new AssertionError("Invalid trie operation!"); 
     123            } 
     124            count++; 
     125            subsequence.remove(0); 
     126            if (!subsequence.isEmpty()) { 
     127                T nextSymbol = subsequence.get(0); 
     128                getChildCreate(nextSymbol).add(subsequence); 
     129            } 
     130        } 
     131    } 
     132 
     133    /** 
     134     * <p> 
     135     * Returns the symbol associated with the node. 
     136     * </p> 
     137     *  
     138     * @return symbol associated with the node 
     139     */ 
     140    public T getSymbol() { 
     141        return symbol; 
     142    } 
     143 
     144    /** 
     145     * <p> 
     146     * Returns the number of occurences of the sequence represented by the node. 
     147     * </p> 
     148     *  
     149     * @return number of occurences of the sequence represented by the node 
     150     */ 
     151    public int getCount() { 
     152        return count; 
     153    } 
     154 
     155    /** 
     156     * <p> 
     157     * Returns the child of the node associated with the given symbol or creates it if it does not 
     158     * exist yet. 
     159     * </p> 
     160     *  
     161     * @param symbol 
     162     *            symbol whose node is required 
     163     * @return node associated with the symbol 
     164     * @see Trie#getChildCreate(Object) 
     165     */ 
     166    protected TrieNode<T> getChildCreate(T symbol) { 
     167        TrieNode<T> node = getChild(symbol); 
     168        if (node == null) { 
     169            node = new TrieNode<T>(symbol); 
     170            children.add(node); 
     171        } 
     172        return node; 
     173    } 
     174 
     175    /** 
     176     * <p> 
     177     * Returns the child of the node associated with the given symbol or null if it does not exist. 
     178     * </p> 
     179     *  
     180     * @param symbol 
     181     *            symbol whose node is required 
     182     * @return node associated with the symbol; null if no such node exists 
     183     * @see Trie#getChild(Object) 
     184     */ 
     185    protected TrieNode<T> getChild(T symbol) { 
     186        for (TrieNode<T> child : children) { 
     187            if (child.getSymbol().equals(symbol)) { 
     188                return child; 
     189            } 
     190        } 
     191        return null; 
     192    } 
     193 
     194    /** 
     195     * <p> 
     196     * Returns all children of this node. 
     197     * </p> 
     198     *  
     199     * @return children of this node 
     200     */ 
     201    protected Collection<TrieNode<T>> getChildren() { 
     202        return children; 
     203    } 
     204 
     205    /** 
     206     * <p> 
     207     * Searches the sub-trie of this trie node for a given sequence and returns the node associated 
     208     * with the sequence or null if no such node is found. 
     209     * </p> 
     210     *  
     211     * @param sequence 
     212     *            sequence that is searched for 
     213     * @return node associated with the sequence 
     214     * @see Trie#find(List) 
     215     */ 
     216    public TrieNode<T> find(List<T> subsequence) { 
     217        TrieNode<T> result = null; 
     218        if (subsequence.isEmpty()) { 
     219            result = this; 
     220        } 
     221        else { 
     222            TrieNode<T> node = getChild(subsequence.get(0)); 
     223            if (node != null) { 
     224                subsequence.remove(0); 
     225                result = node.find(subsequence); 
     226            } 
     227        } 
     228        return result; 
     229    } 
     230 
     231    /** 
     232     * <p> 
     233     * Returns a collection of all symbols that follow a this node, i.e., the symbols associated 
     234     * with the children of this node. 
     235     * </p> 
     236     *  
     237     * @return symbols follow this node 
     238     * @see TrieNode#getFollowingSymbols() 
     239     */ 
     240    public Collection<T> getFollowingSymbols() { 
     241        Collection<T> followingSymbols = new LinkedList<T>(); 
     242        for (TrieNode<T> child : children) { 
     243            followingSymbols.add(child.getSymbol()); 
     244        } 
     245        return followingSymbols; 
     246    } 
     247 
     248    /** 
     249     * <p> 
     250     * The string representation of a node is {@code symbol.toString()#count} 
     251     * </p> 
     252     *  
     253     * @see java.lang.Object#toString() 
     254     */ 
     255    @Override 
     256    public String toString() { 
     257        String str = symbol.toString() + " #" + count; 
     258        if (!children.isEmpty()) { 
     259            str += StringTools.ENDLINE + children.toString(); 
     260        } 
     261        return str; 
     262    } 
     263 
     264    /** 
     265     * <p> 
     266     * Generates a {@link Tree} represenation of the trie. 
     267     * </p> 
     268     *  
     269     * @param parent 
     270     *            parent vertex in the generated tree 
     271     * @param graph 
     272     *            complete tree 
     273     */ 
     274    void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) { 
     275        TrieVertex currentVertex; 
     276        if (isRoot()) { 
     277            currentVertex = new TrieVertex("root"); 
     278            graph.addVertex(currentVertex); 
     279        } 
     280        else { 
     281            currentVertex = new TrieVertex(getSymbol().toString() + "#" + getCount()); 
     282            graph.addChild(new Edge(), parent, currentVertex); 
     283        } 
     284        for (TrieNode<T> node : children) { 
     285            node.getGraph(currentVertex, graph); 
     286        } 
     287    } 
     288 
     289    /** 
     290     * <p> 
     291     * Appends the current node to the dot representation of the trie. 
     292     * </p> 
     293     *  
     294     * @param stringBuilder 
     295     *            {@link StringBuilder} to which the dot representation is appended 
     296     */ 
     297    void appendDotRepresentation(StringBuilder stringBuilder) { 
     298        String thisSaneId; 
     299        if (isRoot()) { 
     300            thisSaneId = "root"; 
     301        } 
     302        else { 
     303            thisSaneId = 
     304                symbol.toString().replace("\"", "\\\"").replaceAll("[\r\n]", "") + "#" + count; 
     305        } 
     306        stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId + "\"];" + 
     307            StringTools.ENDLINE); 
     308        for (TrieNode<T> childNode : children) { 
     309            stringBuilder.append(" " + hashCode() + " -> " + childNode.hashCode() + ";" + 
     310                StringTools.ENDLINE); 
     311        } 
     312        for (TrieNode<T> childNode : children) { 
     313            childNode.appendDotRepresentation(stringBuilder); 
     314        } 
     315    } 
     316 
     317    /** 
     318     * <p> 
     319     * Checks if the node is a leaf. 
     320     * </p> 
     321     *  
     322     * @return true if the node is a leaf, false otherwise. 
     323     */ 
     324    protected boolean isLeaf() { 
     325        return children.isEmpty(); 
     326    } 
     327 
     328    /** 
     329     * <p> 
     330     * Checks if the node is the root. 
     331     * </p> 
     332     *  
     333     * @return true if the node is the root of the trie, false otherwise 
     334     */ 
     335    protected boolean isRoot() { 
     336        return symbol == null; 
     337    } 
     338 
     339    /** 
     340     * <p> 
     341     * Recursive methods that collects all nodes that are ancestors of leafs and stores them in the 
     342     * set. 
     343     * </p> 
     344     *  
     345     * @param ancestors 
     346     *            set of all ancestors of leafs 
     347     */ 
     348    protected void getLeafAncestors(List<TrieNode<T>> ancestors) { 
     349        boolean isAncestor = false; 
     350        for (TrieNode<T> child : children) { 
     351            child.getLeafAncestors(ancestors); 
     352            isAncestor |= child.isLeaf(); 
     353        } 
     354        if (isAncestor) { 
     355            ancestors.add(this); 
     356        } 
     357    } 
     358 
     359    /** 
     360     * <p> 
     361     * Returns the number of descendants of this node that are leafs. This does not only include 
     362     * direct children of this node, but all leafs in the sub-trie with this node as root. 
     363     * </p> 
     364     *  
     365     * @return number of leafs in this sub-trie 
     366     */ 
     367    protected int getNumLeafs() { 
     368        int numLeafs = 0; 
     369        for (TrieNode<T> child : children) { 
     370            if (child.isLeaf()) { 
     371                numLeafs++; 
     372            } 
     373            else { 
     374                numLeafs += child.getNumLeafs(); 
     375            } 
     376        } 
     377        return numLeafs; 
     378    } 
     379 
     380    /** 
     381     * <p> 
     382     * Sets the {@link #count} of this node. 
     383     * </p> 
     384     * <p> 
     385     * This function should only be used sparingly and very carefully! The count is usually 
     386     * maintained automatically by the training procedures. 
     387     * </p> 
     388     *  
     389     * @param count 
     390     *            new count 
     391     */ 
     392    protected void setCount(int count) { 
     393        this.count = count; 
     394    } 
     395 
     396    /** 
     397     * <p> 
     398     * Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and 
     399     * {@link #children} are equal. 
     400     * </p> 
     401     *  
     402     * @see java.lang.Object#equals(java.lang.Object) 
     403     */ 
     404    @SuppressWarnings("rawtypes") 
     405    @Override 
     406    public boolean equals(Object other) { 
     407        if (other == this) { 
     408            return true; 
     409        } 
     410        if (other instanceof TrieNode) { 
     411            TrieNode otherNode = (TrieNode) other; 
     412            if (symbol == null) { 
     413                return count == otherNode.count && otherNode.symbol == null && 
     414                    children.equals(otherNode.children); 
     415            } 
     416            else { 
     417                return count == otherNode.count && symbol.equals(((TrieNode) other).symbol) && 
     418                    children.equals(((TrieNode) other).children); 
     419            } 
     420        } 
     421        return false; 
     422    } 
     423 
     424    /* 
     425     * (non-Javadoc) 
     426     *  
     427     * @see java.lang.Object#hashCode() 
     428     */ 
     429    @Override 
     430    public int hashCode() { 
     431        int multiplier = 17; 
     432        int hash = 42; 
     433        if (symbol != null) { 
     434            hash = multiplier * hash + symbol.hashCode(); 
     435        } 
     436        hash = multiplier * hash + count; 
     437        hash = multiplier * hash + children.hashCode(); 
     438        return hash; 
     439    } 
    443440} 
Note: See TracChangeset for help on using the changeset viewer.