X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=TCImplementation.cpp;h=c3b430a16e7ac762420c0c8c514d9501693608b8;hb=3c8e8e6146312f6f55046c451897234fed56608d;hp=a8303d8be74b7251ba2171dda41cda9f27c4499a;hpb=b472b8a9abdb1695994b4b23963de98c361dc66b;p=SXSI%2FTextCollection.git diff --git a/TCImplementation.cpp b/TCImplementation.cpp index a8303d8..c3b430a 100644 --- a/TCImplementation.cpp +++ b/TCImplementation.cpp @@ -19,6 +19,7 @@ *****************************************************************************/ #include "TCImplementation.h" +//#define DEBUG_MEMUSAGE #ifdef DEBUG_MEMUSAGE #include "HeapProfiler.h" // FIXME remove #endif @@ -40,7 +41,7 @@ namespace SXSI { // Save file version info -const uchar TCImplementation::versionFlag = 4; +const uchar TCImplementation::versionFlag = 6; /** * Constructor inits an empty dynamic FM-index. @@ -63,10 +64,12 @@ bool TCImplementation::EmptyText(DocId k) const return false; // Empty texts are not indexed } -uchar* TCImplementation::GetText(DocId k) const +uchar * TCImplementation::GetText(DocId k) const { assert(k < (DocId)numberOfTexts); - TextPosition i = k; + + return textStorage->GetText(k); +/* TextPosition i = k; string result; // Reserve average string length to avoid reallocs @@ -87,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 @@ -524,30 +527,7 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern // We want unique document indentifiers, using std::set to collect them std::set resultSet; - - // Check each occurrence - for (; sp <= ep; ++sp) - { - TextPosition i = sp; - uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->access(i)) - { - i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping - c = alphabetrank->access(i); - } - if (c == '\0') - { - // Rank among the end-markers in BWT - unsigned endmarkerRank = 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); - } - } + EnumerateDocuments(resultSet, sp, ep); // Convert std::set to std::vector TextCollection::document_result result(resultSet.begin(), resultSet.end()); @@ -566,33 +546,7 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern // We want unique document indentifiers, using std::set to collect them std::set resultSet; - - // Check each occurrence - for (; sp <= ep; ++sp) - { - TextPosition i = sp; - uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->access(i)) - { - i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping - c = alphabetrank->access(i); - } - if (c == '\0') - { - // Rank among the end-markers in BWT - unsigned endmarkerRank = 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); - } - } + EnumerateDocuments(resultSet, sp, ep, begin, end); // Convert std::set to std::vector TextCollection::document_result result(resultSet.begin(), resultSet.end()); @@ -625,6 +579,50 @@ TextCollection::document_result TCImplementation::LessThan(uchar const * pattern return EnumerateEndmarkers(sp, ep, begin, end); } + +TextCollection::document_result TCImplementation::Kmismaches(uchar const * pattern, unsigned k) const +{ + TextPosition m = strlen((char *)pattern); + if (m == 0) + return TextCollection::document_result(); // empty result set + + suffix_range_vector ranges; + kmismatches(ranges, pattern, 0, n-1, m, k); + std::set resultSet; + + for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it) + // Iterate through docs in [sp,ep]: + EnumerateDocuments(resultSet, (*it).first, (*it).second); + + // Convert std::set to std::vector + TextCollection::document_result result(resultSet.begin(), resultSet.end()); + return result; +} + +TextCollection::document_result TCImplementation::Kerrors(uchar const * pattern, unsigned k) const +{ + TextPosition m = strlen((char *)pattern); + if (m == 0) + return TextCollection::document_result(); // empty result set + + suffix_range_vector ranges; + ulong *dd = new ulong[m+1]; + for (ulong i=0;i resultSet; + for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it) + // Iterate through docs in [sp,ep]: + EnumerateDocuments(resultSet, (*it).first, (*it).second); + + // Convert std::set to std::vector + TextCollection::document_result result(resultSet.begin(), resultSet.end()); + return result; +} + + /** * Full result set queries */ @@ -640,34 +638,7 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern full_result result; result.reserve(ep-sp+1); // Try to avoid reallocation. - - // Report each occurrence - for (; sp <= ep; ++sp) - { - TextPosition i = sp; - TextPosition dist = 0; - uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->access(i)) - { - i = C[c]+alphabetrank->rank(c,i)-1; - c = alphabetrank->access(i); - ++ dist; - } - if (c == '\0') - { - // Rank among the end-markers in BWT - unsigned endmarkerRank = 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)); - } - } + EnumeratePositions(result, sp, ep); return result; } @@ -684,39 +655,46 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern full_result result; result.reserve(ep-sp+1); // Try to avoid reallocation. + EnumeratePositions(result, sp, ep, begin, end); + + return result; +} - // Report each occurrence - for (; sp <= ep; ++sp) - { - TextPosition i = sp; - TextPosition dist = 0; - uchar c = alphabetrank->access(i); - while (c != '\0' && !sampled->access(i)) - { - i = C[c]+alphabetrank->rank(c,i)-1; - c = alphabetrank->access(i); - ++ dist; - } - if (c == '\0') - { - // 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 = 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]; +TextCollection::full_result TCImplementation::FullKmismatches(uchar const * pattern, unsigned k) const +{ + TextPosition m = strlen((char *)pattern); + if (m == 0) + return TextCollection::full_result(); // empty result set - if (docId >= begin && docId <= end) - result.push_back(make_pair(docId, textPos)); - } - } - + suffix_range_vector ranges; + ulong count = kmismatches(ranges, pattern, 0, n-1, m, k); + + TextCollection::full_result result; + result.reserve(count); // avoid reallocation. + for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it) + // Iterate through docs in [sp,ep]: + EnumeratePositions(result, (*it).first, (*it).second); + return result; +} + +TextCollection::full_result TCImplementation::FullKerrors(uchar const * pattern, unsigned k) const +{ + TextPosition m = strlen((char *)pattern); + if (m == 0) + return TextCollection::full_result(); // empty result set + + suffix_range_vector ranges; + ulong *dd = new ulong[m+1]; + for (unsigned i=0;isave(file); + textStorage->Save(file); fflush(file); } @@ -815,6 +794,7 @@ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength)."); Doc = static_sequence::load(file); + textStorage = new TextStorage(file); // FIXME Construct data structures with new samplerate //maketables(); @@ -825,7 +805,100 @@ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) /** * Rest of the functions follow... */ +ulong TCImplementation::searchPrefix(uchar const *pattern, ulong i, ulong *sp, ulong *ep) const +{ + int c; + while (*sp<=*ep && i>=1) + { + c = (int)pattern[--i]; + *sp = C[c]+alphabetrank->rank(c,*sp-1); + *ep = C[c]+alphabetrank->rank(c,*ep)-1; + } + if (*sp<=*ep) + return *ep - *sp + 1; + else + return 0; +} + + +ulong TCImplementation::kmismatches(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k) const +{ + if (sp>ep) return 0; + if (j == 0) + { + result.push_back(std::make_pair(sp,ep)); + return ep-sp+1; + } + int c; + ulong spnew; + ulong epnew; + int knew; + ulong sum=0; + if (k==0) + { + sum = searchPrefix(pattern, j, &sp, &ep); + if (sp<=ep) + result.push_back(std::make_pair(sp, ep)); + return sum; + } + vector chars = alphabetrank->accessAll(sp, ep); + for (vector::iterator it = chars.begin(); it != chars.end(); ++it) + { + if (*it == 0) + continue; // skip '\0' + c = *it; + spnew = C[c]+alphabetrank->rank(c,sp-1); + epnew = C[c]+alphabetrank->rank(c,ep)-1; + if (c!=pattern[j-1]) knew = (int)k-1; else knew = k; + if (knew>=0) sum += kmismatches(result, pattern, spnew, epnew, j-1, knew); + } + return sum; +} +//first call kerrors(pattern,1,n,m+k,k,d,m), where d[i]=i +ulong TCImplementation::kerrors(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k, ulong const *d, ulong m) const +{ + cout << "j = " << j << ", k = " << k << ", d:"; + for (unsigned i = 0; i < m+1; ++i) + cout << " " << d[i]; + cout << endl; + + if (d[m]<=k) // range of suffixes with at most k-errors found + { + if (sp<=ep) + result.push_back(std::make_pair(sp, ep)); + return (sp<=ep)?ep-sp+1:0ul; + } + if (sp>ep || j==0) + return 0; + ulong *dnew = new ulong[m+1]; + int c; + ulong spnew; + ulong p,lowerbound; + ulong epnew; + ulong sum=0; + vector chars = alphabetrank->accessAll(sp, ep); + for (vector::iterator it = chars.begin(); it != chars.end(); ++it) + { + if (*it == 0) + continue; // skip '\0' + c = *it; + spnew = C[c]+alphabetrank->rank(c,sp-1); + epnew = C[c]+alphabetrank->rank(c,ep)-1; + if (spnew>epnew) continue; + dnew[0]=m+k-j+1; + lowerbound=k+1; + for (p=1; p<=m; p++) { + dnew[p]=myminofthree(d[p]+1,dnew[p-1]+1,(c==pattern[m-p])?d[p-1]:(d[p-1]+1)); + if (dnew[p]access(p, alphabetrank_i_tmp); + tsbuilder[i] = c; + if (c == '\0') { --textId; @@ -1062,9 +1140,10 @@ void TCImplementation::maketables() p = C[c]+alphabetrank_i_tmp-1; } 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();