BWT via Difference cover

[SXSI/TextCollection.git] / CSA.h

diff --git a/CSA.h b/CSA.h
index b9a1745..c0751cf 100644 (file)
--- a/CSA.h
+++ b/CSA.h
@@ -21,34 +21,34 @@
 #ifndef _CSA_H_
 #define _CSA_H_
 #include "dynFMI.h"
+#include "BitRank.h"
+#include "TextCollection.h"
+#include "BlockArray.h"
+#include "RLWaveletTree.h"
+#include <set>
+#include <vector>
 
 // Include  from XMLTree/libcds
-#include <basics.h>
+#include <basics.h> // Defines W == 32
 #include <static_bitsequence.h>
 #include <alphabet_mapper.h>
 #include <static_sequence.h>
 
-#include <set>
-#include <vector>
-#include "BitRank.h"
-#include "TextCollection.h"
-#include "BlockArray.h"
-#include "RLWaveletTree.h"
+// Re-define word size to ulong:
+#undef W
+#if __WORDSIZE == 64
+#   define W 64
+#else
+#   define W 32
+#endif
+#undef bitset
+
+// Un-comment to compare BWT against a BWT generated from class dynFMI:
+//#define CSA_TEST_BWT
 
 /**
  * Implementation of the TextCollection interface
  *
- * Implementation notes:
- *
- * Dynamic construction (via InsertText()) uses dynamic (balanced) wavelet tree
- * which requires O(n log \sigma) bits of memory. If we know the distribution
- * of characters beforehand, space can easily be made O(nH_0).
- * 
- * The method MakeStatic() constructs a Succinct Suffix Array with a huffman 
- * shaped wavelet tree. This structure achieves only zero'th order entropy. (FIXME)
- *
- * Query methods Prefix, Suffix, Equal, Contains and LessThan can be used
- * with any FM-index variant supporting LF-mapping.
  */
 class CSA : public SXSI::TextCollection {
 public:
@@ -65,6 +65,11 @@ public:
     void MakeStatic();
     bool EmptyText(DocId) const;
     uchar* GetText(DocId) const;
+    /**
+     * Next method is not supported:
+     * Supporting GetText for some substring [i,j]
+     * would require more space.
+     */
 //    uchar* GetText(DocId, TextPosition, TextPosition) const;
 
     bool IsPrefix(uchar const *) const;
@@ -73,6 +78,7 @@ public:
     bool IsContains(uchar const *) const;
     bool IsLessThan(uchar const *) const;
 
+    ulong Count(uchar const *) const;
     unsigned CountPrefix(uchar const *) const;
     unsigned CountSuffix(uchar const *) const;
     unsigned CountEqual(uchar const *) const;
@@ -94,7 +100,7 @@ public:
     void Save(FILE *) const;
 
 
-    // Debug FIXME Remove
+    // FIXME Remove
     void deleteWT()
     {
         delete alphabetrank;
@@ -108,8 +114,6 @@ public:
         sampled =0;
         delete suffixes;
         suffixes = 0;
-        delete positions;
-        positions = 0;
         delete suffixDocId;
         suffixDocId = 0;
     }
@@ -120,6 +124,7 @@ public:
     }
 
 private:
+    // FIXME Unused code
     class TCodeEntry {
     public:
         unsigned count;
@@ -129,6 +134,7 @@ private:
     };   
      
 
+    // FIXME Unused code
     class THuffAlphabetRank {
     // using fixed 0...255 alphabet
     private:
@@ -215,6 +221,7 @@ private:
         }
     };
 
+    // FIXME Unused code
     class node {
     private:
         unsigned weight;
@@ -248,8 +255,6 @@ private:
         static TCodeEntry *makecodetable(uchar *, TextPosition);
     };
     
-    static const unsigned char print = 1;
-    static const unsigned char report = 1;
     static const uchar versionFlag;
     TextPosition n;
     unsigned samplerate;
@@ -258,12 +263,16 @@ private:
 //    THuffAlphabetRank *alphabetrank;
     //    RLWaveletTree *alphabetrank;
     static_sequence * alphabetrank;
+
+#ifdef CSA_TEST_BWT
+    DynFMI *dynFMI;
+#endif
+    TCodeEntry *codetable;
+    
+    // Sample structures for texts longer than samplerate
     BSGAP *sampled; 
     BlockArray *suffixes;
     BlockArray *suffixDocId;
-    BlockArray *positions;
-    TCodeEntry *codetable;
-    DynFMI *dynFMI;
 
     // Total number of texts in the collection
     unsigned numberOfTexts;
@@ -275,30 +284,26 @@ private:
     // Array of document id's in the order of end-markers in BWT
     // Access by endmarkerDocId[rank_$(L, p) - 1].
     BlockArray *endmarkerDocId;
-    // Array of text lengths (in the inserted order)
-    BlockArray *textLength;
-    // Array of text starting positions (in the inserted order)
-    BlockArray *textStartPos;
 
     // FIXME Replace with a more succinct data structure
+    // Note: Empty texts are already handled inside XMLTree class.
     std::set<unsigned> emptyTextId;
     BSGAP *emptyTextRank;
 
-    // Private methods
+    // FIXME A better solution?
+    std::string texts;
+
+    // Following are not part of the public API
     uchar * BWT(uchar *);
-    uchar * LoadFromFile(const char *);
-    void SaveToFile(const char *, uchar *);
     void makewavelet(uchar *);
     void maketables();
-
-    // Following are not part of the public API
-    DocId DocIdAtTextPos(TextPosition) const;
+    DocId DocIdAtTextPos(BlockArray*, TextPosition) const;
     ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *) const;
-    TextPosition Inverse(TextPosition) const;
-    TextPosition LF(uchar c, TextPosition &sp, TextPosition &ep) const;
-    TextPosition Psi(TextPosition) const;
-    uchar * Substring(TextPosition, TextPosition) const;
-    TextPosition Lookup(TextPosition) const;
+//    TextPosition Inverse(TextPosition) const;
+//    TextPosition LF(uchar c, TextPosition &sp, TextPosition &ep) const;
+//    TextPosition Psi(TextPosition) const;
+//    uchar * Substring(TextPosition, TextPosition) const;
+//    TextPosition Lookup(TextPosition) const;
 
     /**
      * Count end-markers in given interval