CSA.h

   1 /******************************************************************************
   2  *   Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki                *
   3  *                                                                            *
   4  *                                                                            *
   5  *   This program is free software; you can redistribute it and/or modify     *
   6  *   it under the terms of the GNU Lesser General Public License as published *
   7  *   by the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                      *
   9  *                                                                            *
  10  *   This program is distributed in the hope that it will be useful,          *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  13  *   GNU Lesser General Public License for more details.                      *
  14  *                                                                            *
  15  *   You should have received a copy of the GNU Lesser General Public License *
  16  *   along with this program; if not, write to the                            *
  17  *   Free Software Foundation, Inc.,                                          *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            *
  19  *****************************************************************************/
  20
  21 #ifndef _CSA_H_
  22 #define _CSA_H_
  23 #include "dynFMI.h"
  24 #include "BitRank.h"
  25 #include "TextCollection.h"
  26 #include "BlockArray.h"
  27 #include "RLWaveletTree.h"
  28 #include <set>
  29 #include <vector>
  30
  31 // Include  from XMLTree/libcds
  32 #include <basics.h>
  33 #include <static_bitsequence.h>
  34 #include <alphabet_mapper.h>
  35 #include <static_sequence.h>
  36
  37 /**
  38  * Implementation of the TextCollection interface
  39  *
  40  * Implementation notes:
  41  *
  42  * Dynamic construction (via InsertText()) uses dynamic (balanced) wavelet tree
  43  * which requires O(n log \sigma) bits of memory. If we know the distribution
  44  * of characters beforehand, space can easily be made O(nH_0).
  45  *
  46  * The method MakeStatic() constructs a Succinct Suffix Array with a huffman
  47  * shaped wavelet tree. This structure achieves only zero'th order entropy. (FIXME)
  48  *
  49  * Query methods Prefix, Suffix, Equal, Contains and LessThan can be used
  50  * with any FM-index variant supporting LF-mapping.
  51  */
  52 class CSA : public SXSI::TextCollection {
  53 public:
  54     /**
  55      * Constructor with (default) samplerate
  56      */
  57     explicit CSA(unsigned);
  58     ~CSA();
  59     /**
  60      * Following functions implement the interface described in TextCollection.h.
  61      * For details/documentation, see TextCollection.h.
  62      */
  63     void InsertText(uchar const *);
  64     void MakeStatic();
  65     bool EmptyText(DocId) const;
  66     uchar* GetText(DocId) const;
  67 //    uchar* GetText(DocId, TextPosition, TextPosition) const;
  68
  69     bool IsPrefix(uchar const *) const;
  70     bool IsSuffix(uchar const *) const;
  71     bool IsEqual(uchar const *) const;
  72     bool IsContains(uchar const *) const;
  73     bool IsLessThan(uchar const *) const;
  74
  75     unsigned CountPrefix(uchar const *) const;
  76     unsigned CountSuffix(uchar const *) const;
  77     unsigned CountEqual(uchar const *) const;
  78     unsigned CountContains(uchar const *) const;
  79     unsigned CountLessThan(const unsigned char*) const;
  80
  81     // document_result is inherited from SXSI::TextCollection.
  82     document_result Prefix(uchar const *) const;
  83     document_result Suffix(uchar const *) const;
  84     document_result Equal(uchar const *) const;
  85     document_result Contains(uchar const *) const;
  86     document_result LessThan(uchar const *) const;
  87
  88     // full_result is inherited from SXSI::TextCollection.
  89     full_result FullContains(uchar const *) const;
  90
  91     // Index from/to disk
  92     void Load(FILE *, unsigned);
  93     void Save(FILE *) const;
  94
  95
  96     // Debug FIXME Remove
  97     void deleteWT()
  98     {
  99         delete alphabetrank;
 100         alphabetrank = 0;
 101         delete [] codetable;
 102         codetable = 0;
 103     }
 104     void deleteSamples()
 105     {
 106         delete sampled;
 107         sampled =0;
 108         delete suffixes;
 109         suffixes = 0;
 110         delete positions;
 111         positions = 0;
 112         delete suffixDocId;
 113         suffixDocId = 0;
 114     }
 115     void deleteEndmarker()
 116     {
 117         delete endmarkerDocId;
 118         endmarkerDocId = 0;
 119     }
 120
 121 private:
 122     class TCodeEntry {
 123     public:
 124         unsigned count;
 125         unsigned bits;
 126         unsigned code;
 127         TCodeEntry() {count=0;bits=0;code=0u;};
 128     };
 129
 130
 131     class THuffAlphabetRank {
 132     // using fixed 0...255 alphabet
 133     private:
 134         BitRank *bitrank;
 135         THuffAlphabetRank *left;
 136         THuffAlphabetRank *right;
 137         TCodeEntry *codetable;
 138         uchar ch;
 139         bool leaf;
 140     public:
 141         THuffAlphabetRank(uchar *, TextPosition, TCodeEntry *, unsigned);
 142         THuffAlphabetRank(FILE *);
 143         ~THuffAlphabetRank();
 144
 145         void Save(FILE *);
 146         bool Test(uchar *, TextPosition);
 147
 148         inline TextPosition rank(int c, TextPosition i) const { // returns the number of characters c before and including position i
 149             THuffAlphabetRank const * temp=this;
 150             if (codetable[c].count == 0) return 0;
 151             unsigned level = 0;
 152             unsigned code = codetable[c].code;
 153             while (!temp->leaf) {
 154                 if ((code & (1u<<level)) == 0) {
 155                 i = i-temp->bitrank->rank(i);
 156                     temp = temp->left;
 157                 }
 158                 else {
 159                     i = temp->bitrank->rank(i)-1;
 160                     temp = temp->right;
 161                 }
 162                ++level;
 163             }
 164             return i+1;
 165         };
 166         inline bool IsCharAtPos(int c, TextPosition i) const {
 167             THuffAlphabetRank const * temp=this;
 168             if (codetable[c].count == 0) return false;
 169             unsigned level = 0;
 170             unsigned code = codetable[c].code;
 171             while (!temp->leaf) {
 172                 if ((code & (1u<<level))==0) {
 173                     if (temp->bitrank->IsBitSet(i)) return false;
 174                     i = i-temp->bitrank->rank(i);
 175                     temp = temp->left;
 176                 }
 177                 else {
 178                     if (!temp->bitrank->IsBitSet(i)) return false;
 179                     i = temp->bitrank->rank(i)-1;
 180                     temp = temp->right;
 181                 }
 182                ++level;
 183             }
 184             return true;
 185         }
 186         inline uchar access(TextPosition i) const {
 187             THuffAlphabetRank const * temp=this;
 188             while (!temp->leaf) {
 189                 if (temp->bitrank->IsBitSet(i)) {
 190                 i = temp->bitrank->rank(i)-1;
 191                 temp = temp->right;
 192             }
 193             else {
 194                 i = i-temp->bitrank->rank(i);
 195                     temp = temp->left;
 196             }
 197             }
 198             return temp->ch;
 199         }
 200
 201         inline uchar charAtPos(ulong i, TextPosition *rank) const {
 202             THuffAlphabetRank const * temp=this;
 203             while (!temp->leaf) {
 204                 if (temp->bitrank->IsBitSet(i)) {
 205                     i = temp->bitrank->rank(i)-1;
 206                     temp = temp->right;
 207                 } else {
 208                     i = i-temp->bitrank->rank(i);
 209                     temp = temp->left;
 210                 }
 211             }
 212             (*rank)=i;
 213             return temp->ch;
 214         }
 215     };
 216
 217     class node {
 218     private:
 219         unsigned weight;
 220         uchar value;
 221         node *child0;
 222         node *child1;
 223
 224         void maketable( unsigned code, unsigned bits, TCodeEntry *codetable ) const;
 225         static void count_chars(uchar *, TextPosition , TCodeEntry *);
 226         static unsigned SetBit(unsigned , unsigned , unsigned );
 227     public:
 228         node( unsigned char c = 0, unsigned i = 0 ) {
 229             value = c;
 230             weight = i;
 231             child0 = 0;
 232             child1 = 0;
 233         }
 234
 235         node( node* c0, node *c1 ) {
 236             value = 0;
 237             weight = c0->weight + c1->weight;
 238             child0 = c0;
 239             child1 = c1;
 240         }
 241
 242
 243         bool operator>( const node &a ) const {
 244             return weight > a.weight;
 245         }
 246
 247         static TCodeEntry *makecodetable(uchar *, TextPosition);
 248     };
 249
 250     static const unsigned char print = 1;
 251     static const unsigned char report = 1;
 252     static const uchar versionFlag;
 253     TextPosition n;
 254     unsigned samplerate;
 255     unsigned C[256];
 256     TextPosition bwtEndPos;
 257 //    THuffAlphabetRank *alphabetrank;
 258     //    RLWaveletTree *alphabetrank;
 259     static_sequence * alphabetrank;
 260     BSGAP *sampled;
 261     BlockArray *suffixes;
 262     BlockArray *suffixDocId;
 263     BlockArray *positions;
 264     TCodeEntry *codetable;
 265     DynFMI *dynFMI;
 266
 267     // Total number of texts in the collection
 268     unsigned numberOfTexts;
 269     // Total number of texts including empty texts
 270     unsigned numberOfAllTexts;
 271     // Length of the longest text
 272     ulong maxTextLength;
 273
 274     // Array of document id's in the order of end-markers in BWT
 275     // Access by endmarkerDocId[rank_$(L, p) - 1].
 276     BlockArray *endmarkerDocId;
 277     // Array of text lengths (in the inserted order)
 278     BlockArray *textLength;
 279     // Array of text starting positions (in the inserted order)
 280     BlockArray *textStartPos;
 281
 282     // FIXME Replace with a more succinct data structure
 283     std::set<unsigned> emptyTextId;
 284     BSGAP *emptyTextRank;
 285
 286     // Private methods
 287     uchar * BWT(uchar *);
 288     uchar * LoadFromFile(const char *);
 289     void SaveToFile(const char *, uchar *);
 290     void makewavelet(uchar *);
 291     void maketables();
 292
 293     // Following are not part of the public API
 294     DocId DocIdAtTextPos(TextPosition) const;
 295     ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *) const;
 296     TextPosition Inverse(TextPosition) const;
 297     TextPosition LF(uchar c, TextPosition &sp, TextPosition &ep) const;
 298     TextPosition Psi(TextPosition) const;
 299     uchar * Substring(TextPosition, TextPosition) const;
 300     TextPosition Lookup(TextPosition) const;
 301
 302     /**
 303      * Count end-markers in given interval
 304      */
 305     inline unsigned CountEndmarkers(TextPosition sp, TextPosition ep) const
 306     {
 307         if (sp > ep)
 308             return 0;
 309
 310         ulong ranksp = 0;
 311         if (sp != 0)
 312             ranksp = alphabetrank->rank(0, sp - 1);
 313
 314         return alphabetrank->rank(0, ep) - ranksp;
 315     }
 316 };
 317
 318 #endif