X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;ds=sidebyside;f=TCImplementation.h;h=e8e8c4bb04a480a186a39abca273b0cad87fc055;hb=2dba1ef94915ba5c1a06c3756d6dd0333605a5f7;hp=0439978d3d0e4a4572169b6a7d929222b61149e1;hpb=bcbed10c547780b6e5b2028d936eae337ecebac5;p=SXSI%2FTextCollection.git diff --git a/TCImplementation.h b/TCImplementation.h index 0439978..e8e8c4b 100644 --- a/TCImplementation.h +++ b/TCImplementation.h @@ -20,6 +20,9 @@ #ifndef _TCImplementation_H_ #define _TCImplementation_H_ + +#include "incbwt/bits/deltavector.h" + #include "BitRank.h" #include "TextCollection.h" #include "BlockArray.h" @@ -39,9 +42,13 @@ # define W 32 #endif #undef bitset +#undef bitget -#include "TextStorage.h" +#include "TextStorage.h" +#include "ArrayDoc.h" +#include +#include namespace SXSI { @@ -53,31 +60,31 @@ namespace SXSI */ class TCImplementation : public SXSI::TextCollection { public: - TCImplementation(uchar *, ulong, unsigned, unsigned, ulong); + TCImplementation(uchar *, ulong, unsigned, unsigned, ulong, ulong, + CSA::DeltaVector &, const std::string &, char); ~TCImplementation(); bool EmptyText(DocId) const; /** - * Returns a pointer to the original text. + * Extracting one text. * - * Do *not* try to free the array. - * (However, this implementation is suspect to change.) - * - * See TextStorage.h for details. + * Call DeleteText() for each pointer returned by GetText() + * to avoid possible memory leaks. */ uchar * GetText(DocId) const; + void DeleteText(uchar *text) const + { textStorage->DeleteText(text); } /** * Returns a pointer to the beginning of texts i, i+1, ..., j. * Texts are separated by a '\0' byte. * - * Do *not* try to free the array. - * (However, this implementation is suspect to change.) - * - * See TextStorage.h for details. + * Call DeleteText() for each pointer returned by GetText() + * to avoid possible memory leaks. */ - uchar * GetText(DocId i, DocId j) const; + uchar * GetText(DocId i, DocId j) const + { return textStorage->GetText(i, j); } /** * Returns a substring of given text ID. @@ -117,6 +124,8 @@ public: document_result Equal(uchar const *) const; document_result Contains(uchar const *) const; document_result LessThan(uchar const *) const; + document_result KMismaches(uchar const *, unsigned) const; + document_result KErrors(uchar const *, unsigned) const; document_result Prefix(uchar const *, DocId, DocId) const; document_result Suffix(uchar const *, DocId, DocId) const; @@ -127,12 +136,16 @@ public: // Definition of full_result is inherited from SXSI::TextCollection. full_result FullContains(uchar const *) const; full_result FullContains(uchar const *, DocId, DocId) const; + full_result FullKMismatches(uchar const *, unsigned) const; + full_result FullKErrors(uchar const *, unsigned) const; // Index from/to disk TCImplementation(FILE *, unsigned); void Save(FILE *) const; private: + typedef std::vector > suffix_range_vector; + static const uchar versionFlag; TextPosition n; unsigned samplerate; @@ -151,7 +164,8 @@ private: ulong maxTextLength; // Array of document id's in the order of end-markers in BWT - static_sequence *Doc; +// static_sequence *Doc; + ArrayDoc *Doc; // Text storage for fast extraction TextStorage * textStorage; @@ -159,12 +173,14 @@ private: // Following methods are not part of the public API uchar * BWT(uchar *); void makewavelet(uchar *); - void maketables(); + void maketables(ulong, char, CSA::DeltaVector &, const string &); DocId DocIdAtTextPos(BlockArray*, TextPosition) const; ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *) const; ulong Search(uchar const *, TextPosition, TextPosition *, TextPosition *, DocId, DocId) const; ulong SearchLessThan(uchar const *, TextPosition, TextPosition *, TextPosition *) const; - + ulong searchPrefix(uchar const *pattern, ulong i, ulong *sp, ulong *ep) const; + ulong kmismatches(suffix_range_vector &, uchar const *, ulong, ulong, ulong, unsigned) const; + ulong kerrors(suffix_range_vector &, uchar const *, ulong, ulong, ulong, unsigned, ulong const *, ulong) const; /** * Count end-markers in given interval */ @@ -223,6 +239,146 @@ private: return Doc->access(sp, ep-1, min, max); } + + /** + * Enumerate documents in given interval [sp, ep] + */ + inline void EnumerateDocuments(std::set &resultSet, TextPosition sp, TextPosition ep) const + { + // We want unique document indentifiers, using std::set to collect them + // FIXME use unordered_set? + uint tmp_rank_c = 0; // Cache rank value of c. + for (; sp <= ep; ++sp) + { + TextPosition i = sp; + uchar c = alphabetrank->access(i, tmp_rank_c); + while (c != '\0' && !sampled->access(i)) + { + i = C[c]+tmp_rank_c-1; //alphabetrank->rank(c,i)-1; + c = alphabetrank->access(i, tmp_rank_c); + } + if (c == '\0') + { + // Rank among the end-markers in BWT + unsigned endmarkerRank = tmp_rank_c-1; //alphabetrank->rank(0, i) - 1; + resultSet.insert(Doc->access(endmarkerRank)); + } + else + { + DocId di = (*suffixDocId)[sampled->rank1(i)-1]; + assert((unsigned)di < numberOfTexts); + resultSet.insert(di); + } + } + } + + /** + * Enumerate documents in given interval [sp, ep] + * and within [begin, end] + */ + inline void EnumerateDocuments(std::set &resultSet, TextPosition sp, TextPosition ep, DocId begin, DocId end) const + { + // We want unique document indentifiers, using std::set to collect them + uint tmp_rank_c = 0; // Cache rank value of c. + for (; sp <= ep; ++sp) + { + TextPosition i = sp; + uchar c = alphabetrank->access(i, tmp_rank_c); + while (c != '\0' && !sampled->access(i)) + { + i = C[c]+tmp_rank_c-1; //alphabetrank->rank(c,i)-1; + c = alphabetrank->access(i, tmp_rank_c); + } + if (c == '\0') + { + // Rank among the end-markers in BWT + unsigned endmarkerRank = tmp_rank_c-1; //alphabetrank->rank(0, i) - 1; + DocId docId = Doc->access(endmarkerRank); + if (docId >= begin && docId <= end) + resultSet.insert(docId); + } + else + { + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; + assert((unsigned)docId < numberOfTexts); + if (docId >= begin && docId <= end) + resultSet.insert(docId); + } + } + } + + /** + * Enumerate document+position pairs (full_result) of + * each suffix in given interval. + */ + inline void EnumeratePositions(full_result &result, TextPosition sp, TextPosition ep) const + { + uint tmp_rank_c = 0; // Cache rank value of c. + for (; sp <= ep; ++sp) + { + TextPosition i = sp; + TextPosition dist = 0; + uchar c = alphabetrank->access(i, tmp_rank_c); + while (c != '\0' && !sampled->access(i)) + { + i = C[c]+tmp_rank_c-1; //alphabetrank->rank(c,i)-1; + c = alphabetrank->access(i, tmp_rank_c); + ++ dist; + } + if (c == '\0') + { + // Rank among the end-markers in BWT + unsigned endmarkerRank = tmp_rank_c-1; //alphabetrank->rank(0, i) - 1; + DocId docId = Doc->access(endmarkerRank); + result.push_back(make_pair(docId, dist)); + } + else + { + TextPosition textPos = (*suffixes)[sampled->rank1(i)-1] + dist; + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; + + result.push_back(make_pair(docId, textPos)); + } + } + } + + /** + * Enumerate document+position pairs (full_result) of + * each suffix in given interval and within [begin, end]. + */ + inline void EnumeratePositions(full_result &result, TextPosition sp, TextPosition ep, DocId begin, DocId end) const + { + uint tmp_rank_c = 0; // Cache rank value of c. + for (; sp <= ep; ++sp) + { + TextPosition i = sp; + TextPosition dist = 0; + uchar c = alphabetrank->access(i, tmp_rank_c); + while (c != '\0' && !sampled->access(i)) + { + i = C[c]+tmp_rank_c-1; //alphabetrank->rank(c,i)-1; + c = alphabetrank->access(i, tmp_rank_c); + ++ dist; + } + if (c == '\0') + { + // Rank among the end-markers in BWT + unsigned endmarkerRank = tmp_rank_c-1; //alphabetrank->rank(0, i) - 1; + DocId docId = Doc->access(endmarkerRank); + if (docId >= begin && docId <= end) + result.push_back(make_pair(docId, dist)); + } + else + { + TextPosition textPos = (*suffixes)[sampled->rank1(i)-1] + dist; + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; + + if (docId >= begin && docId <= end) + result.push_back(make_pair(docId, textPos)); + } + } + } + }; // class TCImplementation } // namespace SXSI