SWCSAWrapper.h

   1 /******************************************************************************
   2  *   Copyright (C) 2010 by Niko Välimäki                                      *
   3  *                                                                            *
   4  *   FMIndex implementation for the TextCollection interface                  *
   5  *                                                                            *
   6  *   This program is free software; you can redistribute it and/or modify     *
   7  *   it under the terms of the GNU Lesser General Public License as published *
   8  *   by the Free Software Foundation; either version 2 of the License, or     *
   9  *   (at your option) any later version.                                      *
  10  *                                                                            *
  11  *   This program is distributed in the hope that it will be useful,          *
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  14  *   GNU Lesser General Public License for more details.                      *
  15  *                                                                            *
  16  *   You should have received a copy of the GNU Lesser General Public License *
  17  *   along with this program; if not, write to the                            *
  18  *   Free Software Foundation, Inc.,                                          *
  19  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            *
  20  *****************************************************************************/
  21
  22 #ifndef _SWCSAWrapper_H_
  23 #define _SWCSAWrapper_H_
  24
  25 #include "TextCollection.h"
  26
  27 #include "TextStorage.h"
  28
  29 #include "incbwt/bits/deltavector.h"
  30 // Re-define word size to ulong:
  31 #undef W
  32 #if __WORDSIZE == 64
  33 #   define W 64
  34 #else
  35 #   define W 32
  36 #endif
  37
  38 #define SWCSAWRAPPER_VERSION_FLAG 101
  39
  40 #include "swcsa/utils/defValues.h"
  41 #include "swcsa/utils/valstring.h"
  42 #include "swcsa/interface.h"
  43
  44 #include <set>
  45 #include <string>
  46
  47 namespace SXSI
  48 {
  49
  50 /**
  51  * Partial implementation of the TextCollection interface
  52  *
  53  * Supports index construction, save, load and simple search.
  54  * Use FMIndex implementation for full support.
  55  */
  56 class SWCSAWrapper : public SXSI::TextCollection {
  57 public:
  58     SWCSAWrapper(uchar * text, ulong length, unsigned samplerate,
  59                  unsigned numberOfTexts_)
  60         : index(0), offsets(0), n(length), seSize(0), numberOfTexts(numberOfTexts_)
  61     {
  62         // Inicializes the arrays used to detect if a char is valid or not.
  63         StartValid();
  64
  65         // Delta encoded bitvector of text offsets.
  66         CSA::DeltaEncoder encoder(32);
  67         encoder.setBit(0); // Start of the first text.
  68
  69         // Construct offset map from words to text elements
  70         seSize = 0;
  71         {
  72             uchar const *pbeg,*pend;
  73
  74             pbeg = text;
  75             pend = text+length;
  76
  77             while (pbeg <pend) {
  78                 //parsing either a word or separator.
  79                 unsigned size=0;
  80
  81                 if (*pbeg == 0)
  82                 {
  83                     std::cerr << "SWCSAWrapper constructor: assert failed, *pbeg == 0" << std::endl;
  84                     std::exit(1);
  85                 }
  86
  87                 if (_Valid[*pbeg]) {   //alphanumerical data
  88                     while ( (size<MAX_SIZE_OF_WORD) && (pbeg<pend)&& ( _Valid[*pbeg] )) {size++;pbeg++;}
  89                 }
  90                 else
  91                 {
  92                     if (*pbeg != ' ') { //a separator comes starting in ' ' comes, so it is a new word
  93                         while ( (size<MAX_SIZE_OF_GAP) && (pbeg<pend) &&  (!_Valid[*pbeg] && *pbeg != 0)) {size++;pbeg++;}
  94
  95                     }
  96                     else {  //a  SPACE comes, so we have to test if next character is alphanumerical or not
  97                         pbeg++;
  98                         if (pbeg >= pend) {size++;}  // a unique BLANK at the end of the file.
  99                         else {
 100                             if (_Valid [*pbeg] ) {
 101                                 while ( (size<MAX_SIZE_OF_WORD) && (pbeg<pend)&& ( _Valid[*pbeg] )) {size++;pbeg++;}
 102                             }
 103                             else {   // a "separator word" ...
 104                                 size++; //the prev BLANK...
 105                                 while ( (size<MAX_SIZE_OF_GAP) && (pbeg<pend) &&  (!_Valid[*pbeg] && *pbeg != 0)) {size++;pbeg++;}
 106                             }//else {  // a "separator word"
 107                         }//else ... not a unique BLANK AT THE END.
 108                     }//else ... starting by a BLANK...
 109                 }
 110
 111                 if (*pbeg == 0)
 112                 {
 113                     encoder.setBit(seSize+1);
 114                     pbeg ++; // Does not affect size of word (skips the 0-byte)
 115                 }
 116                 if (size == 0)
 117                 {
 118                     std::cerr << "SWCSAWrapper constructor: assert failed, size == 0" << std::endl;
 119                     std::exit(1);
 120                 }
 121
 122                 seSize ++;
 123             }//while pbeg<pend
 124         }//1st pass ends
 125         fprintf(stderr,"\n-----------------------\nnumber of words = %lu\n------------------------\n", seSize);
 126         encoder.setBit(seSize);
 127         offsets = new CSA::DeltaVector(encoder, seSize+1);
 128         std::cerr << "Number of texts: " << numberOfTexts << " vs " << offsets->rank(seSize - 1) << std::endl;
 129
 130         char opt[100];
 131         snprintf(opt, 99, "sA=%u;sAinv=%u;sPsi=%u", samplerate, samplerate, samplerate);
 132
 133         int r = build_index(text, n, opt, &index);
 134         if (r)
 135         {
 136             std::cout << "SWCSAWrapper error: " <<  error_index(r) << std::endl;
 137             std::exit(r);
 138         }
 139     }
 140
 141     ~SWCSAWrapper()
 142     {
 143         int r = free_index (index);
 144         if (r)
 145         {
 146             std::cout << "SWCSAWrapper destructor error: " <<  error_index(r) << std::endl;
 147             std::exit(r);
 148         }
 149         index = 0;
 150         delete offsets; offsets = 0;
 151     }
 152
 153     bool EmptyText(DocId k) const
 154     {
 155         assert(k < (DocId)numberOfTexts);
 156         return false; // Empty texts are not indexed
 157     }
 158
 159     /**
 160      * Extracting one text.
 161      *
 162      * Call DeleteText() for each pointer returned by GetText()
 163      * to avoid possible memory leaks.
 164      */
 165     uchar * GetText(DocId i) const
 166     {
 167         return GetText(i, i);
 168     }
 169     void DeleteText(uchar *text) const
 170     {
 171         free(text);
 172     }
 173
 174     /**
 175      * Returns a pointer to the beginning of texts i, i+1, ..., j.
 176      * Texts are separated by a '\0' byte.
 177      *
 178      * Call DeleteText() for each pointer returned by GetText()
 179      * to avoid possible memory leaks.
 180      */
 181     uchar * GetText(DocId i, DocId j) const
 182     {
 183         ulong from, to, l;
 184         uchar *text;
 185         from = offsets->select(i);
 186         to = offsets->select(i+1); // ADD one 1-bit in to end!!!
 187
 188         int r = extractWords(index, from, to, &text, &l);
 189         if (r)
 190         {
 191             std::cout << "SWCSAWrapper error: " <<  error_index(r) << std::endl;
 192           std::exit(r);
 193         }
 194         text[l] = 0;
 195         return text;
 196     }
 197
 198     bool IsPrefix(uchar const *) const { unsupported(); return false; };
 199     bool IsSuffix(uchar const *) const { unsupported(); return false; };
 200     bool IsEqual(uchar const *) const { unsupported(); return false; };
 201     bool IsContains(uchar const *) const { unsupported(); return false; };
 202     bool IsLessThan(uchar const *) const { unsupported(); return false; };
 203
 204     bool IsPrefix(uchar const *, DocId, DocId) const { unsupported(); return false; };
 205     bool IsSuffix(uchar const *, DocId, DocId) const { unsupported(); return false; };
 206     bool IsEqual(uchar const *, DocId, DocId) const { unsupported(); return false; };
 207     bool IsContains(uchar const *, DocId, DocId) const { unsupported(); return false; };
 208     bool IsLessThan(uchar const *, DocId, DocId) const { unsupported(); return false; };
 209
 210     ulong Count(uchar const *pattern) const
 211     {
 212         ulong occs = 0;
 213         // FIXME Const correctness is broken!
 214         int r = count (index, (uchar *)pattern, std::strlen((char const *)pattern), &occs);
 215         if (r)
 216         {
 217             std::cout << "SWCSAWrapper::Count error " <<  error_index(r) << std::endl;
 218             std::exit(r);
 219         }
 220         return occs;
 221     }
 222     unsigned CountPrefix(uchar const *) const { unsupported(); return 0; };
 223     unsigned CountSuffix(uchar const *) const { unsupported(); return 0; };
 224     unsigned CountEqual(uchar const *) const { unsupported(); return 0; };
 225     unsigned CountContains(uchar const *) const { unsupported(); return 0; };
 226     unsigned CountLessThan(const unsigned char*) const { unsupported(); return 0; };
 227
 228     unsigned CountPrefix(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 229     unsigned CountSuffix(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 230     unsigned CountEqual(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 231     unsigned CountContains(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 232     unsigned CountLessThan(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 233
 234     // Definition of document_result is inherited from SXSI::TextCollection.
 235     document_result Prefix(uchar const *) const { unsupported(); return document_result(); };
 236     document_result Suffix(uchar const *) const { unsupported(); return document_result(); };
 237     document_result Equal(uchar const *) const { unsupported(); return document_result(); };
 238     document_result Contains(uchar const *pattern) const
 239     {
 240         ulong *occ = 0, numocc = 0;
 241         // FIXME Const correctness is broken!
 242         int r = locateWord(index, (uchar *)pattern, std::strlen((char const *)pattern), &occ, &numocc, 0);
 243         if (r)
 244         {
 245             std::cout << "SWCSAWrapper::Contains error: " <<  error_index(r) << std::endl;
 246             std::exit(r);
 247         }
 248
 249         document_result dr;
 250         dr.reserve(numocc+1);
 251         for (ulong i = 0; i < numocc; ++i)
 252             dr.push_back(offsets->rank(occ[i])-1);
 253
 254         free(occ);
 255         return dr;
 256     }
 257     document_result LessThan(uchar const *) const { unsupported(); return document_result(); };
 258     document_result KMismaches(uchar const *, unsigned) const { unsupported(); return document_result(); };
 259     document_result KErrors(uchar const *, unsigned) const { unsupported(); return document_result(); };
 260
 261     document_result Prefix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 262     document_result Suffix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 263     document_result Equal(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 264     document_result Contains(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 265     document_result LessThan(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 266
 267     // Definition of full_result is inherited from SXSI::TextCollection.
 268     full_result FullContains(uchar const *) const { unsupported(); return full_result(); };
 269     full_result FullContains(uchar const *, DocId, DocId) const { unsupported(); return full_result(); };
 270     full_result FullKMismatches(uchar const *, unsigned) const { unsupported(); return full_result(); };
 271     full_result FullKErrors(uchar const *, unsigned) const { unsupported(); return full_result(); };
 272
 273     // Index from/to disk
 274     SWCSAWrapper(FILE *file, char const *filename)
 275         : index(0), offsets(0), n(0), seSize(0), numberOfTexts(0)
 276     {
 277         uchar verFlag = 0;
 278         if (std::fread(&verFlag, 1, 1, file) != 1)
 279             throw std::runtime_error("SWCSAWrapper::Load(): file read error (version flag).");
 280         if (verFlag != SWCSAWRAPPER_VERSION_FLAG)
 281             throw std::runtime_error("SWCSAWrapper::Load(): invalid save file version.");
 282
 283         if (std::fread(&(this->n), sizeof(TextPosition), 1, file) != 1)
 284             throw std::runtime_error("SWCSAWrapper::Load(): file read error (n).");
 285         if (std::fread(&seSize, sizeof(ulong), 1, file) != 1)
 286             throw std::runtime_error("SWCSAWrapper::Load(): file read error (seSize).");
 287         if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
 288             throw std::runtime_error("FMIndex::Load(): file read error (numberOfTexts).");
 289
 290         offsets = new CSA::DeltaVector(file);
 291
 292         // FIXME Const correctness is broken!
 293         int r = load_index((char *)filename, &index);
 294         if (r)
 295         {
 296             std::cout << "SWCSAWrapper::Save error: " <<  error_index(r) << std::endl;
 297             std::exit(r);
 298         }
 299     }
 300
 301     void Save(FILE *file, char const *filename) const
 302     {
 303         const char type = 'W';
 304         // Saving type info:
 305         if (std::fwrite(&type, 1, 1, file) != 1)
 306             throw std::runtime_error("SWCSAWrapper::Save(): file write error (type flag).");
 307
 308         const uchar ver = SWCSAWRAPPER_VERSION_FLAG;
 309         // Saving version info:
 310         if (std::fwrite(&ver, 1, 1, file) != 1)
 311             throw std::runtime_error("SWCSAWrapper::Save(): file write error (version flag).");
 312
 313         if (std::fwrite(&(this->n), sizeof(TextPosition), 1, file) != 1)
 314             throw std::runtime_error("SWCSAWrapper::Save(): file write error (n).");
 315         if (std::fwrite(&(this->seSize), sizeof(ulong), 1, file) != 1)
 316             throw std::runtime_error("SWCSAWrapper::Save(): file write error (seSize).");
 317         if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
 318             throw std::runtime_error("SWCSAWrapper::Save(): file write error (numberOfTexts).");
 319
 320         offsets->writeTo(file);
 321
 322         // FIXME Const correctness is broken!
 323         int r = save_index(index, (char *)filename);
 324         if (r)
 325         {
 326             std::cout << "SWCSAWrapper::Save error: " <<  error_index(r) << std::endl;
 327             std::exit(r);
 328         }
 329     }
 330
 331 private:
 332     void *index;
 333     CSA::DeltaVector *offsets;
 334
 335     TextPosition n;
 336     ulong seSize;
 337
 338     // Total number of texts in the collection
 339     unsigned numberOfTexts;
 340
 341     void unsupported() const
 342     {
 343         std::cerr << std::endl << "-------------------------------------------------------------\n"
 344             << "SWCSAWrapper: unsupported method!\nSee SWCSAWrapper.h for more details.\n"
 345             << "The default index (FMIndex) implements this method!" << std::endl;
 346         std::exit(5);
 347     }
 348 }; // class SWCSAWrapper
 349
 350 } // namespace SXSI
 351
 352 #endif