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