Changeset 1253 for trunk/autoquest-core-usageprofiles-test
- Timestamp:
- 07/12/13 18:54:15 (11 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/TrieTest.java
r1252 r1253 17 17 import java.util.ArrayList; 18 18 import java.util.Collection; 19 import java.util.HashMap; 19 20 import java.util.HashSet; 20 21 import java.util.List; 22 import java.util.Map; 21 23 22 24 import junitx.framework.ListAssert; … … 1755 1757 } 1756 1758 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 1757 2059 @Before 1758 2060 public void setUp() throws Exception { … … 1782 2084 } 1783 2085 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 } 1784 2199 }
Note: See TracChangeset
for help on using the changeset viewer.