X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=TCImplementation.cpp;fp=TCImplementation.cpp;h=0000000000000000000000000000000000000000;hb=89dc22aee980ba16f757cd9a7f77478c2da50051;hp=1a29f2524eccf74a394c02aed5b62bf4c54bb252;hpb=443151511a86083b21c1c06eb610f86b3aed35be;p=SXSI%2FTextCollection.git diff --git a/TCImplementation.cpp b/TCImplementation.cpp deleted file mode 100644 index 1a29f25..0000000 --- a/TCImplementation.cpp +++ /dev/null @@ -1,1297 +0,0 @@ -/****************************************************************************** - * Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki * - * * - * * - * This program is free software; you can redistribute it and/or modify * - * it under the terms of the GNU Lesser General Public License as published * - * by the Free Software Foundation; either version 2 of the License, or * - * (at your option) any later version. * - * * - * This program is distributed in the hope that it will be useful, * - * but WITHOUT ANY WARRANTY; without even the implied warranty of * - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * - * GNU Lesser General Public License for more details. * - * * - * You should have received a copy of the GNU Lesser General Public License * - * along with this program; if not, write to the * - * Free Software Foundation, Inc., * - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * - *****************************************************************************/ -#include "TCImplementation.h" - -//#define DEBUG_MEMUSAGE -#ifdef DEBUG_MEMUSAGE -#include "HeapProfiler.h" // FIXME remove -#endif - -#include -#include -#include -#include -#include -#include -#include -#include // For strlen() -using std::vector; -using std::pair; -using std::make_pair; -using std::map; -using std::string; -namespace SXSI -{ - -// Save file version info -const uchar TCImplementation::versionFlag = 8; - -/** - * Constructor inits an empty dynamic FM-index. - * Samplerate defaults to TEXTCOLLECTION_DEFAULT_SAMPLERATE. - */ -TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerate_, - unsigned numberOfTexts_, ulong maxTextLength_, ulong numberOfSamples_, - CSA::DeltaVector & notIndexed, const string & niText, char tsType) - : n(length), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0), - suffixDocId(0), numberOfTexts(numberOfTexts_), maxTextLength(maxTextLength_), Doc(0) -{ - makewavelet(bwt); // Deletes bwt! - bwt = 0; - - // Make sampling tables - maketables(numberOfSamples_, tsType, notIndexed, niText); -} - -bool TCImplementation::EmptyText(DocId k) const -{ - assert(k < (DocId)numberOfTexts); - return false; // Empty texts are not indexed -} - -uchar * TCImplementation::GetText(DocId k) const -{ - assert(k < (DocId)numberOfTexts); - - return textStorage->GetText(k); -/* TextPosition i = k; - - string result; - // Reserve average string length to avoid reallocs - result.reserve(n/numberOfTexts); - - uchar c = alphabetrank->access(i); - while (c != '\0') - { - result.push_back(c); - i = C[c]+alphabetrank->rank(c,i)-1; - - c = alphabetrank->access(i); // "next" char. - } - - // Convert to uchar (FIXME return string?) - i = result.size(); - uchar* res = new uchar[i+1]; - res[i] = '\0'; - for (ulong j = 0; j < i; ++j) - res[i-j-1] = result[j]; - return res;*/ -} - -/* - * Substring queries are supported via the pointer returned by TextStorage::GetText -uchar* TCImplementation::GetText(DocId k, TextPosition i, TextPosition j) const -{ - assert(k < (DocId)numberOfTexts); - assert(j < (*textLength)[k]); - assert(i <= j); - - ulong textRank = 0; - - // Start position of k'th text - ulong start = (*textStartPos)[k]; - - return Substring(i + start, j-i+1); - }*/ - - - -/****************************************************************** - * Existential queries - */ -bool TCImplementation::IsPrefix(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return true; - - TextPosition sp = 0, ep = 0; - Search(pattern, m, &sp, &ep); - - // Check for end-marker(s) in result interval - if (CountEndmarkers(sp, ep)) - return true; - return false; -} - -bool TCImplementation::IsPrefix(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return true; - - TextPosition sp = 0, ep = 0; - Search(pattern, m, &sp, &ep); - - // Check for end-marker(s) in result interval - if (CountEndmarkers(sp, ep, begin, end)) - return true; - return false; -} - - -bool TCImplementation::IsSuffix(uchar const *pattern) const -{ - // Here counting is as fast as IsSuffix(): - if (CountSuffix(pattern) > 0) - return true; - return false; -} - -bool TCImplementation::IsSuffix(uchar const *pattern, DocId begin, DocId end) const -{ - // Here counting is as fast as IsSuffix(): - if (CountSuffix(pattern, begin, end) > 0) - return true; - return false; -} - -bool TCImplementation::IsEqual(uchar const *pattern) const -{ - TextPosition m = std::strlen((char *)pattern); - if (m == 0) - return false; // No empty texts exists - - TextPosition sp = 0, ep = 0; - // Match including end-marker - Search(pattern, m+1, &sp, &ep); - - // Check for end-marker(s) in result interval - if (CountEndmarkers(sp, ep)) - return true; - return false; -} - -bool TCImplementation::IsEqual(uchar const *pattern, DocId begin, DocId end) const -{ - TextPosition m = std::strlen((char *)pattern); - if (m == 0) - return false; // No empty texts exists - - TextPosition sp = 0, ep = 0; - // Match including end-marker - Search(pattern, m+1, &sp, &ep, begin, end); - - // Check for end-marker(s) in result interval - if (CountEndmarkers(sp, ep)) - return true; - return false; -} - -bool TCImplementation::IsContains(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return true; - - TextPosition sp = 0, ep = 0; - // Just check if pattern exists somewhere - ulong count = Search(pattern, m, &sp, &ep); - - if (count > 0) - return true; - return false; -} - -bool TCImplementation::IsContains(uchar const * pattern, DocId begin, DocId end) const -{ - // Here counting is as fast as existential querying - if (CountContains(pattern, begin, end) > 0) - return true; // FIXME No need to filter result set - return false; -} - -bool TCImplementation::IsLessThan(uchar const * pattern) const -{ - if (CountLessThan(pattern) > 0) - return true; - return false; -} - -bool TCImplementation::IsLessThan(uchar const * pattern, DocId begin, DocId end) const -{ - if (CountLessThan(pattern, begin, end) > 0) - return true; - return false; -} - -/****************************************************************** - * Counting queries - */ -ulong TCImplementation::Count(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return 0; - - TextPosition sp = 0, ep = 0; - unsigned count = (unsigned) Search(pattern, m, &sp, &ep); - return count; -} - -unsigned TCImplementation::CountPrefix(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return numberOfTexts; - - TextPosition sp = 0, ep = 0; - Search(pattern, m, &sp, &ep); - - // Count end-markers in result interval - return CountEndmarkers(sp, ep); -} - -unsigned TCImplementation::CountPrefix(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return numberOfTexts; - - TextPosition sp = 0, ep = 0; - Search(pattern, m, &sp, &ep); - - // Count end-markers in result interval - return CountEndmarkers(sp, ep, begin, end); -} - -unsigned TCImplementation::CountSuffix(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return numberOfTexts; - - TextPosition sp = 0, ep = 0; - // Search with end-marker - unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep); - - return count; -} - -unsigned TCImplementation::CountSuffix(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return numberOfTexts; - - TextPosition sp = 0, ep = 0; - // Search with end-marker - unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep, begin, end); - - return count; -} - -unsigned TCImplementation::CountEqual(uchar const *pattern) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - return 0; // No empty texts. - - TextPosition sp = 0, ep = 0; - // Match including end-marker - Search(pattern, m+1, &sp, &ep); - - // Count end-markers in result interval - return CountEndmarkers(sp, ep); -} - -unsigned TCImplementation::CountEqual(uchar const *pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - return 0; // No empty texts. - - TextPosition sp = 0, ep = 0; - // Match including end-marker - Search(pattern, m+1, &sp, &ep, begin, end); - - // Count end-markers in result interval - return CountEndmarkers(sp, ep); // Already within [begin, end] -} - -unsigned TCImplementation::CountContains(uchar const * pattern) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - 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. - TextCollection::document_result result = Contains(pattern); - return result.size(); -} - -unsigned TCImplementation::CountContains(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - 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. - TextCollection::document_result result = Contains(pattern, begin, end); - return result.size(); -} - -// Less than or equal -unsigned TCImplementation::CountLessThan(uchar const * pattern) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - return 0; // No empty texts. - - TextPosition sp = 0, ep = 0; - SearchLessThan(pattern, m, &sp, &ep); - - // Count end-markers in result interval - return CountEndmarkers(sp, ep); -} - -unsigned TCImplementation::CountLessThan(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - return 0; // No empty texts. - - TextPosition sp = 0, ep = 0; - SearchLessThan(pattern, m, &sp, &ep); - - // Count end-markers in result interval - return CountEndmarkers(sp, ep, begin, end); -} - -/** - * Document reporting queries - */ -TextCollection::document_result TCImplementation::Prefix(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); // FIXME Should return all 1...k - - TextPosition sp = 0, ep = 0; - Search(pattern, m, &sp, &ep); - - // Iterate through end-markers in [sp,ep]: - return EnumerateEndmarkers(sp, ep); -} - -TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); // FIXME Should return all 1...k - - TextPosition sp = 0, ep = 0; - Search(pattern, m, &sp, &ep); - - // Return end-markers in [sp,ep] and [begin, end]: - return EnumerateEndmarkers(sp, ep, begin, end); -} - -TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); // FIXME Should return all 1...k - - TextPosition sp = 0, ep = 0; - // Search with end-marker - Search(pattern, m+1, &sp, &ep); - - TextCollection::document_result result; - result.reserve(ep-sp+1); // Try to avoid reallocation. - - // 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; - c = alphabetrank->access(i); - } - // Assert: c == '\0' OR sampled->IsBitSet(i) - - if (c == '\0') - { - // Rank among the end-markers in BWT - unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; - result.push_back(Doc->access(endmarkerRank)); - } - else // Sampled position - { - DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; - result.push_back(docId); - } - } - - return result; -} - -TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); // FIXME Should return all 1...k - - TextPosition sp = 0, ep = 0; - // Search with end-marker - Search(pattern, m+1, &sp, &ep, begin, end); - - TextCollection::document_result result; - result.reserve(ep-sp+1); // Try to avoid reallocation. - - // Check each occurrence, already within [begin, end] - 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; - c = alphabetrank->access(i); - } - // Assert: c == '\0' OR sampled->IsBitSet(i) - - if (c == '\0') - { - // Rank among the end-markers in BWT - unsigned endmarkerRank = alphabetrank->rank(0, i) - 1; - result.push_back(Doc->access(endmarkerRank)); - } - else // Sampled position - { - DocId docId = (*suffixDocId)[sampled->rank1(i)-1]; - result.push_back(docId); - } - } - - return result; -} - - -TextCollection::document_result TCImplementation::Equal(uchar const *pattern) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - return TextCollection::document_result(); // FIXME Should return all empty texts - - TextPosition sp = 0, ep = 0; - // Match including end-marker - Search(pattern, m+1, &sp, &ep); - - // Report end-markers in result interval - return EnumerateEndmarkers(sp, ep); -} - -TextCollection::document_result TCImplementation::Equal(uchar const *pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char const *)pattern); - if (m == 0) - return TextCollection::document_result(); // FIXME Should return all empty texts - - TextPosition sp = 0, ep = 0; - // Match including end-marker - Search(pattern, m+1, &sp, &ep, begin, end); - - // Report end-markers in result interval - return EnumerateEndmarkers(sp, ep, begin, end); -} - - -TextCollection::document_result TCImplementation::Contains(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); - - TextPosition sp = 0, ep = 0; - // Search all occurrences - Search(pattern, m, &sp, &ep); - - // We want unique document indentifiers, using std::set to collect them - std::set resultSet; - EnumerateDocuments(resultSet, sp, ep); - - // Convert std::set to std::vector - TextCollection::document_result result(resultSet.begin(), resultSet.end()); - return result; -} - -TextCollection::document_result TCImplementation::Contains(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); - - TextPosition sp = 0, ep = 0; - // Search all occurrences - Search(pattern, m, &sp, &ep); - - // We want unique document indentifiers, using std::set to collect them - std::set resultSet; - EnumerateDocuments(resultSet, sp, ep, begin, end); - - // Convert std::set to std::vector - TextCollection::document_result result(resultSet.begin(), resultSet.end()); - return result; -} - - -/** - *** -* * FIXME Lessthan or equal - */ -TextCollection::document_result TCImplementation::LessThan(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); // empty result set - - TextPosition sp = 0, ep = 0; - SearchLessThan(pattern, m, &sp, &ep); - - // Report end-markers in result interval - return EnumerateEndmarkers(sp, ep); -} - -TextCollection::document_result TCImplementation::LessThan(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return TextCollection::document_result(); // empty result set - - TextPosition sp = 0, ep = 0; - SearchLessThan(pattern, m, &sp, &ep); - - // Iterate through end-markers in [sp,ep] and [begin, end]: - 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 - */ -TextCollection::full_result TCImplementation::FullContains(uchar const * pattern) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return full_result(); // FIXME Throw exception? - - TextPosition sp = 0, ep = 0; - // Search all occurrences - Search(pattern, m, &sp, &ep); - - full_result result; - result.reserve(ep-sp+1); // Try to avoid reallocation. - EnumeratePositions(result, sp, ep); - - return result; -} - -TextCollection::full_result TCImplementation::FullContains(uchar const * pattern, DocId begin, DocId end) const -{ - TextPosition m = strlen((char *)pattern); - if (m == 0) - return full_result(); // FIXME Throw exception? - - TextPosition sp = 0, ep = 0; - // Search all occurrences - Search(pattern, m, &sp, &ep); - - full_result result; - result.reserve(ep-sp+1); // Try to avoid reallocation. - EnumeratePositions(result, sp, ep, begin, end); - - return result; -} - -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 - - 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;in), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (n)."); - if (std::fwrite(&(this->samplerate), sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (samplerate)."); - - for(ulong i = 0; i < 256; ++i) - if (std::fwrite(this->C + i, sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (C table)."); - - if (std::fwrite(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (bwt end position)."); - - alphabetrank->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->maxTextLength), sizeof(ulong), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (maxTextLength)."); - - Doc->save(file); - textStorage->Save(file); - fflush(file); -} - - -/** - * Load index from a file handle - * - * Throws a std::runtime_error exception on i/o error. - * For more info, see TCImplementation::Save(). - * - * index_mode_t is defined in TextCollection.h and - * defaults to both the index and "naive" text. - * - * Note: Samplerate can not be changed during load. - */ -TCImplementation::TCImplementation(FILE *file, index_mode_t im, unsigned samplerate_) - : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0), - suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0) -{ - uchar verFlag = 0; - if (std::fread(&verFlag, 1, 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (version flag)."); - if (verFlag != TCImplementation::versionFlag) - throw std::runtime_error("TCImplementation::Load(): invalid save file version."); - - if (std::fread(&(this->n), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (n)."); - if (std::fread(&samplerate, sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (samplerate)."); -// FIXME samplerate can not be changed during load. -// if (this->samplerate == 0) -// this->samplerate = samplerate; - - for(ulong i = 0; i < 256; ++i) - if (std::fread(this->C + i, sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (C table)."); - - if (std::fread(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (bwt end position)."); - - alphabetrank = static_sequence::load(file); - if (im == index_mode_text_only) { delete alphabetrank; alphabetrank = 0; } - - sampled = static_bitsequence::load(file); - if (im == index_mode_text_only) { delete sampled; sampled = 0; } - suffixes = new BlockArray(file); - if (im == index_mode_text_only) { delete suffixes; suffixes = 0; } - suffixDocId = new BlockArray(file); - if (im == index_mode_text_only) { delete suffixDocId; suffixDocId = 0; } - - if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (numberOfTexts)."); - if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength)."); - - Doc = new ArrayDoc(file); //static_sequence::load(file); - if (im == index_mode_text_only) { delete Doc; Doc = 0; } - - textStorage = TextStorage::Load(file); - - // FIXME Construct data structures with new samplerate - //maketables(); -} - - - -/** - * 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 -{ - ulong sum=0; - if (d[m]<=k) // range of suffixes with at most k-errors found - { - if (sp<=ep) - result.push_back(std::make_pair(sp, ep)); - sum += (sp<=ep)?ep-sp+1:0ul; - } - if (sp>ep || j==0) - return sum; - ulong *dnew = new ulong[m+1]; - int c; - ulong spnew; - ulong p,lowerbound; - ulong epnew; - 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]rank(c,i) - int c = (int)pattern[m-1]; - TextPosition i=m-1; - TextPosition sp = C[c]; - TextPosition ep = C[c+1]-1; - while (sp<=ep && i>=1) - { -// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep); - c = (int)pattern[--i]; - sp = C[c]+alphabetrank->rank(c,sp-1); - ep = C[c]+alphabetrank->rank(c,ep)-1; - } - *spResult = sp; - *epResult = ep; - if (sp<=ep) - return ep - sp + 1; - else - return 0; -} - -ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult, DocId begin, DocId end) const -{ - // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i) - int c = (int)pattern[m-1]; - assert(c == 0); // Start from endmarkers - TextPosition i=m-1; - TextPosition sp = begin; - TextPosition ep = end; - while (sp<=ep && i>=1) - { -// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep); - c = (int)pattern[--i]; - sp = C[c]+alphabetrank->rank(c,sp-1); - ep = C[c]+alphabetrank->rank(c,ep)-1; - } - *spResult = sp; - *epResult = ep; - if (sp<=ep) - return ep - sp + 1; - else - return 0; -} - - -ulong TCImplementation::SearchLessThan(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) - uint c = (int)pattern[m-1]; - TextPosition i=m-1; - TextPosition sp = 1; - TextPosition ep = C[c+1]-1; - while (sp<=ep && i>=1) - { -// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep); - c = (int)pattern[--i]; - uint result = alphabetrank->rankLessThan(c,ep); - if (result == ~0u) - ep = 0; - else - ep = C[c]+result-1; - } - *spResult = sp; - *epResult = ep; - if (sp<=ep) - return ep - sp + 1; - else - return 0; -} - - -TCImplementation::~TCImplementation() { - delete alphabetrank; - delete sampled; - delete suffixes; - delete suffixDocId; - delete Doc; - delete textStorage; -} - -void TCImplementation::makewavelet(uchar *bwt) -{ - ulong i, min = 0, - max; - for (i=0;i<256;i++) - C[i]=0; - for (i=0;i0) {min = i; break;} - for (i=255;i>=min;--i) - if (C[i]>0) {max = i; break;} - - ulong prev=C[0], temp; - C[0]=0; - for (i=1;i<256;i++) { - temp = C[i]; - C[i]=C[i-1]+prev; - prev = temp; - } -// this->codetable = node::makecodetable(bwt,n); -// alphabetrank = new THuffAlphabetRank(bwt,n, this->codetable,0); -// delete [] bwt; - //alphabetrank = new RLWaveletTree(bwt, n); // Deletes bwt! -// std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; - -#ifdef DEBUG_MEMUSAGE - std::cerr << "max heap usage before WT: " << 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(8); //rrr02(8); // FIXME samplerate? - wt_coder * wtc = new wt_coder_huff(bwt,n,am);//binary(bwt,n,am); // FIXME Huffman shape - alphabetrank = new static_sequence_wvtree(bwt,n,wtc,bmb,am); - delete bmb; - bwt = 0; // already deleted - -#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(ulong sampleLength, char tsType, CSA::DeltaVector & notIndexed, const string & niText) -{ - // Calculate BWT end-marker position (of last inserted text) - { - ulong i = 0; - uint alphabetrank_i_tmp = 0; - uchar c = alphabetrank->access(i, alphabetrank_i_tmp); - while (c != '\0') - { - i = C[c]+alphabetrank_i_tmp-1; - c = alphabetrank->access(i, alphabetrank_i_tmp); - } - - this->bwtEndPos = i; - } - -#ifdef DEBUG_MEMUSAGE - std::cerr << "heap usage before BWT traverse: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl; - HeapProfiler::ResetMaxHeapConsumption(); -#endif - - // Build up array for text starting positions -// BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n)); -// (*textStartPos)[0] = 0; - - // Mapping from end-markers to doc ID's: - unsigned logNumberOfTexts = Tools::CeilLog2(numberOfTexts); -// uint *endmarkerDocId = new uint[(numberOfTexts * logNumberOfTexts)/(8*sizeof(uint)) + 1]; - BlockArray *endmarkerDocId = new BlockArray(numberOfTexts, logNumberOfTexts); - - BlockArray* positions = new BlockArray(sampleLength, Tools::CeilLog2(this->n)); - uint *sampledpositions = new uint[n/(sizeof(uint)*8)+1]; - for (ulong i = 0; i < n / (sizeof(uint)*8) + 1; i++) - sampledpositions[i] = 0; - - ulong x,p=bwtEndPos; - ulong sampleCount = 0; - // Keeping track of text position of prev. end-marker seen - ulong posOfSuccEndmarker = n-1; - DocId textId = numberOfTexts; - ulong ulongmax = 0; - ulongmax--; - uint alphabetrank_i_tmp =0; - - // Text length = n + number of bytes not indexed. - TextStorageBuilder tsbuilder(n + niText.length()); - ulong tsb_i = n + niText.length(); // Iterator from text length to 0. - string::const_reverse_iterator nit_i = niText.rbegin(); // Iterator through non-indexed texts - - for (ulong i=n-1;iGetPos(i) - x=(i==n-1)?0:i+1; - - uchar c = alphabetrank->access(p, alphabetrank_i_tmp); - - tsbuilder[--tsb_i] = c; // Build TextStorage - - if ((posOfSuccEndmarker - i) % samplerate == 0 && c != '\0') - { - set_field(sampledpositions,1,p,1); - (*positions)[sampleCount] = p; - sampleCount ++; - } - - if (c == '\0') - { - unsigned prevTextId = textId; // Cache textId value. - --textId; - /** - * At first c == '\0' it holds that (prevTextId == numberOfTexts), thus, - * we have to search for the first text that is actually *indexed* - * to get correct prevTextId. - */ - if (prevTextId == numberOfTexts) - { - prevTextId = 0; - while (notIndexed.isSet(prevTextId)) - ++ prevTextId; - // Now prevTextId points to the first indexed Doc ID. - } - - /** - * Insert non-indexed texts - */ - while (notIndexed.isSet(textId)) - { - do { - tsbuilder[tsb_i] = *nit_i; - -- tsb_i; - ++ nit_i; - } while (nit_i != niText.rend() && *nit_i != '\0'); - - tsbuilder[tsb_i] = '\0'; - - if (textId == 0) - break; - --textId; - } - - // Record the order of end-markers in BWT: - ulong endmarkerRank = alphabetrank_i_tmp - 1; - //set_field(endmarkerDocId, logNumberOfTexts, endmarkerRank, (textId + 1) % numberOfTexts); - (*endmarkerDocId)[endmarkerRank] = prevTextId % numberOfTexts; - - // Store text length and text start position: - if (textId < (DocId)numberOfTexts - 1) - { -// (*textStartPos)[textId + 1] = x; // x-1 is text position of end-marker. - - posOfSuccEndmarker = i; - } - - // LF-mapping from '\0' does not work with this (pseudo) BWT. - // Correct LF-mapping to the last char of the previous text: - p = textId - notIndexed.rank(textId); - } - else // Now c != '\0', do LF-mapping: - p = C[c]+alphabetrank_i_tmp-1; - } - while (textId > 0 && notIndexed.isSet(textId-1)) - { - do { - -- tsb_i; - tsbuilder[tsb_i] = *nit_i; - ++ nit_i; - } while (nit_i != niText.rend() && *nit_i != '\0'); - --textId; - } - assert(textId == 0); - assert(tsb_i == 0); - assert(nit_i == niText.rend()); - -#ifdef DEBUG_MEMUSAGE - std::cerr << "heap usage before tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl; - HeapProfiler::ResetMaxHeapConsumption(); -#endif - - textStorage = tsbuilder.InitTextStorage(tsType); - -#ifdef DEBUG_MEMUSAGE - std::cerr << "heap usage after tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl; - HeapProfiler::ResetMaxHeapConsumption(); -#endif - - sampled = new static_bitsequence_rrr02(sampledpositions, n, 16); - delete [] sampledpositions; - assert(sampleCount == sampleLength); - assert(sampled->rank1(n-1) == sampleLength); - -#ifdef DEBUG_MEMUSAGE - std::cerr << "heap usage after sampled bit vector: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl; - HeapProfiler::ResetMaxHeapConsumption(); -#endif - - // Suffixes store an offset from the text start position - suffixes = new BlockArray(sampleLength, Tools::CeilLog2(maxTextLength)); - suffixDocId = new BlockArray(sampleLength, Tools::CeilLog2(numberOfTexts)); - - x = n + niText.length() - 2; - textId = numberOfTexts - 1; - posOfSuccEndmarker = x + 1; - for(ulong i = 0; i < sampleLength; i ++) { - // Find next sampled text position - while ((posOfSuccEndmarker - x) % samplerate != 0 - || notIndexed.isSet(textId)) // Loop over non-indexed - { - --x; - assert(x != ~0lu); - if (textStorage->IsEndmarker(x)) - { - posOfSuccEndmarker = x--; - -- textId; - } - } - assert((*positions)[i] < n); - ulong j = sampled->rank1((*positions)[i]); - - assert(j != 0); // if (j==0) j=sampleLength; - - TextPosition textPos = (x==n-1)?0:x+1; - (*suffixDocId)[j-1] = textId; // textStorage->DocIdAtTextPos(textPos); - assert(textStorage->DocIdAtTextPos(textPos) == textId); - - assert((*suffixDocId)[j-1] < numberOfTexts); - // calculate offset from text start: - (*suffixes)[j-1] = textPos - textStorage->TextStartPos((*suffixDocId)[j-1]); - --x; - if (x != ~0lu && textStorage->IsEndmarker(x)) - { - posOfSuccEndmarker = x--; - -- textId; - } - } - - delete positions; - -#ifdef DEBUG_MEMUSAGE - std::cerr << "heap usage after sampled arrays: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl; - HeapProfiler::ResetMaxHeapConsumption(); -#endif - -#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_rrr02(32); // FIXME samplerate? - Doc = new static_sequence_wvtree_noptrs(endmarkerDocId, numberOfTexts, logNumberOfTexts, bmb, am, true); - delete bmb;*/ - // delete [] endmarkerDocId; // already deleted in static_sequence_wvtree_noptrs! - - Doc = new ArrayDoc(endmarkerDocId); - -#ifdef DEBUG_MEMUSAGE - std::cerr << "max heap usage after Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl; -#endif -} - - -/** - * Finds document identifier for given text position - * - * Starting text position of the document is stored into second parameter. - * Binary searching on text starting positions. - */ -TextCollection::DocId TCImplementation::DocIdAtTextPos(BlockArray* textStartPos, TextPosition i) const -{ - assert(i < n); - - DocId a = 0; - DocId b = numberOfTexts - 1; - while (a < b) - { - DocId c = a + (b - a)/2; - if ((*textStartPos)[c] > i) - b = c - 1; - else if ((*textStartPos)[c+1] > i) - return c; - else - a = c + 1; - } - - assert(a < (DocId)numberOfTexts); - assert(i >= (*textStartPos)[a]); - assert(i < (a == (DocId)numberOfTexts - 1 ? n : (*textStartPos)[a+1])); - return a; -} - - -} // namespace SXSI -