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