incbwt/lcp_test.cpp

   1 #include <algorithm>
   2 #include <cstdlib>
   3 #include <ctime>
   4 #include <fstream>
   5 #include <iostream>
   6
   7 #include "rlcsa.h"
   8 #include "misc/utils.h"
   9
  10
  11 using namespace CSA;
  12
  13
  14 int main(int argc, char** argv)
  15 {
  16   std::cout << "RLCSA LCP test" << std::endl;
  17   if(argc < 5)
  18   {
  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;
  29     return 1;
  30   }
  31
  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;
  38
  39   std::string mode_string(argv[4]);
  40   usint modes = 0;
  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;
  55
  56   usint seed = 0xDEADBEEF;
  57   if(argc > 5)
  58   {
  59     seed = atoi(argv[5]);
  60   }
  61   std::cout << "Random seed: " << seed << std::endl;
  62   std::cout << std::endl;
  63   if(modes == 0 || queries == 0) { return 0; }
  64
  65   RLCSA rlcsa(base_name);
  66   if((mode_plcp || mode_hybrid) && !rlcsa.supportsLocate())
  67   {
  68     std::cerr << "Error: Locate is not supported!" << std::endl;
  69     return 2;
  70   }
  71   rlcsa.printInfo();
  72   rlcsa.reportSize(true);
  73
  74   RLEVector* plcp = 0;
  75   if(mode_plcp || mode_hybrid)
  76   {
  77     std::string plcp_name = base_name + PLCP_EXTENSION;
  78     std::ifstream plcp_file(plcp_name.c_str(), std::ios_base::binary);
  79     if(!plcp_file)
  80     {
  81       std::cerr << "Error: Cannot open PLCP file!" << std::endl;
  82       return 3;
  83     }
  84     plcp = new RLEVector(plcp_file);
  85     std::cout << "PLCP:            " << (plcp->reportSize() / (double)MEGABYTE) << " MB" << std::endl;
  86     plcp_file.close();
  87   }
  88
  89   LCPSamples* lcp = 0;
  90   if(mode_sampled)
  91   {
  92     std::string lcp_name = base_name + LCP_SAMPLES_EXTENSION;
  93     std::ifstream lcp_file(lcp_name.c_str(), std::ios_base::binary);
  94     if(!lcp_file)
  95     {
  96       std::cerr << "Error: Cannot open LCP sample file!" << std::endl;
  97       delete plcp;
  98       return 4;
  99     }
 100     lcp = new LCPSamples(lcp_file);
 101     std::cout << "Sampled LCP:     " << (lcp->reportSize() / (double)MEGABYTE) << " MB" << std::endl;
 102     lcp_file.close();
 103   }
 104
 105   LCPSamples* minimal = 0;
 106   if(mode_hybrid)
 107   {
 108     std::string minimal_name = base_name + ".minimal";
 109     std::ifstream minimal_file(minimal_name.c_str(), std::ios_base::binary);
 110     if(!minimal_file)
 111     {
 112       std::cerr << "Error: Cannot open minimal LCP sample file!" << std::endl;
 113       delete plcp; delete lcp;
 114       return 5;
 115     }
 116     minimal = new LCPSamples(minimal_file);
 117     std::cout << "Minimal samples: " << (minimal->reportSize() / (double)MEGABYTE) << " MB" << std::endl;
 118     minimal_file.close();
 119   }
 120   std::cout << std::endl;
 121
 122   srand(seed);
 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++)
 130   {
 131     positions[i] = rand() % rlcsa.getSize();
 132   }
 133   double start, time;
 134
 135   if(mode_direct)
 136   {
 137     std::cout << "Direct LCP computation:" << std::endl;
 138     for(usint j = 0; j < runs; j++)
 139     {
 140       start = readTimer();
 141       for(usint i = 0; i < queries; i++)
 142       {
 143         results1[i] = rlcsa.lcpDirect(positions[i]);
 144       }
 145       time = readTimer() - start;
 146       std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
 147     }
 148     std::cout << std::endl;
 149   }
 150
 151   if(mode_plcp)
 152   {
 153     std::cout << "Using PLCP:" << std::endl;
 154     RLEVector::Iterator iter(*plcp);
 155     for(usint j = 0; j < runs; j++)
 156     {
 157       start = readTimer();
 158       for(usint i = 0; i < queries; i++)
 159       {
 160         usint pos = rlcsa.locate(positions[i]);
 161         results2[i] = iter.select(pos) - 2 * pos;
 162       }
 163       time = readTimer() - start;
 164       std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
 165     }
 166     std::cout << std::endl;
 167   }
 168
 169   if(mode_sampled)
 170   {
 171     std::cout << "Using Sampled LCP:" << std::endl;
 172     for(usint j = 0; j < runs; j++)
 173     {
 174       start = readTimer();
 175       for(usint i = 0; i < queries; i++)
 176       {
 177         results3[i] = rlcsa.lcp(positions[i], *lcp);
 178       }
 179       time = readTimer() - start;
 180       std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
 181     }
 182     std::cout << std::endl;
 183   }
 184
 185   if(mode_hybrid)
 186   {
 187     std::cout << "Using hybrid approach:" << std::endl;
 188     for(usint j = 0; j < runs; j++)
 189     {
 190       start = readTimer();
 191       for(usint i = 0; i < queries; i++)
 192       {
 193         results4[i] = rlcsa.lcp(positions[i], *minimal, *plcp);
 194       }
 195       time = readTimer() - start;
 196       std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
 197     }
 198     std::cout << std::endl;
 199   }
 200
 201   if(mode_locate)
 202   {
 203     std::cout << "Locate:" << std::endl;
 204     for(usint j = 0; j < runs; j++)
 205     {
 206       start = readTimer();
 207       for(usint i = 0; i < queries; i++)
 208       {
 209         results5[i] = rlcsa.locate(positions[i]);
 210       }
 211       time = readTimer() - start;
 212       std::cout << queries << " queries in " << time << " seconds (" << (queries / time) << " / s)" << std::endl;
 213     }
 214     std::cout << std::endl;
 215   }
 216
 217   if(mode_verify && modes > 1)
 218   {
 219     for(usint i = 0; i < queries; i++)
 220     {
 221       bool ok = true;
 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]);
 228       if(!ok)
 229       {
 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;
 236       }
 237     }
 238   }
 239
 240   delete[] positions;
 241   delete[] results1; delete[] results2; delete[] results3; delete[] results4; delete[] results5;
 242   delete plcp; delete lcp; delete minimal;
 243   return 0;
 244 }