FMIndexBuilder.cpp

   1 #include "incbwt/rlcsa_builder.h"
   2 #include "incbwt/bits/deltavector.h"
   3
   4 #include "FMIndexBuilder.h"
   5 #include "FMIndex.h"
   6
   7 using std::string;
   8
   9 namespace SXSI
  10 {
  11
  12 struct TCBuilderRep
  13 {
  14     unsigned samplerate;
  15     CSA::RLCSABuilder * sa;
  16
  17     ulong n;
  18     // Total number of texts in the collection
  19     unsigned numberOfTexts;
  20     // Length of the longest text
  21     ulong maxTextLength;
  22     ulong numberOfSamples;
  23
  24     CSA::DeltaEncoder *notIndexed; // Doc IDs of those texts that are excluded from index.
  25     string niText; // Texts that are not indexed.
  26
  27 #ifdef TCB_TEST_BWT
  28     DynFMI *dynFMI;
  29 #endif
  30 };
  31
  32 /**
  33  * Init text collection
  34  *
  35  */
  36 FMIndexBuilder::FMIndexBuilder(unsigned samplerate, ulong estimatedInputLength)
  37     : p_(new struct TCBuilderRep())
  38 {
  39     p_->n = 0;
  40     p_->samplerate = samplerate;
  41     p_->numberOfTexts = 0;
  42     p_->numberOfSamples = 0;
  43     p_->maxTextLength = 0;
  44     p_->notIndexed = new CSA::DeltaEncoder(32); // Block size of 32
  45     p_->niText = "";
  46
  47     // Current params: 8 bytes, no samples, buffer size n/10 bytes.
  48     // Buffer size is always at least 15MB:
  49     if (estimatedInputLength < TEXTCOLLECTION_DEFAULT_INPUT_LENGTH)
  50         estimatedInputLength = TEXTCOLLECTION_DEFAULT_INPUT_LENGTH;
  51     p_->sa = new CSA::RLCSABuilder(8, 0, estimatedInputLength/10);
  52     assert(p_->sa->isOk());
  53
  54 #ifdef TCB_TEST_BWT
  55     uchar temp[256];
  56     for (unsigned i = 0; i < 255; ++i)
  57         temp[i] = i+1;
  58     temp[255] = 0;
  59     p_->dynFMI = new DynFMI(temp, 1, 255, false);
  60 #endif
  61 }
  62
  63 FMIndexBuilder::~FMIndexBuilder()
  64 {
  65 #ifdef TCB_TEST_BWT
  66     delete p_->dynFMI;
  67 #endif
  68
  69     delete p_->sa;
  70     delete p_->notIndexed;
  71     delete p_;
  72 }
  73
  74 void FMIndexBuilder::InsertText(uchar const * text, bool index)
  75 {
  76     TextCollection::TextPosition m = std::strlen((char *)text) + 1;
  77     if (m <= 1)
  78     {
  79         // FIXME indexing empty texts
  80         std::cerr << "FMIndexBuilder::InsertText() error: can not index empty texts!" << std::endl;
  81         exit(1);
  82     }
  83
  84     p_->numberOfTexts ++;
  85
  86     if (index)
  87     {
  88         /**
  89          * Insert text into the index
  90          */
  91         p_->n += m;
  92         p_->numberOfSamples += (m-1)/p_->samplerate;
  93
  94         if (m > p_->maxTextLength)
  95             p_->maxTextLength = m; // Store length of the longest text seen so far.
  96
  97         p_->sa->insertSequence((char*)text, m-1, 0);
  98         assert(p_->sa->isOk());
  99     }
 100     else
 101     {
 102         /**
 103          * Insert text only to TextStorage
 104          */
 105         p_->notIndexed->setBit(p_->numberOfTexts - 1);
 106         p_->niText.append((const char *)text, m);
 107     }
 108 }
 109
 110
 111 TextCollection * FMIndexBuilder::InitTextCollection(char type)
 112 {
 113     uchar * bwt = 0;
 114     CSA::usint length = 0;
 115     if (p_->numberOfTexts == 0)
 116     {
 117         p_->numberOfTexts ++; // Add one empty text
 118         bwt = new uchar[2];
 119         bwt[0] = '\0';
 120         bwt[1] = '\0';
 121         length = 1;
 122         p_->maxTextLength = 1;
 123     }
 124     else
 125     {
 126         bwt = (uchar *)p_->sa->getBWT(length);
 127         delete p_->sa;
 128         p_->sa = 0;
 129
 130         assert(length == p_->n);
 131     }
 132
 133     p_->notIndexed->setBit(p_->numberOfTexts); // FIXME CSA::DeltaVector can not be all 0's
 134     CSA::DeltaVector deltav(*p_->notIndexed, p_->numberOfTexts+1);
 135     delete p_->notIndexed;
 136     p_->notIndexed = 0;
 137
 138     TextCollection *result = new FMIndex(bwt, (ulong)length,
 139                    p_->samplerate, p_->numberOfTexts, p_->maxTextLength, p_->numberOfSamples,
 140                    deltav, p_->niText, type);
 141
 142     return result;
 143 }
 144
 145
 146 } // namespace SXSI