Ignore:
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:
1 edited

Legend:

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

    r1252 r1253  
    1717import java.util.ArrayList; 
    1818import java.util.Collection; 
     19import java.util.HashMap; 
    1920import java.util.HashSet; 
    2021import java.util.List; 
     22import java.util.Map; 
    2123 
    2224import junitx.framework.ListAssert; 
     
    17551757    } 
    17561758 
     1759    @Test 
     1760    public void testLargeTrie_1() throws Exception { 
     1761        Trie<Integer> fixture = new Trie<Integer>(); 
     1762 
     1763        int order = 2; 
     1764         
     1765        TrieTester tester = new TrieTester(3, 10, order); 
     1766 
     1767        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1768         
     1769        for (Integer elem : tester.sequence) { 
     1770            sequence.add(elem); 
     1771        } 
     1772         
     1773        fixture.train(sequence, order); 
     1774         
     1775        fixture.process(tester); 
     1776        assertTrue(tester.counts.isEmpty()); 
     1777    } 
     1778 
     1779    @Test 
     1780    public void testLargeTrie_2() throws Exception { 
     1781        Trie<Integer> fixture = new Trie<Integer>(); 
     1782 
     1783        int order = 2; 
     1784         
     1785        TrieTester tester = new TrieTester(300, 100000, order); 
     1786 
     1787        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1788         
     1789        for (Integer elem : tester.sequence) { 
     1790            sequence.add(elem); 
     1791        } 
     1792         
     1793        fixture.train(sequence, order); 
     1794         
     1795        fixture.process(tester); 
     1796        assertTrue(tester.counts.isEmpty()); 
     1797    } 
     1798 
     1799    @Test 
     1800    public void testLargeTrie_3() throws Exception { 
     1801        Trie<Integer> fixture = new Trie<Integer>(); 
     1802 
     1803        int order = 2; 
     1804         
     1805        TrieTester tester = new TrieTester(1000, 100000, order); 
     1806 
     1807        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1808         
     1809        for (Integer elem : tester.sequence) { 
     1810            sequence.add(elem); 
     1811        } 
     1812         
     1813        fixture.train(sequence, order); 
     1814         
     1815        fixture.process(tester); 
     1816        assertTrue(tester.counts.isEmpty()); 
     1817    } 
     1818 
     1819    @Test 
     1820    public void testLargeTrie_4() throws Exception { 
     1821        Trie<Integer> fixture = new Trie<Integer>(); 
     1822 
     1823        int order = 3; 
     1824         
     1825        TrieTester tester = new TrieTester(3, 50, order); 
     1826 
     1827        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1828         
     1829        for (Integer elem : tester.sequence) { 
     1830            sequence.add(elem); 
     1831        } 
     1832         
     1833        fixture.train(sequence, order); 
     1834         
     1835        fixture.process(tester); 
     1836        assertTrue(tester.counts.isEmpty()); 
     1837    } 
     1838 
     1839    @Test 
     1840    public void testLargeTrie_5() throws Exception { 
     1841        Trie<Integer> fixture = new Trie<Integer>(); 
     1842 
     1843        int order = 3; 
     1844         
     1845        TrieTester tester = new TrieTester(300, 100000, order); 
     1846 
     1847        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1848         
     1849        for (Integer elem : tester.sequence) { 
     1850            sequence.add(elem); 
     1851        } 
     1852         
     1853        fixture.train(sequence, order); 
     1854         
     1855        fixture.process(tester); 
     1856        assertTrue(tester.counts.isEmpty()); 
     1857    } 
     1858 
     1859    @Test 
     1860    public void testLargeTrie_6() throws Exception { 
     1861        Trie<Integer> fixture = new Trie<Integer>(); 
     1862 
     1863        int order = 3; 
     1864         
     1865        TrieTester tester = new TrieTester(1000, 100000, order); 
     1866 
     1867        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1868         
     1869        for (Integer elem : tester.sequence) { 
     1870            sequence.add(elem); 
     1871        } 
     1872         
     1873        fixture.train(sequence, order); 
     1874         
     1875        fixture.process(tester); 
     1876        assertTrue(tester.counts.isEmpty()); 
     1877    } 
     1878 
     1879    @Test 
     1880    public void testLargeTrie_7() throws Exception { 
     1881        Trie<Integer> fixture = new Trie<Integer>(); 
     1882 
     1883        int order = 4; 
     1884         
     1885        TrieTester tester = new TrieTester(3, 50, order); 
     1886 
     1887        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1888         
     1889        for (Integer elem : tester.sequence) { 
     1890            sequence.add(elem); 
     1891        } 
     1892         
     1893        fixture.train(sequence, order); 
     1894         
     1895        fixture.process(tester); 
     1896        assertTrue(tester.counts.isEmpty()); 
     1897    } 
     1898 
     1899    @Test 
     1900    public void testLargeTrie_8() throws Exception { 
     1901        Trie<Integer> fixture = new Trie<Integer>(); 
     1902 
     1903        int order = 4; 
     1904         
     1905        TrieTester tester = new TrieTester(300, 100000, order); 
     1906 
     1907        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1908         
     1909        for (Integer elem : tester.sequence) { 
     1910            sequence.add(elem); 
     1911        } 
     1912         
     1913        fixture.train(sequence, order); 
     1914         
     1915        fixture.process(tester); 
     1916        assertTrue(tester.counts.isEmpty()); 
     1917    } 
     1918 
     1919    @Test 
     1920    public void testLargeTrie_9() throws Exception { 
     1921        Trie<Integer> fixture = new Trie<Integer>(); 
     1922 
     1923        int order = 4; 
     1924         
     1925        TrieTester tester = new TrieTester(1000, 100000, order); 
     1926 
     1927        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1928         
     1929        for (Integer elem : tester.sequence) { 
     1930            sequence.add(elem); 
     1931        } 
     1932         
     1933        fixture.train(sequence, order); 
     1934         
     1935        fixture.process(tester); 
     1936        assertTrue(tester.counts.isEmpty()); 
     1937    } 
     1938 
     1939    @Test 
     1940    public void testLargeTrie_10() throws Exception { 
     1941        Trie<Integer> fixture = new Trie<Integer>(); 
     1942 
     1943        int order = 5; 
     1944         
     1945        TrieTester tester = new TrieTester(3, 50, order); 
     1946 
     1947        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1948         
     1949        for (Integer elem : tester.sequence) { 
     1950            sequence.add(elem); 
     1951        } 
     1952         
     1953        fixture.train(sequence, order); 
     1954         
     1955        fixture.process(tester); 
     1956        assertTrue(tester.counts.isEmpty()); 
     1957    } 
     1958 
     1959    @Test 
     1960    public void testLargeTrie_11() throws Exception { 
     1961        Trie<Integer> fixture = new Trie<Integer>(); 
     1962 
     1963        int order = 5; 
     1964         
     1965        TrieTester tester = new TrieTester(300, 100000, order); 
     1966 
     1967        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1968         
     1969        for (Integer elem : tester.sequence) { 
     1970            sequence.add(elem); 
     1971        } 
     1972         
     1973        fixture.train(sequence, order); 
     1974         
     1975        fixture.process(tester); 
     1976        assertTrue(tester.counts.isEmpty()); 
     1977    } 
     1978 
     1979    @Test 
     1980    public void testLargeTrie_12() throws Exception { 
     1981        Trie<Integer> fixture = new Trie<Integer>(); 
     1982 
     1983        int order = 5; 
     1984         
     1985        TrieTester tester = new TrieTester(1000, 100000, order); 
     1986 
     1987        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     1988         
     1989        for (Integer elem : tester.sequence) { 
     1990            sequence.add(elem); 
     1991        } 
     1992         
     1993        fixture.train(sequence, order); 
     1994         
     1995        fixture.process(tester); 
     1996        assertTrue(tester.counts.isEmpty()); 
     1997    } 
     1998 
     1999    @Test 
     2000    public void testLargeTrie_13() throws Exception { 
     2001        Trie<Integer> fixture = new Trie<Integer>(); 
     2002 
     2003        int order = 6; 
     2004         
     2005        TrieTester tester = new TrieTester(3, 50, order); 
     2006 
     2007        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     2008         
     2009        for (Integer elem : tester.sequence) { 
     2010            sequence.add(elem); 
     2011        } 
     2012         
     2013        fixture.train(sequence, order); 
     2014         
     2015        fixture.process(tester); 
     2016        assertTrue(tester.counts.isEmpty()); 
     2017    } 
     2018 
     2019    @Test 
     2020    public void testLargeTrie_14() throws Exception { 
     2021        Trie<Integer> fixture = new Trie<Integer>(); 
     2022 
     2023        int order = 6; 
     2024         
     2025        TrieTester tester = new TrieTester(300, 100000, order); 
     2026 
     2027        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     2028         
     2029        for (Integer elem : tester.sequence) { 
     2030            sequence.add(elem); 
     2031        } 
     2032         
     2033        fixture.train(sequence, order); 
     2034         
     2035        fixture.process(tester); 
     2036        assertTrue(tester.counts.isEmpty()); 
     2037    } 
     2038 
     2039    @Test 
     2040    public void testLargeTrie_15() throws Exception { 
     2041        Trie<Integer> fixture = new Trie<Integer>(); 
     2042 
     2043        int order = 6; 
     2044         
     2045        TrieTester tester = new TrieTester(1000, 100000, order); 
     2046 
     2047        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length); 
     2048         
     2049        for (Integer elem : tester.sequence) { 
     2050            sequence.add(elem); 
     2051        } 
     2052         
     2053        fixture.train(sequence, order); 
     2054         
     2055        fixture.process(tester); 
     2056        assertTrue(tester.counts.isEmpty()); 
     2057    } 
     2058 
    17572059    @Before 
    17582060    public void setUp() throws Exception { 
     
    17822084    } 
    17832085 
     2086    /** 
     2087     * <p> 
     2088     * class internally used for testing large tries. 
     2089     * </p> 
     2090     *  
     2091     * @author Patrick Harms 
     2092     */ 
     2093    private static class TrieTester implements TrieProcessor<Integer> { 
     2094         
     2095        /** 
     2096         * the symbols used for testing the trie 
     2097         */ 
     2098        private int[] symbols; 
     2099 
     2100        /** 
     2101         * the simulated sequence 
     2102         */ 
     2103        private int[] sequence; 
     2104 
     2105        /** 
     2106         * the trained order of the tested trie 
     2107         */ 
     2108        private int maxOrder; 
     2109         
     2110        /** 
     2111         * the expected counts of subsequences 
     2112         */ 
     2113        private Map<Long, Integer> counts = new HashMap<Long, Integer>(); 
     2114 
     2115        /** 
     2116         * generates a simulated sequence and thereby stores the expected counts of the 
     2117         * subsequences up to max order in a map. The technique uses integer and long values 
     2118         * to be efficient and to allow testing with large sequences and symbol numbers. However, 
     2119         * the technique is restricted to 1024 different symbols and a maximum tree depth of 6. 
     2120         * The tester is also used as a trie processor to check for any node in the tree, if the 
     2121         * trie calculated the count correctly and if it did not create too many nodes. 
     2122         */ 
     2123        public TrieTester(int noOfSymbols, int sequenceLength, int maxOrder) { 
     2124            if (noOfSymbols > 1024) { 
     2125                throw new IllegalArgumentException("too large number of symbols"); 
     2126            } 
     2127            if (maxOrder > 6) { 
     2128                throw new IllegalArgumentException("too large number of symbols"); 
     2129            } 
     2130             
     2131            this.symbols = new int[noOfSymbols]; 
     2132             
     2133            for (int i = 0; i < noOfSymbols; i++) { 
     2134                this.symbols[i] = i; 
     2135             } 
     2136             
     2137            this.maxOrder = maxOrder; 
     2138             
     2139            this.sequence = new int[sequenceLength]; 
     2140 
     2141            for (int i = 0; i < sequenceLength; i++) { 
     2142                int symbolIndex = (int) (Math.random() * noOfSymbols); 
     2143                this.sequence[i] = this.symbols[symbolIndex]; 
     2144                 
     2145                if ((i - maxOrder + 1) >= 0) { 
     2146                    storeCounts(this.sequence, i - maxOrder + 1, i); 
     2147                } 
     2148            } 
     2149             
     2150            for (int i = sequenceLength - maxOrder + 1; i < sequenceLength; i++) { 
     2151                storeCounts(this.sequence, i, sequenceLength - 1); 
     2152            } 
     2153        } 
     2154 
     2155        /** 
     2156         * <p> 
     2157         * stores the counts for the subsequence denoted by the start and end index (inclusive). 
     2158         * </p> 
     2159         */ 
     2160        private void storeCounts(int[] sequence, int startIndex, int endIndex) { 
     2161            long key = 0; 
     2162             
     2163            for (int i = startIndex; i <= endIndex; i++) { 
     2164                key = key << 10; 
     2165                key += 1 + this.sequence[i]; 
     2166             
     2167                Integer count = this.counts.get(key); 
     2168                if (count == null) { 
     2169                    count = 0; 
     2170                } 
     2171             
     2172                //System.out.println(key + "  " + (count + 1)); 
     2173                this.counts.put(key, count + 1); 
     2174            } 
     2175        } 
     2176 
     2177        /* (non-Javadoc) 
     2178         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int) 
     2179         */ 
     2180        @Override 
     2181        public TrieProcessor.Result process(List<Integer> sequence, int count) { 
     2182            long key = 0; 
     2183             
     2184            for (Integer symbol : sequence) { 
     2185                key = key << 10; 
     2186                key += 1 + symbol; 
     2187            } 
     2188             
     2189            Integer expectedCount = this.counts.remove(key); 
     2190            assertNotNull(expectedCount); 
     2191            assertEquals(expectedCount.intValue(), count); 
     2192             
     2193            assertTrue(sequence.size() <= this.maxOrder); 
     2194             
     2195            return TrieProcessor.Result.CONTINUE; 
     2196        } 
     2197 
     2198    } 
    17842199} 
Note: See TracChangeset for help on using the changeset viewer.