X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=CSA.h;h=c0751cf406b4254b625c1c7f062fbd7509151781;hb=6149332e97e23dbcfb42434f88be4a59143e73ab;hp=4303b53f582f571da0122fd5373910d5312fa06f;hpb=9c741e645d2c51f59b7cc40bf9ca0a91e1ed51d4;p=SXSI%2FTextCollection.git

diff --git a/CSA.h b/CSA.h
index 4303b53..c0751cf 100644
--- a/CSA.h
+++ b/CSA.h
@@ -29,25 +29,26 @@
 #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>
 
+// 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:
@@ -64,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;
@@ -72,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;
@@ -93,7 +100,7 @@ public:
     void Save(FILE *) const;
 
 
-    // Debug FIXME Remove
+    // FIXME Remove
     void deleteWT()
     {
         delete alphabetrank;
@@ -107,8 +114,6 @@ public:
         sampled =0;
         delete suffixes;
         suffixes = 0;
-        delete positions;
-        positions = 0;
         delete suffixDocId;
         suffixDocId = 0;
     }
@@ -119,6 +124,7 @@ public:
     }
 
 private:
+    // FIXME Unused code
     class TCodeEntry {
     public:
         unsigned count;
@@ -128,6 +134,7 @@ private:
     };   
      
 
+    // FIXME Unused code
     class THuffAlphabetRank {
     // using fixed 0...255 alphabet
     private:
@@ -214,6 +221,7 @@ private:
         }
     };
 
+    // FIXME Unused code
     class node {
     private:
         unsigned weight;
@@ -247,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;
@@ -257,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;
@@ -274,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