Changeset 1253

Timestamp:

07/12/13 18:54:15 (11 years ago)

Author:

pharms

Message:

• added a test for very large tries. First of all to see, if the trie works correctly with the new symbol map used internally, and also to see, how it scales with longer sequences and a large number of different symbols.

File:

• trunk/autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/TrieTest.java (modified) (3 diffs)

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

@@ -17 +17 @@
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
+import java.util.Map;
 
 import junitx.framework.ListAssert;
@@ -1755 +1757 @@
     }
 
+    @Test
+    public void testLargeTrie_1() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 2;
+        
+        TrieTester tester = new TrieTester(3, 10, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_2() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 2;
+        
+        TrieTester tester = new TrieTester(300, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_3() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 2;
+        
+        TrieTester tester = new TrieTester(1000, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_4() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 3;
+        
+        TrieTester tester = new TrieTester(3, 50, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_5() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 3;
+        
+        TrieTester tester = new TrieTester(300, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_6() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 3;
+        
+        TrieTester tester = new TrieTester(1000, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_7() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 4;
+        
+        TrieTester tester = new TrieTester(3, 50, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_8() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 4;
+        
+        TrieTester tester = new TrieTester(300, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_9() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 4;
+        
+        TrieTester tester = new TrieTester(1000, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_10() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 5;
+        
+        TrieTester tester = new TrieTester(3, 50, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_11() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 5;
+        
+        TrieTester tester = new TrieTester(300, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_12() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 5;
+        
+        TrieTester tester = new TrieTester(1000, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_13() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 6;
+        
+        TrieTester tester = new TrieTester(3, 50, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_14() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 6;
+        
+        TrieTester tester = new TrieTester(300, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTrie_15() throws Exception {
+        Trie<Integer> fixture = new Trie<Integer>();
+
+        int order = 6;
+        
+        TrieTester tester = new TrieTester(1000, 100000, order);
+
+        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
+        
+        for (Integer elem : tester.sequence) {
+            sequence.add(elem);
+        }
+        
+        fixture.train(sequence, order);
+        
+        fixture.process(tester);
+        assertTrue(tester.counts.isEmpty());
+    }
+
     @Before
     public void setUp() throws Exception {
@@ -1782 +2084 @@
     }
 
+    /**
+     * <p>
+     * class internally used for testing large tries.
+     * </p>
+     * 
+     * @author Patrick Harms
+     */
+    private static class TrieTester implements TrieProcessor<Integer> {
+        
+        /**
+         * the symbols used for testing the trie
+         */
+        private int[] symbols;
+
+        /**
+         * the simulated sequence
+         */
+        private int[] sequence;
+
+        /**
+         * the trained order of the tested trie
+         */
+        private int maxOrder;
+        
+        /**
+         * the expected counts of subsequences
+         */
+        private Map<Long, Integer> counts = new HashMap<Long, Integer>();
+
+        /**
+         * generates a simulated sequence and thereby stores the expected counts of the
+         * subsequences up to max order in a map. The technique uses integer and long values
+         * to be efficient and to allow testing with large sequences and symbol numbers. However,
+         * the technique is restricted to 1024 different symbols and a maximum tree depth of 6.
+         * The tester is also used as a trie processor to check for any node in the tree, if the
+         * trie calculated the count correctly and if it did not create too many nodes.
+         */
+        public TrieTester(int noOfSymbols, int sequenceLength, int maxOrder) {
+            if (noOfSymbols > 1024) {
+                throw new IllegalArgumentException("too large number of symbols");
+            }
+            if (maxOrder > 6) {
+                throw new IllegalArgumentException("too large number of symbols");
+            }
+            
+            this.symbols = new int[noOfSymbols];
+            
+            for (int i = 0; i < noOfSymbols; i++) {
+                this.symbols[i] = i;
+             }
+            
+            this.maxOrder = maxOrder;
+            
+            this.sequence = new int[sequenceLength];
+
+            for (int i = 0; i < sequenceLength; i++) {
+                int symbolIndex = (int) (Math.random() * noOfSymbols);
+                this.sequence[i] = this.symbols[symbolIndex];
+                
+                if ((i - maxOrder + 1) >= 0) {
+                    storeCounts(this.sequence, i - maxOrder + 1, i);
+                }
+            }
+            
+            for (int i = sequenceLength - maxOrder + 1; i < sequenceLength; i++) {
+                storeCounts(this.sequence, i, sequenceLength - 1);
+            }
+        }
+
+        /**
+         * <p>
+         * stores the counts for the subsequence denoted by the start and end index (inclusive).
+         * </p>
+         */
+        private void storeCounts(int[] sequence, int startIndex, int endIndex) {
+            long key = 0;
+            
+            for (int i = startIndex; i <= endIndex; i++) {
+                key = key << 10;
+                key += 1 + this.sequence[i];
+            
+                Integer count = this.counts.get(key);
+                if (count == null) {
+                    count = 0;
+                }
+            
+                //System.out.println(key + "  " + (count + 1));
+                this.counts.put(key, count + 1);
+            }
+        }
+
+        /* (non-Javadoc)
+         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
+         */
+        @Override
+        public TrieProcessor.Result process(List<Integer> sequence, int count) {
+            long key = 0;
+            
+            for (Integer symbol : sequence) {
+                key = key << 10;
+                key += 1 + symbol;
+            }
+            
+            Integer expectedCount = this.counts.remove(key);
+            assertNotNull(expectedCount);
+            assertEquals(expectedCount.intValue(), count);
+            
+            assertTrue(sequence.size() <= this.maxOrder);
+            
+            return TrieProcessor.Result.CONTINUE;
+        }
+
+    }
 }