8 #include "misc/utils.h"
14 int main(int argc, char** argv)
16 std::cout << "RLCSA LCP test" << std::endl;
19 std::cout << "Usage: lcp_test basename queries runs modes [random_seed]" << std::endl;
20 std::cout << std::endl;
21 std::cout << "Supported modes:" << std::endl;
22 std::cout << "d -- Direct LCP" << std::endl;
23 std::cout << "p -- PLCP" << std::endl;
24 std::cout << "s -- Sampled LCP" << std::endl;
25 std::cout << "h -- Hybrid: PLCP and Sampled LCP" << std::endl;
26 std::cout << "l -- Locate" << std::endl;
27 std::cout << "v -- Verify results" << std::endl;
28 std::cout << std::endl;
32 std::string base_name = argv[1];
33 std::cout << "Base name: " << base_name << std::endl;
34 usint queries = atoi(argv[2]);
35 std::cout << "Number of queries: " << queries << std::endl;
36 usint runs = std::max(1, atoi(argv[3]));
37 std::cout << "Number of test runs: " << runs << std::endl;
39 std::string mode_string(argv[4]);
41 bool mode_direct = (mode_string.find('d') != std::string::npos);
42 bool mode_plcp = (mode_string.find('p') != std::string::npos);
43 bool mode_sampled = (mode_string.find('s') != std::string::npos);
44 bool mode_hybrid = (mode_string.find('h') != std::string::npos);
45 bool mode_locate = (mode_string.find('l') != std::string::npos);
46 bool mode_verify = (mode_string.find('v') != std::string::npos);
47 std::cout << "Modes: ";
48 if(mode_direct) { std::cout << "direct "; modes++; }
49 if(mode_plcp) { std::cout << "plcp "; modes++; }
50 if(mode_sampled) { std::cout << "sampled "; modes++; }
51 if(mode_hybrid) { std::cout << "hybrid "; modes++; }
52 if(mode_locate) { std::cout << "locate "; }
53 if(mode_verify) { std::cout << "verify"; }
54 std::cout << std::endl;
56 usint seed = 0xDEADBEEF;
61 std::cout << "Random seed: " << seed << std::endl;
62 std::cout << std::endl;
63 if(modes == 0 || queries == 0) { return 0; }
65 RLCSA rlcsa(base_name);
66 if((mode_plcp || mode_hybrid) && !rlcsa.supportsLocate())
68 std::cerr << "Error: Locate is not supported!" << std::endl;
72 rlcsa.reportSize(true);
75 if(mode_plcp || mode_hybrid)
77 std::string plcp_name = base_name + PLCP_EXTENSION;
78 std::ifstream plcp_file(plcp_name.c_str(), std::ios_base::binary);
81 std::cerr << "Error: Cannot open PLCP file!" << std::endl;
84 plcp = new RLEVector(plcp_file);
85 std::cout << "PLCP: " << (plcp->reportSize() / (double)MEGABYTE) << " MB" << std::endl;
92 std::string lcp_name = base_name + LCP_SAMPLES_EXTENSION;
93 std::ifstream lcp_file(lcp_name.c_str(), std::ios_base::binary);
96 std::cerr << "Error: Cannot open LCP sample file!" << std::endl;
100 lcp = new LCPSamples(lcp_file);
101 std::cout << "Sampled LCP: " << (lcp->reportSize() / (double)MEGABYTE) << " MB" << std::endl;
105 LCPSamples* minimal = 0;
108 std::string minimal_name = base_name + ".minimal";
109 std::ifstream minimal_file(minimal_name.c_str(), std::ios_base::binary);
112 std::cerr << "Error: Cannot open minimal LCP sample file!" << std::endl;
113 delete plcp; delete lcp;
116 minimal = new LCPSamples(minimal_file);
117 std::cout << "Minimal samples: " << (minimal->reportSize() / (double)MEGABYTE) << " MB" << std::endl;
118 minimal_file.close();
120 std::cout << std::endl;
123 usint* positions = new usint[queries];
124 usint* results1 = new usint[queries];
125 usint* results2 = new usint[queries];
126 usint* results3 = new usint[queries];
127 usint* results4 = new usint[queries];
128 usint* results5 = new usint[queries];
129 for(usint i = 0; i < queries; i++)
131 positions[i] = rand() % rlcsa.getSize();
137 std::cout << "Direct LCP computation:" << std::endl;
138 for(usint j = 0; j < runs; j++)
141 for(usint i = 0; i < queries; i++)
143 results1[i] = rlcsa.lcpDirect(positions[i]);
145 time = readTimer() - start;
146 std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
148 std::cout << std::endl;
153 std::cout << "Using PLCP:" << std::endl;
154 RLEVector::Iterator iter(*plcp);
155 for(usint j = 0; j < runs; j++)
158 for(usint i = 0; i < queries; i++)
160 usint pos = rlcsa.locate(positions[i]);
161 results2[i] = iter.select(pos) - 2 * pos;
163 time = readTimer() - start;
164 std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
166 std::cout << std::endl;
171 std::cout << "Using Sampled LCP:" << std::endl;
172 for(usint j = 0; j < runs; j++)
175 for(usint i = 0; i < queries; i++)
177 results3[i] = rlcsa.lcp(positions[i], *lcp);
179 time = readTimer() - start;
180 std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
182 std::cout << std::endl;
187 std::cout << "Using hybrid approach:" << std::endl;
188 for(usint j = 0; j < runs; j++)
191 for(usint i = 0; i < queries; i++)
193 results4[i] = rlcsa.lcp(positions[i], *minimal, *plcp);
195 time = readTimer() - start;
196 std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
198 std::cout << std::endl;
203 std::cout << "Locate:" << std::endl;
204 for(usint j = 0; j < runs; j++)
207 for(usint i = 0; i < queries; i++)
209 results5[i] = rlcsa.locate(positions[i]);
211 time = readTimer() - start;
212 std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
214 std::cout << std::endl;
217 if(mode_verify && modes > 1)
219 for(usint i = 0; i < queries; i++)
222 ok &= !mode_direct | !mode_plcp | (results1[i] == results2[i]);
223 ok &= !mode_direct | !mode_sampled | (results1[i] == results3[i]);
224 ok &= !mode_direct | !mode_hybrid | (results1[i] == results4[i]);
225 ok &= !mode_plcp | !mode_sampled | (results2[i] == results3[i]);
226 ok &= !mode_plcp | !mode_hybrid | (results2[i] == results4[i]);
227 ok &= !mode_sampled | !mode_hybrid | (results3[i] == results4[i]);
230 std::cout << "Query " << i << ": LCP[" << positions[i] << "] = ";
231 if(mode_direct) { std::cout << results1[i] << " (direct) "; }
232 if(mode_plcp) { std::cout << results2[i] << " (plcp) "; }
233 if(mode_sampled) { std::cout << results3[i] << " (sampled) "; }
234 if(mode_hybrid) { std::cout << results4[i] << " (hybrid) "; }
235 std::cout << std::endl;
241 delete[] results1; delete[] results2; delete[] results3; delete[] results4; delete[] results5;
242 delete plcp; delete lcp; delete minimal;