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     bool IsPrefix(uchar const *, DocId, DocId) const;
  86     bool IsSuffix(uchar const *, DocId, DocId) const;
  87     bool IsEqual(uchar const *, DocId, DocId) const;
  88     bool IsContains(uchar const *, DocId, DocId) const;
  89     bool IsLessThan(uchar const *, DocId, DocId) const;
  90
  91     ulong Count(uchar const *) const;
  92     unsigned CountPrefix(uchar const *) const;
  93     unsigned CountSuffix(uchar const *) const;
  94     unsigned CountEqual(uchar const *) const;
  95     unsigned CountContains(uchar const *) const;
  96     unsigned CountLessThan(const unsigned char*) const;
  97
  98     unsigned CountPrefix(uchar const *, DocId, DocId) const;
  99     unsigned CountSuffix(uchar const *, DocId, DocId) const;
 100     unsigned CountEqual(uchar const *, DocId, DocId) const;
 101     unsigned CountContains(uchar const *, DocId, DocId) const;
 102     unsigned CountLessThan(uchar const *, DocId, DocId) const;
 103
 104     // Definition of document_result is inherited from SXSI::TextCollection.
 105     document_result Prefix(uchar const *) const;
 106     document_result Suffix(uchar const *) const;
 107     document_result Equal(uchar const *) const;
 108     document_result Contains(uchar const *) const;
 109     document_result LessThan(uchar const *) const;
 110
 111     document_result Prefix(uchar const *, DocId, DocId) const;
 112     document_result Suffix(uchar const *, DocId, DocId) const;
 113     document_result Equal(uchar const *, DocId, DocId) const;
 114     document_result Contains(uchar const *, DocId, DocId) const;
 115     document_result LessThan(uchar const *, DocId, DocId) const;
 116
 117     // Definition of full_result is inherited from SXSI::TextCollection.
 118     full_result FullContains(uchar const *) const;
 119     full_result FullContains(uchar const *, DocId, DocId) const;
 120
 121     // Index from/to disk
 122     void Load(FILE *, unsigned);
 123     void Save(FILE *) const;
 124
 125
 126     // FIXME Remove
 127     void deleteWT()
 128     {
 129         delete alphabetrank;
 130         alphabetrank = 0;
 131         delete [] codetable;
 132         codetable = 0;
 133     }
 134     void deleteSamples()
 135     {
 136         delete sampled;
 137         sampled =0;
 138         delete suffixes;
 139         suffixes = 0;
 140         delete suffixDocId;
 141         suffixDocId = 0;
 142     }
 143     void deleteEndmarker()
 144     {
 145         delete endmarkerDocId;
 146         endmarkerDocId = 0;
 147     }
 148
 149 private:
 150     // FIXME Unused code
 151     class TCodeEntry {
 152     public:
 153         unsigned count;
 154         unsigned bits;
 155         unsigned code;
 156         TCodeEntry() {count=0;bits=0;code=0u;};
 157     };
 158
 159
 160     // FIXME Unused code
 161     class THuffAlphabetRank {
 162     // using fixed 0...255 alphabet
 163     private:
 164         BitRank *bitrank;
 165         THuffAlphabetRank *left;
 166         THuffAlphabetRank *right;
 167         TCodeEntry *codetable;
 168         uchar ch;
 169         bool leaf;
 170     public:
 171         THuffAlphabetRank(uchar *, TextPosition, TCodeEntry *, unsigned);
 172         THuffAlphabetRank(FILE *);
 173         ~THuffAlphabetRank();
 174
 175         void Save(FILE *);
 176         bool Test(uchar *, TextPosition);
 177
 178         inline TextPosition rank(int c, TextPosition i) const { // returns the number of characters c before and including position i
 179             THuffAlphabetRank const * temp=this;
 180             if (codetable[c].count == 0) return 0;
 181             unsigned level = 0;
 182             unsigned code = codetable[c].code;
 183             while (!temp->leaf) {
 184                 if ((code & (1u<<level)) == 0) {
 185                 i = i-temp->bitrank->rank(i);
 186                     temp = temp->left;
 187                 }
 188                 else {
 189                     i = temp->bitrank->rank(i)-1;
 190                     temp = temp->right;
 191                 }
 192                ++level;
 193             }
 194             return i+1;
 195         };
 196         inline bool IsCharAtPos(int c, TextPosition i) const {
 197             THuffAlphabetRank const * temp=this;
 198             if (codetable[c].count == 0) return false;
 199             unsigned level = 0;
 200             unsigned code = codetable[c].code;
 201             while (!temp->leaf) {
 202                 if ((code & (1u<<level))==0) {
 203                     if (temp->bitrank->IsBitSet(i)) return false;
 204                     i = i-temp->bitrank->rank(i);
 205                     temp = temp->left;
 206                 }
 207                 else {
 208                     if (!temp->bitrank->IsBitSet(i)) return false;
 209                     i = temp->bitrank->rank(i)-1;
 210                     temp = temp->right;
 211                 }
 212                ++level;
 213             }
 214             return true;
 215         }
 216         inline uchar access(TextPosition i) const {
 217             THuffAlphabetRank const * temp=this;
 218             while (!temp->leaf) {
 219                 if (temp->bitrank->IsBitSet(i)) {
 220                 i = temp->bitrank->rank(i)-1;
 221                 temp = temp->right;
 222             }
 223             else {
 224                 i = i-temp->bitrank->rank(i);
 225                     temp = temp->left;
 226             }
 227             }
 228             return temp->ch;
 229         }
 230
 231         inline uchar charAtPos(ulong i, TextPosition *rank) const {
 232             THuffAlphabetRank const * temp=this;
 233             while (!temp->leaf) {
 234                 if (temp->bitrank->IsBitSet(i)) {
 235                     i = temp->bitrank->rank(i)-1;
 236                     temp = temp->right;
 237                 } else {
 238                     i = i-temp->bitrank->rank(i);
 239                     temp = temp->left;
 240                 }
 241             }
 242             (*rank)=i;
 243             return temp->ch;
 244         }
 245     };
 246
 247     // FIXME Unused code
 248     class node {
 249     private:
 250         unsigned weight;
 251         uchar value;
 252         node *child0;
 253         node *child1;
 254
 255         void maketable( unsigned code, unsigned bits, TCodeEntry *codetable ) const;
 256         static void count_chars(uchar *, TextPosition , TCodeEntry *);
 257         static unsigned SetBit(unsigned , unsigned , unsigned );
 258     public:
 259         node( unsigned char c = 0, unsigned i = 0 ) {
 260             value = c;
 261             weight = i;
 262             child0 = 0;
 263             child1 = 0;
 264         }
 265
 266         node( node* c0, node *c1 ) {
 267             value = 0;
 268             weight = c0->weight + c1->weight;
 269             child0 = c0;
 270             child1 = c1;
 271         }
 272
 273
 274         bool operator>( const node &a ) const {
 275             return weight > a.weight;
 276         }
 277
 278         static TCodeEntry *makecodetable(uchar *, TextPosition);
 279     };
 280
 281     static const uchar versionFlag;
 282     TextPosition n;
 283     unsigned samplerate;
 284     unsigned C[256];
 285     TextPosition bwtEndPos;
 286 //    THuffAlphabetRank *alphabetrank;
 287     //    RLWaveletTree *alphabetrank;
 288     static_sequence * alphabetrank;
 289
 290 #ifdef CSA_TEST_BWT
 291     DynFMI *dynFMI;
 292 #endif
 293     TCodeEntry *codetable;
 294
 295     // Sample structures for texts longer than samplerate
 296     BSGAP *sampled;
 297     BlockArray *suffixes;
 298     BlockArray *suffixDocId;
 299
 300     // Total number of texts in the collection
 301     unsigned numberOfTexts;
 302     // Total number of texts including empty texts
 303     unsigned numberOfAllTexts;
 304     // Length of the longest text
 305     ulong maxTextLength;
 306
 307     // Array of document id's in the order of end-markers in BWT
 308     // Access by endmarkerDocId[rank_$(L, p) - 1].
 309     BlockArray *endmarkerDocId;
 310
 311     // FIXME Replace with a more succinct data structure
 312     // Note: Empty texts are already handled inside XMLTree class.
 313     std::set<unsigned> emptyTextId;
 314     BSGAP *emptyTextRank;
 315
 316     // FIXME A better solution?
 317     std::string texts;
 318
 319     // Following are not part of the public API
 320     uchar * BWT(uchar *);
 321     void makewavelet(uchar *);
 322     void maketables();
 323     DocId DocIdAtTextPos(BlockArray*, TextPosition) const;
 324     ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *) const;
 325     ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *, DocId, DocId) const;
 326     ulong SearchLessThan(uchar const *, TextPosition, TextPosition *, TextPosition *) const;
 327 //    TextPosition Inverse(TextPosition) const;
 328 //    TextPosition LF(uchar c, TextPosition &sp, TextPosition &ep) const;
 329 //    TextPosition Psi(TextPosition) const;
 330 //    uchar * Substring(TextPosition, TextPosition) const;
 331 //    TextPosition Lookup(TextPosition) const;
 332
 333     /**
 334      * Count end-markers in given interval
 335      */
 336     inline unsigned CountEndmarkers(TextPosition sp, TextPosition ep) const
 337     {
 338         if (sp > ep)
 339             return 0;
 340
 341         ulong ranksp = 0;
 342         if (sp != 0)
 343             ranksp = alphabetrank->rank(0, sp - 1);
 344
 345         return alphabetrank->rank(0, ep) - ranksp;
 346     }
 347     unsigned CountEndmarkers(TextPosition, TextPosition, DocId, DocId) const;
 348 }; // class CSA
 349
 350 } // namespace SXSI
 351
 352 #endif