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