X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=TCImplementation.cpp;h=211849e312f177c5acfa15387e0daf30b57c237d;hb=26060a4257e11ded60e950b1ffd18a3473dfe63c;hp=723a2b911bf1e00edc986980c7f669f2b7b976f9;hpb=5b209950c7b0533b3082fcc2bde5fce1cf2fe632;p=SXSI%2FTextCollection.git diff --git a/TCImplementation.cpp b/TCImplementation.cpp index 723a2b9..211849e 100644 --- a/TCImplementation.cpp +++ b/TCImplementation.cpp @@ -19,7 +19,9 @@ *****************************************************************************/ #include "TCImplementation.h" -//#include "HeapProfiler.h" // FIXME remove +#ifdef DEBUG_MEMUSAGE +#include "HeapProfiler.h" // FIXME remove +#endif #include #include @@ -378,16 +380,7 @@ 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]: return EnumerateEndmarkers(sp, ep); } @@ -401,15 +394,6 @@ 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. - // Return end-markers in [sp,ep] and [begin, end]: return EnumerateEndmarkers(sp, ep, begin, end); } @@ -427,14 +411,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); @@ -449,7 +432,7 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) } else // Sampled position { - DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; result.push_back(docId); } } @@ -470,14 +453,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); @@ -492,7 +474,7 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, } else // Sampled position { - DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1]; + DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; result.push_back(docId); } } @@ -511,8 +493,6 @@ 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 return EnumerateEndmarkers(sp, ep); } @@ -527,8 +507,6 @@ 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 return EnumerateEndmarkers(sp, ep, begin, end); } @@ -547,13 +525,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); @@ -566,7 +543,7 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern } 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); } @@ -590,13 +567,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); @@ -611,7 +587,7 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern } 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); @@ -632,8 +608,6 @@ 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 return EnumerateEndmarkers(sp, ep); } @@ -647,15 +621,6 @@ 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]: return EnumerateEndmarkers(sp, ep, begin, end); } @@ -676,14 +641,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); @@ -698,9 +662,8 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern } 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]; result.push_back(make_pair(docId, textPos)); } @@ -722,14 +685,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); @@ -747,9 +709,8 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern } 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]; if (docId >= begin && docId <= end) result.push_back(make_pair(docId, textPos)); @@ -798,7 +759,7 @@ 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); @@ -844,7 +805,7 @@ 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); @@ -924,7 +885,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 @@ -972,20 +933,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() @@ -1006,9 +970,7 @@ void TCImplementation::maketables() // Build up arrays for text length and starting positions // FIXME Temp, remove - //BlockArray* textLength = new BlockArray(numberOfTexts, Tools::CeilLog2(maxTextLength)); BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n)); - //(*textLength)[0] = l; (*textStartPos)[0] = 0; // Construct samples @@ -1020,9 +982,9 @@ void TCImplementation::maketables() // Mapping from end-markers to doc ID's: BlockArray *endmarkerDocId = new BlockArray(numberOfTexts, Tools::CeilLog2(numberOfTexts)); - ulong *sampledpositions = new ulong[n/W+1]; - for (ulong i=0;iGetPos(i) + 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); + set_field(sampledpositions,1,p,1); (*positions)[sampleCount] = p; (*tmpSuffix)[sampleCount] = x; // FIXME remove sampleCount ++; @@ -1057,7 +1018,6 @@ void TCImplementation::maketables() // 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; } @@ -1065,13 +1025,14 @@ 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; + sampleLength = sampled->rank1(n-1); assert(sampleCount == sampleLength); // Suffixes store an offset from the text start position @@ -1080,7 +1041,8 @@ void TCImplementation::maketables() for(ulong i=0; irank((*positions)[i]); + ulong j = sampled->rank1((*positions)[i]); + if (j==0) j=sampleLength; TextPosition textPos = (*tmpSuffix)[i]; (*suffixDocId)[j-1] = DocIdAtTextPos(textStartPos, textPos); @@ -1093,31 +1055,38 @@ void TCImplementation::maketables() // FIXME Temp, remove delete tmpSuffix; delete positions; -// delete textLength; delete textStartPos; +#ifdef DEBUG_MEMUSAGE + std::cerr << "max heap usage before Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; + HeapProfiler::ResetMaxHeapConsumption(); +#endif uint *tmp = new uint[numberOfTexts]; // FIXME Silly... -// cout << "Doc: "; for (unsigned i = 0; i < numberOfTexts; ++i) { tmp[i] = ((*endmarkerDocId)[i] + 1) % numberOfTexts; - // cout << tmp[i] << ", "; +// cout << tmp[i] << ","; } // cout << endl; delete endmarkerDocId; + alphabet_mapper * am = new alphabet_mapper_none(); static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(16); // FIXME samplerate? - wt_coder * wtc = new wt_coder_binary(tmp, numberOfTexts, am); - Doc = new static_sequence_wvtree(tmp, numberOfTexts, wtc, bmb, am); + Doc = new static_sequence_wvtree_noptrs(tmp, numberOfTexts, bmb, am); delete bmb; - delete [] tmp; + // delete [] tmp; // already deleted! + +#ifdef DEBUG_MEMUSAGE + std::cerr << "max heap usage after Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; +#endif - /* document_result res = Doc->access(1, 2, 0, 1); - cout << "result: "; + /*document_result res = Doc->access(3, 3, 0, 3); + cout << "Access result: "; for (document_result::iterator it = res.begin(); it != res.end(); ++it) cout << *it << ", "; - cout << endl;*/ + cout << endl; + exit(0);*/ }