RLCSAWrapper.h

   1 /******************************************************************************
   2  *   Copyright (C) 2010 by Niko Välimäki                                      *
   3  *                                                                            *
   4  *   RLCSA 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 _RLCSAWrapper_H_
  23 #define _RLCSAWrapper_H_
  24
  25 #include "TextCollection.h"
  26 #include "IndelQuery.h"
  27
  28 #include "incbwt/rlcsa.h"
  29
  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 #include <stdexcept>
  39 #include <set>
  40 #include <string>
  41
  42 namespace SXSI
  43 {
  44
  45 /**
  46  * Partial implementation of the TextCollection interface
  47  *
  48  * Supports index construction, save, load and simple search.
  49  * Use FMIndex implementation for full support.
  50  */
  51 class RLCSAWrapper : public SXSI::TextCollection
  52 {
  53 public:
  54     RLCSAWrapper(const CSA::RLCSA* index)
  55         : rlcsa(index)
  56     {
  57         // Init the edit distance look-up tables
  58         MyersEditDistanceIncremental::initMyersFourRussians();
  59     }
  60
  61     ~RLCSAWrapper()
  62     {
  63         delete rlcsa; rlcsa = 0;
  64     }
  65
  66     bool EmptyText(DocId k) const
  67     {
  68         return false; // Empty texts are not indexed
  69     }
  70
  71     /**
  72      * Extracting one text.
  73      *
  74      * Call DeleteText() for each pointer returned by GetText()
  75      * to avoid possible memory leaks.
  76      */
  77     uchar * GetText(DocId i) const
  78     {
  79         return rlcsa->display(i);
  80     }
  81     void DeleteText(uchar *text) const
  82     {
  83         delete [] text;
  84     }
  85
  86     /**
  87      * Returns a pointer to the beginning of texts i, i+1, ..., j.
  88      * Texts are separated by a '\0' byte.
  89      *
  90      * Call DeleteText() for each pointer returned by GetText()
  91      * to avoid possible memory leaks.
  92      */
  93     uchar * GetText(DocId i, DocId j) const
  94     {
  95         std::cerr << "RLCSAWrapper::GetText(i,j): unsupported method!" << std::endl
  96                   << "Use the default (FMIndex) text collection instead!" << std::endl;
  97         std::exit(1);
  98     }
  99
 100     bool IsPrefix(uchar const *) const { unsupported(); return false; };
 101     bool IsSuffix(uchar const *) const { unsupported(); return false; };
 102     bool IsEqual(uchar const *) const { unsupported(); return false; };
 103     bool IsContains(uchar const *) const { unsupported(); return false; };
 104     bool IsLessThan(uchar const *) const { unsupported(); return false; };
 105
 106     bool IsPrefix(uchar const *, DocId, DocId) const { unsupported(); return false; };
 107     bool IsSuffix(uchar const *, DocId, DocId) const { unsupported(); return false; };
 108     bool IsEqual(uchar const *, DocId, DocId) const { unsupported(); return false; };
 109     bool IsContains(uchar const *, DocId, DocId) const { unsupported(); return false; };
 110     bool IsLessThan(uchar const *, DocId, DocId) const { unsupported(); return false; };
 111
 112     ulong Count(uchar const *pattern) const
 113     {
 114 //        std::pair<TextPosition, TextPosition> p = backwards(pattern);
 115         CSA::pair_type p = rlcsa->count(std::string((char const *)pattern));
 116
 117         if (p.first <= p.second)
 118             return p.second - p.first + 1;
 119         else
 120             return 0;
 121     }
 122
 123     unsigned CountPrefix(uchar const *) const { unsupported(); return 0; };
 124     unsigned CountSuffix(uchar const *) const { unsupported(); return 0; };
 125     unsigned CountEqual(uchar const *) const { unsupported(); return 0; };
 126     unsigned CountContains(uchar const *) const { unsupported(); return 0; };
 127     unsigned CountLessThan(const unsigned char*) const { unsupported(); return 0; };
 128
 129     unsigned CountPrefix(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 130     unsigned CountSuffix(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 131     unsigned CountEqual(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 132     unsigned CountContains(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 133     unsigned CountLessThan(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 134
 135     // Definition of document_result is inherited from SXSI::TextCollection.
 136     document_result Prefix(uchar const *) const { unsupported(); return document_result(); };
 137     document_result Suffix(uchar const *) const { unsupported(); return document_result(); };
 138     document_result Equal(uchar const *) const { unsupported(); return document_result(); };
 139
 140     document_result Contains(uchar const *pattern) const
 141     {
 142         /*************************************************************************
 143          * Approximate pattern matching
 144          *
 145          * Using suffix filters. Has to enumerate *all* approx. occurrences (sloooow...)
 146          * instead of just returning the best occurrence (which is usually much faster).
 147          *
 148          * Query format: contains("APM 3 GATTACA")
 149          * where
 150          *          "APM" is the keyword for approximate queries.
 151          *            "3" is the maximum edit distance allowed.
 152          *      "GATTACA" is the query word to be aligned.
 153          */
 154         if (strncmp((char const *)pattern, "APM ", 4) == 0)
 155         {
 156             // Edit distance allowed.
 157             int k = std::atoi((char const *)pattern + 4);
 158             if (k < 0 || k == INT_MAX || k == INT_MIN)
 159                 goto exact_pattern_matching; // Invalid format
 160
 161             // Find the start of the pattern (i.e. the second ' ')
 162             uchar const * tmp = pattern + 4;
 163             while (*tmp != ' ' && *tmp != 0) ++tmp;
 164             if (*tmp != ' ' || tmp == pattern + 4)
 165                 goto exact_pattern_matching; // Invalid format
 166
 167             IndelQuery iq(this);
 168             //std::cerr << "Pattern: " << tmp+1 << ", k = " << k << std::endl;
 169             return iq.align(tmp+1, k);
 170         }
 171
 172         /*************************************************************************
 173          * Exact pattern matching
 174          */
 175     exact_pattern_matching:
 176         CSA::pair_type p = rlcsa->count(std::string((char const *)pattern));
 177         if (p.first > p.second)
 178             return document_result();
 179
 180         document_result dr;
 181         dr.reserve(p.second - p.first + 2);
 182         for (ulong i = p.first; i <= p.second; ++i)
 183             dr.push_back(rlcsa->getSequenceForPosition(rlcsa->locate(i)));
 184         return dr;
 185     }
 186     document_result LessThan(uchar const *) const { unsupported(); return document_result(); };
 187     document_result KMismaches(uchar const *, unsigned) const { unsupported(); return document_result(); };
 188     document_result KErrors(uchar const *, unsigned) const { unsupported(); return document_result(); };
 189
 190     document_result Prefix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 191     document_result Suffix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 192     document_result Equal(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 193     document_result Contains(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 194     document_result LessThan(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 195
 196     // Definition of full_result is inherited from SXSI::TextCollection.
 197     full_result FullContains(uchar const *) const { unsupported(); return full_result(); };
 198     full_result FullContains(uchar const *, DocId, DocId) const { unsupported(); return full_result(); };
 199     full_result FullKMismatches(uchar const *, unsigned) const { unsupported(); return full_result(); };
 200     full_result FullKErrors(uchar const *, unsigned) const { unsupported(); return full_result(); };
 201
 202     // Index from/to disk
 203     RLCSAWrapper(FILE *file, char const *filename)
 204         : rlcsa(new CSA::RLCSA(std::string(filename)))
 205     { /* NOP */ }
 206
 207     void Save(FILE *file, char const *filename) const
 208     {
 209         const char type = 'R';
 210         // Saving type info:
 211         if (std::fwrite(&type, 1, 1, file) != 1)
 212             throw std::runtime_error("RLCSAWrapper::Save(): file write error (type flag).");
 213
 214         this->rlcsa->writeTo(std::string(filename));
 215     }
 216
 217     TextCollection::TextPosition getLength() const
 218     {
 219         return this->rlcsa->getSize() + this->rlcsa->getNumberOfSequences();
 220     }
 221
 222     inline TextCollection::TextPosition LF(uchar c, TextPosition i) const
 223     {
 224         ++i;
 225         if(i < this->rlcsa->getNumberOfSequences())
 226             return rlcsa->C(c);
 227         return rlcsa->LF(i - this->rlcsa->getNumberOfSequences(), c);
 228     }
 229
 230     uchar* getSuffix(TextPosition pos, unsigned l) const
 231     {
 232         ++pos;
 233         uchar* text = new uchar[l + 1];
 234
 235         if(l == 0 || pos < this->rlcsa->getNumberOfSequences())
 236         {
 237             text[0] = 0;
 238             return text;
 239         }
 240         pos -= this->rlcsa->getNumberOfSequences();
 241
 242         unsigned n = rlcsa->displayFromPosition(pos, l, text);
 243         text[n] = 0;
 244         return text;
 245     }
 246
 247     DocId getDoc(TextPosition i) const
 248     {
 249         if(i < this->rlcsa->getNumberOfSequences())
 250             return i;
 251
 252         CSA::pair_type pt = rlcsa->getRelativePosition(this->rlcsa->locate(i - this->rlcsa->getNumberOfSequences()));
 253         return pt.first;
 254     }
 255
 256 private:
 257     const CSA::RLCSA* rlcsa;
 258
 259 /*    std::pair<TextPosition, TextPosition> backwards(uchar const *pattern) const
 260     {
 261         TextPosition i = std::strlen((char const *)pattern) - 1;
 262         int c = (int)pattern[i];
 263
 264         std::cerr << "\nFirst symb = " << (char)c << std::endl;
 265
 266         TextPosition sp = LF(c, -1);
 267         TextPosition ep = LF(c, getLength()-1) - 1;
 268         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 269         while (sp<=ep && i>=1)
 270         {
 271             c = (int)pattern[--i];
 272             sp = LF(c, sp-1);
 273             ep = LF(c, ep)-1;
 274             printf("new: c = %c, sp = %lu, ep = %lu\n", pattern[i], sp, ep);
 275         }
 276
 277         return std::make_pair(sp, ep);
 278         }*/
 279
 280     void unsupported() const
 281     {
 282         std::cerr << std::endl << "-------------------------------------------------------------\n"
 283             << "RLCSAWrapper: unsupported method!\nSee RLCSAWrapper.h for more details.\n"
 284             << "The default index (FMIndex) implements this method!" << std::endl;
 285         std::exit(5);
 286     }
 287 }; // class RLCSAWrapper
 288
 289 } // namespace SXSI
 290
 291 #endif