TCImplementation.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 _TCImplementation_H_
  22 #define _TCImplementation_H_
  23 #include "BitRank.h"
  24 #include "TextCollection.h"
  25 #include "BlockArray.h"
  26
  27 // Include  from XMLTree/libcds
  28 #include <basics.h> // Defines W == 32
  29 #include <static_bitsequence.h>
  30 #include <alphabet_mapper.h>
  31 #include <static_sequence.h>
  32 #include <static_sequence_wvtree_noptrs.h>
  33
  34 // Re-define word size to ulong:
  35 #undef W
  36 #if __WORDSIZE == 64
  37 #   define W 64
  38 #else
  39 #   define W 32
  40 #endif
  41 #undef bitset
  42
  43 #include "TextStorage.h"
  44
  45
  46 namespace SXSI
  47 {
  48
  49
  50 /**
  51  * Implementation of the TextCollection interface
  52  *
  53  */
  54 class TCImplementation : public SXSI::TextCollection {
  55 public:
  56     TCImplementation(uchar *, ulong, unsigned, unsigned, ulong);
  57     ~TCImplementation();
  58
  59     bool EmptyText(DocId) const;
  60
  61     /**
  62      * Returns a pointer to the original text.
  63      *
  64      * Do *not* try to free the array.
  65      * (However, this implementation is suspect to change.)
  66      *
  67      * See TextStorage.h for details.
  68      */
  69     uchar * GetText(DocId) const;
  70
  71     /**
  72      * Returns a pointer to the beginning of texts i, i+1, ..., j.
  73      * Texts are separated by a '\0' byte.
  74      *
  75      * Do *not* try to free the array.
  76      * (However, this implementation is suspect to change.)
  77      *
  78      * See TextStorage.h for details.
  79      */
  80     uchar * GetText(DocId i, DocId j) const;
  81
  82     /**
  83      * Returns a substring of given text ID.
  84      *
  85      * FIXME This may be reimplemented via TextStorage.
  86      */
  87 //    uchar* GetText(DocId, TextPosition, TextPosition) const;
  88
  89     bool IsPrefix(uchar const *) const;
  90     bool IsSuffix(uchar const *) const;
  91     bool IsEqual(uchar const *) const;
  92     bool IsContains(uchar const *) const;
  93     bool IsLessThan(uchar const *) const;
  94
  95     bool IsPrefix(uchar const *, DocId, DocId) const;
  96     bool IsSuffix(uchar const *, DocId, DocId) const;
  97     bool IsEqual(uchar const *, DocId, DocId) const;
  98     bool IsContains(uchar const *, DocId, DocId) const;
  99     bool IsLessThan(uchar const *, DocId, DocId) const;
 100
 101     ulong Count(uchar const *) const;
 102     unsigned CountPrefix(uchar const *) const;
 103     unsigned CountSuffix(uchar const *) const;
 104     unsigned CountEqual(uchar const *) const;
 105     unsigned CountContains(uchar const *) const;
 106     unsigned CountLessThan(const unsigned char*) const;
 107
 108     unsigned CountPrefix(uchar const *, DocId, DocId) const;
 109     unsigned CountSuffix(uchar const *, DocId, DocId) const;
 110     unsigned CountEqual(uchar const *, DocId, DocId) const;
 111     unsigned CountContains(uchar const *, DocId, DocId) const;
 112     unsigned CountLessThan(uchar const *, DocId, DocId) const;
 113
 114     // Definition of document_result is inherited from SXSI::TextCollection.
 115     document_result Prefix(uchar const *) const;
 116     document_result Suffix(uchar const *) const;
 117     document_result Equal(uchar const *) const;
 118     document_result Contains(uchar const *) const;
 119     document_result LessThan(uchar const *) const;
 120
 121     document_result Prefix(uchar const *, DocId, DocId) const;
 122     document_result Suffix(uchar const *, DocId, DocId) const;
 123     document_result Equal(uchar const *, DocId, DocId) const;
 124     document_result Contains(uchar const *, DocId, DocId) const;
 125     document_result LessThan(uchar const *, DocId, DocId) const;
 126
 127     // Definition of full_result is inherited from SXSI::TextCollection.
 128     full_result FullContains(uchar const *) const;
 129     full_result FullContains(uchar const *, DocId, DocId) const;
 130
 131     // Index from/to disk
 132     TCImplementation(FILE *, unsigned);
 133     void Save(FILE *) const;
 134
 135 private:
 136     static const uchar versionFlag;
 137     TextPosition n;
 138     unsigned samplerate;
 139     unsigned C[256];
 140     TextPosition bwtEndPos;
 141     static_sequence * alphabetrank;
 142
 143     // Sample structures for texts longer than samplerate
 144     static_bitsequence * sampled;
 145     BlockArray *suffixes;
 146     BlockArray *suffixDocId;
 147
 148     // Total number of texts in the collection
 149     unsigned numberOfTexts;
 150     // Length of the longest text
 151     ulong maxTextLength;
 152
 153     // Array of document id's in the order of end-markers in BWT
 154     static_sequence *Doc;
 155
 156     // Text storage for fast extraction
 157     TextStorage * textStorage;
 158
 159     // Following methods are not part of the public API
 160     uchar * BWT(uchar *);
 161     void makewavelet(uchar *);
 162     void maketables();
 163     DocId DocIdAtTextPos(BlockArray*, TextPosition) const;
 164     ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *) const;
 165     ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *, DocId, DocId) const;
 166     ulong SearchLessThan(uchar const *, TextPosition, TextPosition *, TextPosition *) const;
 167
 168     /**
 169      * Count end-markers in given interval
 170      */
 171     inline unsigned CountEndmarkers(TextPosition sp, TextPosition ep) const
 172     {
 173         if (sp > ep)
 174             return 0;
 175
 176         ulong ranksp = 0;
 177         if (sp != 0)
 178             ranksp = alphabetrank->rank(0, sp - 1);
 179
 180         return alphabetrank->rank(0, ep) - ranksp;
 181     }
 182
 183     /**
 184      * Count end-markers in given interval and
 185      * within docIds [min,max]
 186      */
 187     inline unsigned CountEndmarkers(TextPosition sp, TextPosition ep, DocId min, DocId max) const
 188     {
 189         if (sp != 0)
 190             sp = alphabetrank->rank(0, sp - 1);
 191         ep = alphabetrank->rank(0, ep);
 192         if (ep == 0)
 193             return 0;
 194
 195         return Doc->count(sp, ep-1, min, max);
 196     }
 197
 198     /**
 199      * Enumerate all end-markers in given interval
 200      */
 201     inline document_result EnumerateEndmarkers(TextPosition sp, TextPosition ep) const
 202     {
 203         if (sp != 0)
 204             sp = alphabetrank->rank(0, sp - 1);
 205         ep = alphabetrank->rank(0, ep);
 206         if (ep == 0)
 207             return document_result();
 208
 209         return Doc->accessAll(sp, ep-1);
 210     }
 211
 212     /**
 213      * Enumerate end-markers in given interval and
 214      * within docIds [min,max]
 215      */
 216     inline document_result EnumerateEndmarkers(TextPosition sp, TextPosition ep, DocId min, DocId max) const
 217     {
 218         if (sp != 0)
 219             sp = alphabetrank->rank(0, sp - 1);
 220         ep = alphabetrank->rank(0, ep);
 221         if (ep == 0)
 222             return document_result();
 223
 224         return Doc->access(sp, ep-1, min, max);
 225     }
 226 }; // class TCImplementation
 227
 228 } // namespace SXSI
 229
 230 #endif