X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=TCImplementation.cpp;h=5959e6af991c9a7d3e5d803e77c20e9ee8f7bd85;hb=131f6c58241d797b0c8aaf1e691eb10cd19467aa;hp=290ca9c15864bfadf1ad304ebf83733308d79983;hpb=40ddf9aca842bdc081b6350a4ebfe36b066c94c9;p=SXSI%2FTextCollection.git diff --git a/TCImplementation.cpp b/TCImplementation.cpp index 290ca9c..5959e6a 100644 --- a/TCImplementation.cpp +++ b/TCImplementation.cpp @@ -19,7 +19,10 @@ *****************************************************************************/ #include "TCImplementation.h" -//#include "HeapProfiler.h" // FIXME remove +//#define DEBUG_MEMUSAGE +#ifdef DEBUG_MEMUSAGE +#include "HeapProfiler.h" // FIXME remove +#endif #include #include @@ -38,7 +41,7 @@ namespace SXSI { // Save file version info -const uchar TCImplementation::versionFlag = 3; +const uchar TCImplementation::versionFlag = 6; /** * Constructor inits an empty dynamic FM-index. @@ -46,20 +49,8 @@ const uchar TCImplementation::versionFlag = 3; */ TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerate_, unsigned numberOfTexts_, ulong maxTextLength_) : n(length), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0), - suffixDocId(0), numberOfTexts(numberOfTexts_), numberOfAllTexts(numberOfTexts_), maxTextLength(maxTextLength_), endmarkerDocId(0), - emptyTextRank(0) + suffixDocId(0), numberOfTexts(numberOfTexts_), maxTextLength(maxTextLength_), Doc(0) { - - // Bitvector of empty texts, FIXME Remove? - { - //std::cout << std::endl << "texts: " << numberOfTexts << ", all texts " << numberOfAllTexts << ", size : " << emptyTextId.size() <::const_iterator it = emptyTextId.begin(); it != emptyTextId.end(); ++it) -// Tools::SetField(tempB, 1, (*it), 1); - emptyTextRank = new BSGAP(tempB, numberOfTexts, true); - } makewavelet(bwt); // Deletes bwt! bwt = 0; @@ -70,26 +61,15 @@ TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerat bool TCImplementation::EmptyText(DocId k) const { assert(k < (DocId)numberOfTexts); - if (emptyTextRank->IsBitSet(k)) - return true; - return false; + return false; // Empty texts are not indexed } -uchar* TCImplementation::GetText(DocId k) const +uchar * TCImplementation::GetText(DocId k) const { assert(k < (DocId)numberOfTexts); - ulong textRank = 0; - if (emptyTextRank->IsBitSet(k, &textRank)) - { - uchar* result = new uchar[1]; - result[0] = 0; - return result; - } - // Map to non-empty text - k -= textRank; //emptyTextRank->rank(k); - - TextPosition i = k; + return textStorage->GetText(k); +/* TextPosition i = k; string result; // Reserve average string length to avoid reallocs @@ -110,7 +90,7 @@ uchar* TCImplementation::GetText(DocId k) const res[i] = '\0'; for (ulong j = 0; j < i; ++j) res[i-j-1] = result[j]; - return res; + return res;*/ } /* * Not supported @@ -121,15 +101,6 @@ uchar* TCImplementation::GetText(DocId k, TextPosition i, TextPosition j) const assert(i <= j); ulong textRank = 0; - if (emptyTextRank->IsBitSet(k, &textRank)) - { - uchar* result = new uchar[1]; - result[0] = 0; - return result; - } - - // Map to non-empty text - k -= textRank; // emptyTextRank->rank(k); // Start position of k'th text ulong start = (*textStartPos)[k]; @@ -191,11 +162,7 @@ bool TCImplementation::IsEqual(uchar const *pattern) const { TextPosition m = std::strlen((char *)pattern); if (m == 0) - { - if (numberOfAllTexts - numberOfTexts > 0u) - return true; // Empty texts exists return false; // No empty texts exists - } TextPosition sp = 0, ep = 0; // Match including end-marker @@ -211,11 +178,7 @@ bool TCImplementation::IsEqual(uchar const *pattern, DocId begin, DocId end) con { TextPosition m = std::strlen((char *)pattern); if (m == 0) - { - if (numberOfAllTexts - numberOfTexts > 0u) - return true; // Empty texts exists return false; // No empty texts exists - } TextPosition sp = 0, ep = 0; // Match including end-marker @@ -282,7 +245,7 @@ unsigned TCImplementation::CountPrefix(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) - return numberOfAllTexts; + return numberOfTexts; TextPosition sp = 0, ep = 0; Search(pattern, m, &sp, &ep); @@ -295,7 +258,7 @@ unsigned TCImplementation::CountPrefix(uchar const * pattern, DocId begin, DocId { TextPosition m = strlen((char *)pattern); if (m == 0) - return numberOfAllTexts; + return numberOfTexts; TextPosition sp = 0, ep = 0; Search(pattern, m, &sp, &ep); @@ -308,7 +271,7 @@ unsigned TCImplementation::CountSuffix(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) - return numberOfAllTexts; + return numberOfTexts; TextPosition sp = 0, ep = 0; // Search with end-marker @@ -321,7 +284,7 @@ unsigned TCImplementation::CountSuffix(uchar const * pattern, DocId begin, DocId { TextPosition m = strlen((char *)pattern); if (m == 0) - return numberOfAllTexts; + return numberOfTexts; TextPosition sp = 0, ep = 0; // Search with end-marker @@ -334,7 +297,7 @@ unsigned TCImplementation::CountEqual(uchar const *pattern) const { TextPosition m = strlen((char const *)pattern); if (m == 0) - return numberOfAllTexts - numberOfTexts; // Empty texts. + return 0; // No empty texts. TextPosition sp = 0, ep = 0; // Match including end-marker @@ -348,7 +311,7 @@ unsigned TCImplementation::CountEqual(uchar const *pattern, DocId begin, DocId e { TextPosition m = strlen((char const *)pattern); if (m == 0) - return numberOfAllTexts - numberOfTexts; // Empty texts. + return 0; // No empty texts. TextPosition sp = 0, ep = 0; // Match including end-marker @@ -362,7 +325,7 @@ unsigned TCImplementation::CountContains(uchar const * pattern) const { TextPosition m = strlen((char const *)pattern); if (m == 0) - return numberOfAllTexts; // Total number of texts. + return numberOfTexts; // Total number of texts. // Here counting is as slow as fetching the result set // because we have to filter out occ's that fall within same document. @@ -374,7 +337,7 @@ unsigned TCImplementation::CountContains(uchar const * pattern, DocId begin, Doc { TextPosition m = strlen((char const *)pattern); if (m == 0) - return numberOfAllTexts; // Total number of texts. + return numberOfTexts; // Total number of texts. // Here counting is as slow as fetching the result set // because we have to filter out occ's that fall within same document. @@ -387,7 +350,7 @@ unsigned TCImplementation::CountLessThan(uchar const * pattern) const { TextPosition m = strlen((char const *)pattern); if (m == 0) - return numberOfAllTexts - numberOfTexts; // Empty texts. + return 0; // No empty texts. TextPosition sp = 0, ep = 0; SearchLessThan(pattern, m, &sp, &ep); @@ -400,7 +363,7 @@ unsigned TCImplementation::CountLessThan(uchar const * pattern, DocId begin, Doc { TextPosition m = strlen((char const *)pattern); if (m == 0) - return numberOfAllTexts - numberOfTexts; // Empty texts. + return 0; // No empty texts. TextPosition sp = 0, ep = 0; SearchLessThan(pattern, m, &sp, &ep); @@ -420,33 +383,9 @@ TextCollection::document_result TCImplementation::Prefix(uchar const * pattern) TextPosition sp = 0, ep = 0; Search(pattern, m, &sp, &ep); - - TextCollection::document_result result; - // Report end-markers in result interval - unsigned resultSize = CountEndmarkers(sp, ep); - if (resultSize == 0) - return result; - - result.reserve(resultSize); // Try to avoid reallocation. - // Iterate through end-markers in [sp,ep]: - unsigned i = 0; - if (sp > 0) - i = alphabetrank->rank(0, sp - 1); - while (resultSize) - { - // End-marker we found belongs to the "preceeding" doc in the collection - DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - result.push_back(docId); - - -- resultSize; - ++ i; - } - - return result; + return EnumerateEndmarkers(sp, ep); } TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, DocId begin, DocId end) const @@ -458,33 +397,8 @@ TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, TextPosition sp = 0, ep = 0; Search(pattern, m, &sp, &ep); - TextCollection::document_result result; - - // Report end-markers in result interval - unsigned resultSize = CountEndmarkers(sp, ep); - if (resultSize == 0) - return result; - - result.reserve(resultSize); // Try to avoid reallocation. - - // Iterate through end-markers in [sp,ep] and [begin, end]: - unsigned i = 0; - if (sp > 0) - i = alphabetrank->rank(0, sp - 1); - while (resultSize) - { - // End-marker we found belongs to the "preceeding" doc in the collection - DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - if (docId >= begin && docId <= end) - result.push_back(docId); - - -- resultSize; - ++ i; - } - - return result; + // Return end-markers in [sp,ep] and [begin, end]: + return EnumerateEndmarkers(sp, ep, begin, end); } TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) const @@ -500,14 +414,13 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) TextCollection::document_result result; result.reserve(ep-sp+1); // Try to avoid reallocation. - ulong sampled_rank_i = 0; // Check each occurrence for (; sp <= ep; ++sp) { TextPosition i = sp; uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i)) + while (c != '\0' && !sampled->access(i)) { i = C[c]+alphabetrank->rank(c,i)-1; c = alphabetrank->access(i); @@ -518,18 +431,11 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) { // Rank among the end-markers in BWT unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; - - // End-marker that we found belongs to the "preceeding" doc in collection: - DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - result.push_back(docId); + result.push_back(Doc->access(endmarkerRank)); } else // Sampled position { - DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; result.push_back(docId); } } @@ -550,14 +456,13 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, TextCollection::document_result result; result.reserve(ep-sp+1); // Try to avoid reallocation. - ulong sampled_rank_i = 0; // Check each occurrence, already within [begin, end] for (; sp <= ep; ++sp) { TextPosition i = sp; uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i)) + while (c != '\0' && !sampled->access(i)) { i = C[c]+alphabetrank->rank(c,i)-1; c = alphabetrank->access(i); @@ -568,18 +473,11 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, { // Rank among the end-markers in BWT unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; - - // End-marker that we found belongs to the "preceeding" doc in collection: - DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - result.push_back(docId); + result.push_back(Doc->access(endmarkerRank)); } else // Sampled position { - DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; result.push_back(docId); } } @@ -598,31 +496,8 @@ TextCollection::document_result TCImplementation::Equal(uchar const *pattern) co // Match including end-marker Search(pattern, m+1, &sp, &ep); - TextCollection::document_result result; - // Report end-markers in result interval - unsigned resultSize = CountEndmarkers(sp, ep); - if (resultSize == 0) - return result; - - result.reserve(resultSize); // Try to avoid reallocation. - - unsigned i = 0; - if (sp > 0) - i = alphabetrank->rank(0, sp - 1); - while (resultSize) - { - // End-marker we found belongs to the "previous" doc in the collection - DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - result.push_back(docId); - - -- resultSize; - ++ i; - } - - return result; + return EnumerateEndmarkers(sp, ep); } TextCollection::document_result TCImplementation::Equal(uchar const *pattern, DocId begin, DocId end) const @@ -635,31 +510,8 @@ TextCollection::document_result TCImplementation::Equal(uchar const *pattern, Do // Match including end-marker Search(pattern, m+1, &sp, &ep, begin, end); - TextCollection::document_result result; - // Report end-markers in result interval - unsigned resultSize = CountEndmarkers(sp, ep); - if (resultSize == 0) - return result; - - result.reserve(resultSize); // Try to avoid reallocation. - - unsigned i = 0; - if (sp > 0) - i = alphabetrank->rank(0, sp - 1); - while (resultSize) - { - // End-marker we found belongs to the "previous" doc in the collection - DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - result.push_back(docId); // already within [begin, end] - - -- resultSize; - ++ i; - } - - return result; + return EnumerateEndmarkers(sp, ep, begin, end); } @@ -676,13 +528,12 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern // We want unique document indentifiers, using std::set to collect them std::set resultSet; - ulong sampled_rank_i = 0; // Check each occurrence for (; sp <= ep; ++sp) { TextPosition i = sp; uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i)) + while (c != '\0' && !sampled->access(i)) { i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping c = alphabetrank->access(i); @@ -691,14 +542,11 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern { // Rank among the end-markers in BWT unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; - - // End-marker that we found belongs to the "preceeding" doc in collection: - DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts; - resultSet.insert(docId); + resultSet.insert(Doc->access(endmarkerRank)); } else { - DocId di = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; + DocId di = (*suffixDocId)[sampled->rank1(i)-1]; assert((unsigned)di < numberOfTexts); resultSet.insert(di); } @@ -706,9 +554,6 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern // Convert std::set to std::vector TextCollection::document_result result(resultSet.begin(), resultSet.end()); - // Map to doc ID's - for (document_result::iterator it = result.begin(); it != result.end(); ++it) - *it = emptyTextRank->select0(*it+1); return result; } @@ -725,13 +570,12 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern // We want unique document indentifiers, using std::set to collect them std::set resultSet; - ulong sampled_rank_i = 0; // Check each occurrence for (; sp <= ep; ++sp) { TextPosition i = sp; uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i)) + while (c != '\0' && !sampled->access(i)) { i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping c = alphabetrank->access(i); @@ -740,15 +584,13 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern { // Rank among the end-markers in BWT unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; - - // End-marker that we found belongs to the "preceeding" doc in collection: - DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts; + DocId docId = Doc->access(endmarkerRank); if (docId >= begin && docId <= end) resultSet.insert(docId); } else { - DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; assert((unsigned)docId < numberOfTexts); if (docId >= begin && docId <= end) resultSet.insert(docId); @@ -757,9 +599,6 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern // Convert std::set to std::vector TextCollection::document_result result(resultSet.begin(), resultSet.end()); - // Map to doc ID's - for (document_result::iterator it = result.begin(); it != result.end(); ++it) - *it = emptyTextRank->select0(*it+1); return result; } @@ -772,32 +611,8 @@ TextCollection::document_result TCImplementation::LessThan(uchar const * pattern TextPosition sp = 0, ep = 0; SearchLessThan(pattern, m, &sp, &ep); - TextCollection::document_result result; - // Report end-markers in result interval - unsigned resultSize = CountEndmarkers(sp, ep); - if (resultSize == 0) - return result; - - result.reserve(resultSize); // Try to avoid reallocation. - - // Iterate through end-markers in [sp,ep]: - unsigned i = 0; - if (sp > 0) - i = alphabetrank->rank(0, sp - 1); - while (resultSize) - { - // End-marker we found belongs to the "preceeding" doc in the collection - DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - result.push_back(docId); - - -- resultSize; - ++ i; - } - - return result; + return EnumerateEndmarkers(sp, ep); } TextCollection::document_result TCImplementation::LessThan(uchar const * pattern, DocId begin, DocId end) const @@ -809,33 +624,8 @@ TextCollection::document_result TCImplementation::LessThan(uchar const * pattern TextPosition sp = 0, ep = 0; SearchLessThan(pattern, m, &sp, &ep); - TextCollection::document_result result; - - // Report end-markers in result interval - unsigned resultSize = CountEndmarkers(sp, ep); - if (resultSize == 0) - return result; - - result.reserve(resultSize); // Try to avoid reallocation. - // Iterate through end-markers in [sp,ep] and [begin, end]: - unsigned i = 0; - if (sp > 0) - i = alphabetrank->rank(0, sp - 1); - while (resultSize) - { - // End-marker we found belongs to the "preceeding" doc in the collection - DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - if (docId >= begin && docId <= end) - result.push_back(docId); - - -- resultSize; - ++ i; - } - - return result; + return EnumerateEndmarkers(sp, ep, begin, end); } /** @@ -854,14 +644,13 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern full_result result; result.reserve(ep-sp+1); // Try to avoid reallocation. - ulong sampled_rank_i = 0; // Report each occurrence for (; sp <= ep; ++sp) { TextPosition i = sp; TextPosition dist = 0; uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i)) + while (c != '\0' && !sampled->access(i)) { i = C[c]+alphabetrank->rank(c,i)-1; c = alphabetrank->access(i); @@ -871,21 +660,14 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern { // Rank among the end-markers in BWT unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; - - // End-marker that we found belongs to the "preceeding" doc in collection: - DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); + DocId docId = Doc->access(endmarkerRank); result.push_back(make_pair(docId, dist)); } else { - TextPosition textPos = (*suffixes)[sampled_rank_i-1]+dist; //sampled->rank(i)-1] + dist; - DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; -// textPos = textPos - (*textStartPos)[docId]; // Offset inside the text + TextPosition textPos = (*suffixes)[sampled->rank1(i)-1] + dist; + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); result.push_back(make_pair(docId, textPos)); } } @@ -906,14 +688,13 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern full_result result; result.reserve(ep-sp+1); // Try to avoid reallocation. - ulong sampled_rank_i = 0; // Report each occurrence for (; sp <= ep; ++sp) { TextPosition i = sp; TextPosition dist = 0; uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i)) + while (c != '\0' && !sampled->access(i)) { i = C[c]+alphabetrank->rank(c,i)-1; c = alphabetrank->access(i); @@ -925,20 +706,15 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; // End-marker that we found belongs to the "preceeding" doc in collection: - DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); + DocId docId = Doc->access(endmarkerRank); if (docId >= begin && docId <= end) result.push_back(make_pair(docId, dist)); } else { - TextPosition textPos = (*suffixes)[sampled_rank_i-1]+dist; //sampled->rank(i)-1] + dist; - DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; -// textPos = textPos - (*textStartPos)[docId]; // Offset inside the text + TextPosition textPos = (*suffixes)[sampled->rank1(i)-1] + dist; + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); if (docId >= begin && docId <= end) result.push_back(make_pair(docId, textPos)); } @@ -964,10 +740,8 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern BlockArray *suffixes; BlockArray *suffixDocId; unsigned numberOfTexts; - unsigned numberOfAllTexts; ulong maxTextLength; - BlockArray *endmarkerDocId; - BSGAP *emptyTextRank; + static_sequence *docId; */ void TCImplementation::Save(FILE *file) const { @@ -988,19 +762,17 @@ void TCImplementation::Save(FILE *file) const throw std::runtime_error("TCImplementation::Save(): file write error (bwt end position)."); alphabetrank->save(file); - sampled->Save(file); + sampled->save(file); suffixes->Save(file); suffixDocId->Save(file); if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1) throw std::runtime_error("TCImplementation::Save(): file write error (numberOfTexts)."); - if (std::fwrite(&(this->numberOfAllTexts), sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (numberOfAllTexts)."); if (std::fwrite(&(this->maxTextLength), sizeof(ulong), 1, file) != 1) throw std::runtime_error("TCImplementation::Save(): file write error (maxTextLength)."); - endmarkerDocId->Save(file); - emptyTextRank->Save(file); + Doc->save(file); + textStorage->Save(file); fflush(file); } @@ -1013,8 +785,7 @@ void TCImplementation::Save(FILE *file) const */ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0), - suffixDocId(0), numberOfTexts(0), numberOfAllTexts(0), maxTextLength(0), endmarkerDocId(0), - emptyTextRank(0) + suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0) { uchar verFlag = 0; if (std::fread(&verFlag, 1, 1, file) != 1) @@ -1038,19 +809,17 @@ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) throw std::runtime_error("TCImplementation::Load(): file read error (bwt end position)."); alphabetrank = static_sequence::load(file); - sampled = new BSGAP(file); + sampled = static_bitsequence::load(file); suffixes = new BlockArray(file); suffixDocId = new BlockArray(file); if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1) throw std::runtime_error("TCImplementation::Load(): file read error (numberOfTexts)."); - if (std::fread(&(this->numberOfAllTexts), sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (numberOfAllTexts)."); if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1) throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength)."); - endmarkerDocId = new BlockArray(file); - emptyTextRank = new BSGAP(file); + Doc = static_sequence::load(file); + textStorage = new TextStorage(file); // FIXME Construct data structures with new samplerate //maketables(); @@ -1063,38 +832,7 @@ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) */ -// FIXME Use 2D-search structure -unsigned TCImplementation::CountEndmarkers(TextPosition sp, TextPosition ep, DocId begin, DocId end) const -{ - if (sp > ep) - return 0; - - ulong ranksp = 0; - if (sp != 0) - ranksp = alphabetrank->rank(0, sp - 1); - - unsigned resultSize = alphabetrank->rank(0, ep) - ranksp; - if (resultSize == 0) - return 0; - // Count end-markers in result interval and within [begin, end] - unsigned count = 0; - unsigned i = ranksp; - while (resultSize) - { - // End-marker we found belongs to the "previous" doc in the collection - DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // Map to doc ID: - docId = emptyTextRank->select0(docId+1); - if (docId >= begin && docId <= end) - ++ count; - - -- resultSize; - ++ i; - } - return count; -} - ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const { // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i) @@ -1152,7 +890,7 @@ ulong TCImplementation::SearchLessThan(uchar const * pattern, TextPosition m, Te { // printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep); c = (int)pattern[--i]; - uint result = alphabetrank->rank(c,ep); + uint result = alphabetrank->rankLessThan(c,ep); if (result == ~0u) ep = 0; else @@ -1168,16 +906,12 @@ ulong TCImplementation::SearchLessThan(uchar const * pattern, TextPosition m, Te TCImplementation::~TCImplementation() { -#ifdef CSA_TEST_BWT - delete dynFMI; -#endif delete alphabetrank; delete sampled; delete suffixes; delete suffixDocId; - - delete endmarkerDocId; - delete emptyTextRank; + delete Doc; + delete textStorage; } void TCImplementation::makewavelet(uchar *bwt) @@ -1205,20 +939,23 @@ void TCImplementation::makewavelet(uchar *bwt) // delete [] bwt; //alphabetrank = new RLWaveletTree(bwt, n); // Deletes bwt! // std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; -// std::cerr << "max heap usage before WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; -// HeapProfiler::ResetMaxHeapConsumption(); // FIXME remove +#ifdef DEBUG_MEMUSAGE + std::cerr << "max heap usage before WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; + HeapProfiler::ResetMaxHeapConsumption(); // FIXME remove +#endif alphabet_mapper * am = new alphabet_mapper_none(); static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(8); // FIXME samplerate? -// static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(16); // FIXME samplerate? wt_coder * wtc = new wt_coder_binary(bwt,n,am); alphabetrank = new static_sequence_wvtree(bwt,n,wtc,bmb,am); delete bmb; bwt = 0; // already deleted -// std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; -// std::cerr << "max heap usage after WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; +#ifdef DEBUG_MEMUSAGE + std::cerr << "heap usage after WT: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; + std::cerr << "max heap usage after WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; +#endif } void TCImplementation::maketables() @@ -1237,25 +974,16 @@ void TCImplementation::maketables() this->bwtEndPos = i; } - // Build up arrays for text length and starting positions - // FIXME Temp, remove - //BlockArray* textLength = new BlockArray(numberOfTexts, Tools::CeilLog2(maxTextLength)); + // Build up array for text starting positions BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n)); - //(*textLength)[0] = l; (*textStartPos)[0] = 0; - // Construct samples - ulong sampleLength = (n%samplerate==0) ? n/samplerate : n/samplerate+1; - unsigned ceilLog2n = Tools::CeilLog2(n); - BlockArray* positions = new BlockArray(sampleLength, ceilLog2n); - BlockArray* tmpSuffix = new BlockArray(sampleLength, ceilLog2n); - // Mapping from end-markers to doc ID's: - endmarkerDocId = new BlockArray(numberOfTexts, Tools::CeilLog2(numberOfTexts)); + uint *endmarkerDocId = new uint[numberOfTexts]; // FIXME Use BlockArray with static_sequence_wvtree_noptrs. - ulong *sampledpositions = new ulong[n/W+1]; - for (ulong i=0;iGetPos(i) + /** + * First pass: populate tables textStartPos and sampledpositions. + */ + for (ulong i=n-1;iGetPos(i) x=(i==n-1)?0:i+1; if (x % samplerate == 0 && posOfSuccEndmarker - x > samplerate) { - Tools::SetField(sampledpositions,1,p,1); - (*positions)[sampleCount] = p; - (*tmpSuffix)[sampleCount] = x; // FIXME remove + set_field(sampledpositions,1,p,1); sampleCount ++; } @@ -1285,12 +1013,11 @@ void TCImplementation::maketables() // Record the order of end-markers in BWT: ulong endmarkerRank = alphabetrank_i_tmp - 1; - (*endmarkerDocId)[endmarkerRank] = textId; + endmarkerDocId[endmarkerRank] = (textId + 1) % numberOfTexts; // Store text length and text start position: if (textId < (DocId)numberOfTexts - 1) { - //(*textLength)[textId + 1] = posOfSuccEndmarker - x; (*textStartPos)[textId + 1] = x; // x is the position of end-marker. posOfSuccEndmarker = x; } @@ -1298,36 +1025,71 @@ void TCImplementation::maketables() // LF-mapping from '\0' does not work with this (pseudo) BWT (see details from Wolfgang's thesis). p = textId; // Correct LF-mapping to the last char of the previous text. } - else + else // Now c != '\0', do LF-mapping: p = C[c]+alphabetrank_i_tmp-1; } assert(textId == 0); - sampled = new BSGAP(sampledpositions,n,true); - sampleLength = sampled->rank(n-1); + sampled = new static_bitsequence_rrr02(sampledpositions, n, 16); + delete [] sampledpositions; + ulong sampleLength = sampled->rank1(n-1); assert(sampleCount == sampleLength); // Suffixes store an offset from the text start position suffixes = new BlockArray(sampleLength, Tools::CeilLog2(maxTextLength)); suffixDocId = new BlockArray(sampleLength, Tools::CeilLog2(numberOfTexts)); - for(ulong i=0; irank((*positions)[i]); - if (j==0) j=sampleLength; - TextPosition textPos = (*tmpSuffix)[i]; - (*suffixDocId)[j-1] = DocIdAtTextPos(textStartPos, textPos); - - assert((unsigned)DocIdAtTextPos(textStartPos, textPos) < numberOfTexts); - assert((*suffixDocId)[j-1] < numberOfTexts); - // calculate offset from text start: - (*suffixes)[j-1] = textPos - (*textStartPos)[(*suffixDocId)[j-1]]; + p=bwtEndPos; + textId = numberOfTexts; + + TextStorageBuilder tsbuilder(n); + + /** + * Second pass: populate tables suffixes and suffixDocId. + */ + for (ulong i=n-1;iaccess(p)) { + ulong j = sampled->rank1(p)-1; + + (*suffixDocId)[j] = DocIdAtTextPos(textStartPos, x); + + // calculate offset from text start: + (*suffixes)[j] = x - (*textStartPos)[(*suffixDocId)[j]]; + } + + uchar c = alphabetrank->access(p, alphabetrank_i_tmp); + tsbuilder[i] = c; + + if (c == '\0') + { + --textId; + // LF-mapping from '\0' does not work with this (pseudo) BWT (see details from Wolfgang's thesis). + p = textId; // Correct LF-mapping to the last char of the previous text. + } + else // Now c != '\0', do LF-mapping: + p = C[c]+alphabetrank_i_tmp-1; } - // FIXME Temp, remove - delete tmpSuffix; - delete positions; -// delete textLength; + assert(textId == 0); delete textStartPos; + + textStorage = tsbuilder.InitTextStorage(); + +#ifdef DEBUG_MEMUSAGE + std::cerr << "max heap usage before Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; + HeapProfiler::ResetMaxHeapConsumption(); +#endif + + alphabet_mapper * am = new alphabet_mapper_none(); + static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(16); // FIXME samplerate? + Doc = new static_sequence_wvtree_noptrs(endmarkerDocId, numberOfTexts, bmb, am, true); + delete bmb; + // delete [] endmarkerDocId; // already deleted in static_sequence_wvtree_noptrs! + +#ifdef DEBUG_MEMUSAGE + std::cerr << "max heap usage after Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; +#endif }