Changeset 1060


Ignore:
Timestamp:
02/07/13 17:57:07 (12 years ago)
Author:
pharms
Message:
  • extended Trie implementation to be able to use different compare strategies
  • implemented a method to determine subsequences of a minimal length that occur most often
Location:
trunk
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/TrieTest.java

    r927 r1060  
    7575        @Test(expected = java.lang.IllegalArgumentException.class) 
    7676        public void testTrie_3() throws Exception { 
    77                 new Trie<String>(null); 
    78         } 
     77                new Trie<String>((SymbolComparator<String>) null); 
     78        } 
     79 
     80        @Test(expected = java.lang.IllegalArgumentException.class) 
     81        public void testTrie_4() throws Exception { 
     82                new Trie<String>((Trie<String>) null); 
     83        } 
    7984 
    8085        @Test 
    … …  
    240245                assertEquals(0, result.size()); 
    241246        } 
     247 
     248        @Test 
     249        public void testGetSequencesWithMostOccurrences_1() throws Exception { 
     250                Trie<String> fixture = new Trie<String>(); 
     251                fixture.train(sequence, 3); 
     252                 
     253                List<String> expected = new ArrayList<String>(); 
     254                expected.add("a"); 
     255 
     256                Collection<List<String>> result = fixture.getSequencesWithMostOccurrences(1); 
     257 
     258                assertEquals(1, result.size()); 
     259                ListAssert.assertEquals(expected, result.iterator().next()); 
     260        } 
     261 
     262        @Test 
     263        public void testGetSequencesWithMostOccurrences_2() throws Exception { 
     264                Trie<String> fixture = new Trie<String>(); 
     265                fixture.train(sequence, 3); 
     266                 
     267                Collection<List<String>> result = fixture.getSequencesWithMostOccurrences(2); 
     268 
     269                assertEquals(5, result.size()); 
     270                 
     271                List<String> expected = new ArrayList<String>(); 
     272                expected.add("a"); 
     273                expected.add("b"); 
     274                ListAssert.assertContains((List<List<String>>) result, expected); 
     275                 
     276                expected.add("r"); 
     277                ListAssert.assertContains((List<List<String>>) result, expected); 
     278                 
     279                expected.clear(); 
     280                expected.add("b"); 
     281                expected.add("r"); 
     282                ListAssert.assertContains((List<List<String>>) result, expected); 
     283                 
     284                expected.add("a"); 
     285                ListAssert.assertContains((List<List<String>>) result, expected); 
     286                 
     287                expected.clear(); 
     288                expected.add("r"); 
     289                expected.add("a"); 
     290                ListAssert.assertContains((List<List<String>>) result, expected); 
     291        } 
     292 
     293        @Test 
     294        public void testGetSequencesWithMostOccurrences_3() throws Exception { 
     295                Trie<String> fixture = new Trie<String>(); 
     296                fixture.train(sequence, 3); 
     297                 
     298                Collection<List<String>> result = fixture.getSequencesWithMostOccurrences(3); 
     299 
     300                assertEquals(2, result.size()); 
     301                 
     302                List<String> expected = new ArrayList<String>(); 
     303                expected.add("a"); 
     304                expected.add("b"); 
     305                expected.add("r"); 
     306                ListAssert.assertContains((List<List<String>>) result, expected); 
     307                 
     308                expected.clear(); 
     309                expected.add("b"); 
     310                expected.add("r"); 
     311                expected.add("a"); 
     312                ListAssert.assertContains((List<List<String>>) result, expected); 
     313        } 
     314 
     315        @Test 
     316        public void testGetSequencesWithMostOccurrences_4() throws Exception { 
     317                Trie<String> fixture = new Trie<String>(); 
     318                fixture.train(sequence, 3); 
     319                 
     320                Collection<List<String>> result = fixture.getSequencesWithMostOccurrences(4); 
     321 
     322                assertEquals(0, result.size()); 
     323        } 
    242324 
    243325        @Test 

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

    r927 r1060  
    3434 * </p> 
    3535 *  
    36  * @author Steffen Herbold 
     36 * @author Steffen Herbold, Patrick Harms 
    3737 *  
    3838 * @param <T> 
    … …  
    6666    /** 
    6767     * <p> 
    68      * Contructor. Creates a new Trie. 
     68     * Comparator to be used for comparing the symbols with each other 
     69     * </p> 
     70     */ 
     71    private SymbolComparator<T> comparator; 
     72 
     73    /** 
     74     * <p> 
     75     * Contructor. Creates a new Trie with a {@link DefaultSymbolComparator}. 
    6976     * </p> 
    7077     */ 
    7178    public Trie() { 
    72         rootNode = new TrieNode<T>(); 
     79        this(new DefaultSymbolComparator<T>()); 
     80    } 
     81 
     82    /** 
     83     * <p> 
     84     * Contructor. Creates a new Trie with that uses a specific {@link SymbolComparator}. 
     85     * </p> 
     86     */ 
     87    public Trie(SymbolComparator<T> comparator) { 
     88        this.comparator = comparator; 
     89        rootNode = new TrieNode<T>(comparator); 
    7390        knownSymbols = new LinkedHashSet<T>(); 
    7491    } 
    … …  
    7693    /** 
    7794     * <p> 
    78      * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must noch be null. 
     95     * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must not be null. 
    7996     * </p> 
    8097     *  
    … …  
    88105        rootNode = new TrieNode<T>(other.rootNode); 
    89106        knownSymbols = new LinkedHashSet<T>(other.knownSymbols); 
     107        comparator = other.comparator; 
    90108    } 
    91109 
    … …  
    120138        for (T currentEvent : sequence) { 
    121139            latestActions.add(currentEvent); 
    122             knownSymbols.add(currentEvent); 
     140            addToKnownSymbols(currentEvent); 
    123141            i++; 
    124142            if (i >= maxOrder) { 
    … …  
    143161    protected void add(List<T> subsequence) { 
    144162        if (subsequence != null && !subsequence.isEmpty()) { 
    145             knownSymbols.addAll(subsequence); 
     163            addToKnownSymbols(subsequence); 
    146164            subsequence = new LinkedList<T>(subsequence); // defensive copy! 
    147165            T firstSymbol = subsequence.get(0); 
    … …  
    306324    /** 
    307325     * <p> 
     326     * returns a list of symbol sequences which have a minimal length and that occurred most often 
     327     * with the same number of occurrences. The resulting list is empty, if there is no symbol 
     328     * sequence with the minimal length. 
     329     * </p> 
     330     * 
     331     * @param minimalLength the minimal length of the returned sequences 
     332     *  
     333     * @return as described 
     334     */ 
     335    public Collection<List<T>> getSequencesWithMostOccurrences(int minimalLength) { 
     336        LinkedList<TrieNode<T>> context = new LinkedList<TrieNode<T>>(); 
     337        Collection<List<TrieNode<T>>> paths = new LinkedList<List<TrieNode<T>>>(); 
     338         
     339        context.push(rootNode); 
     340         
     341        // traverse the trie and determine all sequences, which have the maximum number of 
     342        // occurrences and a minimal length. 
     343         
     344        // minimalLength + 1 because we denote the depth including the root node 
     345        determineLongPathsWithMostOccurrences(minimalLength + 1, paths, context); 
     346         
     347        Collection<List<T>> resultingPaths = new LinkedList<List<T>>(); 
     348        List<T> resultingPath; 
     349         
     350        if (paths.size() > 0) { 
     351             
     352            for (List<TrieNode<T>> path : paths) { 
     353                resultingPath = new LinkedList<T>(); 
     354                 
     355                for (TrieNode<T> node : path) { 
     356                    if (node.getSymbol() != null) { 
     357                        resultingPath.add(node.getSymbol()); 
     358                    } 
     359                } 
     360                 
     361                resultingPaths.add(resultingPath); 
     362            } 
     363        } 
     364         
     365        return resultingPaths; 
     366    } 
     367 
     368    /** 
     369     * <p> 
     370     * Traverses the trie to collect all sequences with a maximum number of occurrences and with 
     371     * a minimal length. The length is encoded in the provided recursion depth. 
     372     * </p> 
     373     * 
     374     * @param minimalDepth the minimal recursion depth to be done 
     375     * @param paths        the paths through the trie that all occurred with the same amount and 
     376     *                     that have the so far found maximum of occurrences (is updated each 
     377     *                     time a further path with the same number of occurrences is found; is 
     378     *                     replaced if a path with more occurrences is found) 
     379     * @param context      the path through the trie, that is analyzed by the recursive call 
     380     */ 
     381    private void determineLongPathsWithMostOccurrences(int                           minimalDepth, 
     382                                                       Collection<List<TrieNode<T>>> paths, 
     383                                                       LinkedList<TrieNode<T>>       context) 
     384    { 
     385        int maxCount = 0; 
     386 
     387        // only if we already reached the depth to be achieved, we check if the paths have the 
     388        // maximum number of occurrences 
     389        if (context.size() >= minimalDepth) { 
     390             
     391            // try to determine the maximum number of occurrences so far, if any 
     392            if (paths.size() > 0) { 
     393                List<TrieNode<T>> path = paths.iterator().next(); 
     394                maxCount = path.get(path.size() - 1).getCount(); 
     395            } 
     396 
     397            // if the current path has a higher number of occurrences than all so far, clear 
     398            // the paths collected so far and set the new number of occurrences as new maximum 
     399            if (context.getLast().getCount() > maxCount) { 
     400                paths.clear(); 
     401                maxCount = context.getLast().getCount(); 
     402            } 
     403             
     404            // if the path matches the current maximal number of occurrences, add it to the list 
     405            // of collected paths with these number of occurrences 
     406            if (context.getLast().getCount() == maxCount) { 
     407                paths.add(new LinkedList<TrieNode<T>>(context)); 
     408            } 
     409        } 
     410         
     411        // perform the trie traversal 
     412        for (TrieNode<T> child : context.getLast().getChildren()) { 
     413            if (child.getCount() >= maxCount) { 
     414                context.add(child); 
     415                determineLongPathsWithMostOccurrences(minimalDepth, paths, context); 
     416                context.removeLast(); 
     417            } 
     418        } 
     419    } 
     420     
     421    /** 
     422     * <p> 
     423     * adds a new symbol to the collection of known symbols if this symbol is not already 
     424     * contained. The symbols are compared using the comparator. 
     425     * </p> 
     426     * 
     427     * @param symbol the symbol to be added to the known symbols 
     428     */ 
     429    private void addToKnownSymbols(T symbol) { 
     430        for (T knownSymbol : knownSymbols) { 
     431            if (comparator.equals(knownSymbol, symbol)) { 
     432                return; 
     433            } 
     434        } 
     435         
     436        knownSymbols.add(symbol); 
     437    } 
     438 
     439    /** 
     440     * <p> 
     441     * adds a list of new symbols to the collection of known symbols. Uses the 
     442     * {@link #addToKnownSymbols(Object)} method for each element of the provided list. 
     443     * </p> 
     444     * 
     445     * @param symbols the list of symbols to be added to the known symbols 
     446     */ 
     447    private void addToKnownSymbols(List<T> symbols) { 
     448        for (T symbol : symbols) { 
     449            addToKnownSymbols(symbol); 
     450        } 
     451    } 
     452 
     453    /** 
     454     * <p> 
    308455     * Helper class for graph visualization of a trie. 
    309456     * </p> 
    … …  
    441588        knownSymbols = new HashSet<T>(); 
    442589        for (TrieNode<T> node : rootNode.getChildren()) { 
    443             knownSymbols.add(node.getSymbol()); 
     590            addToKnownSymbols(node.getSymbol()); 
    444591        } 
    445592    } 
    … …  
    478625        return hash; 
    479626    } 
     627 
    480628} 

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

    r927 r1060  
    3333 * </p> 
    3434 *  
    35  * @author Steffen Herbold 
     35 * @author Steffen Herbold, Patrick Harms 
    3636 *  
    3737 * @param <T> 
    … …  
    7171    /** 
    7272     * <p> 
     73     * Comparator to be used for comparing the symbols with each other 
     74     * </p> 
     75     */ 
     76    private SymbolComparator<T> comparator; 
     77 
     78    /** 
     79     * <p> 
    7380     * Constructor. Creates a new TrieNode without a symbol associated.<br> 
    7481     * <b>This constructor should only be used to create the root node of the trie!</b> 
     82     * The comparator used by the tree node will be a {@link DefaultSymbolComparator}. 
    7583     * </p> 
    7684     */ 
    7785    TrieNode() { 
     86        this(new DefaultSymbolComparator<T>()); 
     87    } 
     88 
     89    /** 
     90     * <p> 
     91     * Constructor. Creates a new TrieNode. The symbol must not be null. 
     92     * The comparator used by the tree node will be a {@link DefaultSymbolComparator}. 
     93     * </p> 
     94     *  
     95     * @param symbol 
     96     *            symbol associated with the trie node 
     97     */ 
     98    TrieNode(T symbol) { 
     99        this(symbol, new DefaultSymbolComparator<T>()); 
     100    } 
     101 
     102    /** 
     103     * <p> 
     104     * Constructor. Creates a new TrieNode without a symbol associated using the provided 
     105     * comparator.<br> 
     106     * <b>This constructor should only be used to create the root node of the trie!</b> 
     107     * <br>The comparator must not be null. 
     108     * </p> 
     109     */ 
     110    TrieNode(SymbolComparator<T> comparator) { 
     111        if (comparator == null) { 
     112            throw new IllegalArgumentException("comparator must not be null!"); 
     113        } 
     114        this.comparator = comparator; 
    78115        this.symbol = null; 
    79116        count = 0; 
    … …  
    83120    /** 
    84121     * <p> 
    85      * Constructor. Creates a new TrieNode. The symbol must not be null. 
     122     * Constructor. Creates a new TrieNode using the provided comparator. The symbol and the 
     123     * comparator must not be null. 
    86124     * </p> 
    87125     *  
    … …  
    89127     *            symbol associated with the trie node 
    90128     */ 
    91     TrieNode(T symbol) { 
     129    TrieNode(T symbol, SymbolComparator<T> comparator) { 
    92130        if (symbol == null) { 
    93             throw new IllegalArgumentException( 
    94                                                 "symbol must not be null. null is reserved for root node!"); 
     131            throw new IllegalArgumentException 
     132                ("symbol must not be null. null is reserved for root node!"); 
    95133        } 
    96134        this.symbol = symbol; 
     135         
     136        if (comparator == null) { 
     137            throw new IllegalArgumentException("comparator must not be null!"); 
     138        } 
     139        this.comparator = comparator; 
     140 
    97141        count = 0; 
    98142        children = new LinkedList<TrieNode<T>>(); 
    … …  
    112156        symbol = other.symbol; 
    113157        count = other.count; 
     158        comparator = other.comparator; 
    114159        children = new LinkedList<TrieNode<T>>(); 
    115160        for (TrieNode<T> child : other.children) { 
    … …  
    129174    public void add(List<T> subsequence) { 
    130175        if (!subsequence.isEmpty()) { 
    131             if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by 
    132                                                       // the 
    133                                                       // recursion/TrieRoot! 
     176            if (!comparator.equals(symbol, subsequence.get(0))) { // should be guaranteed by 
     177                                                                  // the recursion/TrieRoot! 
    134178                throw new AssertionError("Invalid trie operation!"); 
    135179            } 
    … …  
    179223        TrieNode<T> node = getChild(symbol); 
    180224        if (node == null) { 
    181             node = new TrieNode<T>(symbol); 
     225            node = new TrieNode<T>(symbol, comparator); 
    182226            children.add(node); 
    183227        } 
    … …  
    197241    protected TrieNode<T> getChild(T symbol) { 
    198242        for (TrieNode<T> child : children) { 
    199             if (child.getSymbol().equals(symbol)) { 
     243            if (comparator.equals(child.getSymbol(), symbol)) { 
    200244                return child; 
    201245            } 
    … …  
    267311    @Override 
    268312    public String toString() { 
    269         String str = symbol.toString() + " #" + count; 
     313        String str; 
     314         
     315        if (symbol == null) { 
     316            str = "ROOT"; 
     317        } 
     318        else { 
     319            str = symbol.toString() + " #" + count; 
     320        } 
     321         
    270322        if (!children.isEmpty()) { 
    271323            str += StringTools.ENDLINE + children.toString(); 
    … …  
    276328    /** 
    277329     * <p> 
    278      * Generates a {@link Tree} represenation of the trie. 
     330     * Generates a {@link Tree} representation of the trie. 
    279331     * </p> 
    280332     *  
    … …  
    409461     * <p> 
    410462     * Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and 
    411      * {@link #children} are equal. 
     463     * {@link #children} are equal. For the comparison of their symbols the comparator is used. 
    412464     * </p> 
    413465     *  
    414466     * @see java.lang.Object#equals(java.lang.Object) 
    415467     */ 
    416     @SuppressWarnings("rawtypes") 
     468    @SuppressWarnings({ "rawtypes", "unchecked" }) 
    417469    @Override 
    418470    public boolean equals(Object other) { 
    … …  
    427479            } 
    428480            else { 
    429                 return count == otherNode.count && symbol.equals(((TrieNode) other).symbol) && 
     481                return count == otherNode.count && 
     482                    symbol.getClass().isInstance(((TrieNode) other).symbol) && 
     483                    comparator.equals(symbol, ((TrieNode<T>) other).symbol) && 
    430484                    children.equals(((TrieNode) other).children); 
    431485            } 
Note: See TracChangeset for help on using the changeset viewer.