*****************************************************************************/
#include "TCImplementation.h"
-//#include "HeapProfiler.h" // FIXME remove
+//#define DEBUG_MEMUSAGE
+#ifdef DEBUG_MEMUSAGE
+#include "HeapProfiler.h" // FIXME remove
+#endif
#include <iostream>
#include <map>
{
// Save file version info
-const uchar TCImplementation::versionFlag = 3;
+const uchar TCImplementation::versionFlag = 6;
/**
* 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_)
+TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerate_,
+ unsigned numberOfTexts_, ulong maxTextLength_, ulong numberOfSamples_)
: 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() <<std::endl;
- ulong *tempB = new ulong[numberOfTexts/W + 1];
- for (ulong i = 0; i < numberOfTexts/W + 1; ++i)
- tempB[i] = 0;
-// for (std::set<unsigned>::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;
// Make sampling tables
- maketables();
+ maketables(numberOfSamples_);
}
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
res[i] = '\0';
for (ulong j = 0; j < i; ++j)
res[i-j-1] = result[j];
- return res;
+ return res;*/
}
/*
* Not supported
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];
{
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
{
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
{
TextPosition m = strlen((char *)pattern);
if (m == 0)
- return numberOfAllTexts;
+ return numberOfTexts;
TextPosition sp = 0, ep = 0;
Search(pattern, m, &sp, &ep);
{
TextPosition m = strlen((char *)pattern);
if (m == 0)
- return numberOfAllTexts;
+ return numberOfTexts;
TextPosition sp = 0, ep = 0;
Search(pattern, m, &sp, &ep);
{
TextPosition m = strlen((char *)pattern);
if (m == 0)
- return numberOfAllTexts;
+ return numberOfTexts;
TextPosition sp = 0, ep = 0;
// Search with end-marker
{
TextPosition m = strlen((char *)pattern);
if (m == 0)
- return numberOfAllTexts;
+ return numberOfTexts;
TextPosition sp = 0, ep = 0;
// Search with end-marker
{
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
{
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
{
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.
{
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.
{
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);
{
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);
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
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
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);
{
// 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);
}
}
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);
{
// 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);
}
}
// 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
// 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);
}
// We want unique document indentifiers, using std::set to collect them
std::set<DocId> 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))
- {
- 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;
-
- // End-marker that we found belongs to the "preceeding" doc in collection:
- DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
- resultSet.insert(docId);
- }
- else
- {
- DocId di = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(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());
- // Map to doc ID's
- for (document_result::iterator it = result.begin(); it != result.end(); ++it)
- *it = emptyTextRank->select0(*it+1);
return result;
}
// We want unique document indentifiers, using std::set to collect them
std::set<DocId> 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))
- {
- 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;
-
- // End-marker that we found belongs to the "preceeding" doc in collection:
- DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
- if (docId >= begin && docId <= end)
- resultSet.insert(docId);
- }
- else
- {
- DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(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());
- // Map to doc ID's
- for (document_result::iterator it = result.begin(); it != result.end(); ++it)
- *it = emptyTextRank->select0(*it+1);
return result;
}
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
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;
+ // Iterate through end-markers in [sp,ep] and [begin, end]:
+ return EnumerateEndmarkers(sp, ep, begin, end);
+}
- 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);
+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
- -- resultSize;
- ++ i;
- }
+ suffix_range_vector ranges;
+ kmismatches(ranges, pattern, 0, n-1, m, k);
+ std::set<DocId> 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<m+1;i++)
+ dd[i]=i;
+ kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
+ delete [] dd;
+ std::set<DocId> 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
*/
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))
- {
- 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 = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
- // Map to doc ID:
- docId = emptyTextRank->select0(docId+1);
- 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
-
- // Map to doc ID:
- docId = emptyTextRank->select0(docId+1);
- result.push_back(make_pair(docId, textPos));
- }
- }
+ EnumeratePositions(result, sp, ep);
return result;
}
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))
- {
- 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 = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
- // Map to doc ID:
- docId = emptyTextRank->select0(docId+1);
- 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
-
- // Map to doc ID:
- docId = emptyTextRank->select0(docId+1);
- if (docId >= begin && docId <= end)
- result.push_back(make_pair(docId, textPos));
- }
- }
+ 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;i<m+1;i++)
+ dd[i]=i;
+ ulong count = kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
+ delete [] dd;
+
+ 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;
+}
+
/**
* Save index to a file handle
BlockArray *suffixes;
BlockArray *suffixDocId;
unsigned numberOfTexts;
- unsigned numberOfAllTexts;
ulong maxTextLength;
- BlockArray *endmarkerDocId;
- BSGAP *emptyTextRank;
+ static_sequence *docId;
*/
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);
}
*/
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)
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();
/**
* 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;
+}
-// FIXME Use 2D-search structure
-unsigned TCImplementation::CountEndmarkers(TextPosition sp, TextPosition ep, DocId begin, DocId end) const
+ulong TCImplementation::kmismatches(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k) 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;
+ 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<int> chars = alphabetrank->accessAll(sp, ep);
+ for (vector<int>::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;
+}
- // Count end-markers in result interval and within [begin, end]
- unsigned count = 0;
- unsigned i = ranksp;
- while (resultSize)
+//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
+{
+ if (d[m]<=k) // range of suffixes with at most k-errors found
{
- // 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;
+ if (sp<=ep)
+ result.push_back(std::make_pair(sp, ep));
+ return (sp<=ep)?ep-sp+1:0ul;
}
- return count;
+ 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<int> chars = alphabetrank->accessAll(sp, ep);
+ for (vector<int>::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]<lowerbound)
+ lowerbound = dnew[p];
+ }
+ if (lowerbound<=k)
+ sum += kerrors(result, pattern, spnew, epnew, j-1, k,dnew,m);
+ }
+ delete [] dnew;
+ return sum;
}
-
+
+
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)
{
// 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
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)
// 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();
+#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()
+void TCImplementation::maketables(ulong sampleLength)
{
// Calculate BWT end-marker position (of last inserted text)
{
this->bwtEndPos = i;
}
- // 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;
+#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
- // 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);
+ // 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:
- endmarkerDocId = new BlockArray(numberOfTexts, Tools::CeilLog2(numberOfTexts));
-
- ulong *sampledpositions = new ulong[n/W+1];
- for (ulong i=0;i<n/W+1;i++)
- sampledpositions[i]=0lu;
+ unsigned logNumberOfTexts = Tools::CeilLog2(numberOfTexts);
+ uint *endmarkerDocId = new uint[(numberOfTexts * logNumberOfTexts)/(8*sizeof(uint)) + 1];
+
+ 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;
+ ulong posOfSuccEndmarker = n-1;
DocId textId = numberOfTexts;
ulong ulongmax = 0;
ulongmax--;
uint alphabetrank_i_tmp =0;
- //positions:
- for (ulong i=n-1;i<ulongmax;i--) { // TODO bad solution with ulongmax?
- // i substitutes SA->GetPos(i)
+ TextStorageBuilder tsbuilder(n);
+ Tools::StartTimer();
+
+ for (ulong i=n-1;i<ulongmax;i--) {
+ // i substitutes SA->GetPos(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
+ uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
+ tsbuilder[i] = c;
+
+ if ((posOfSuccEndmarker - i) % samplerate == 0 && c != '\0')
+ {
+ set_field(sampledpositions,1,p,1);
+ (*positions)[sampleCount] = p;
sampleCount ++;
}
- uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
if (c == '\0')
{
--textId;
// Record the order of end-markers in BWT:
ulong endmarkerRank = alphabetrank_i_tmp - 1;
- (*endmarkerDocId)[endmarkerRank] = textId;
+ set_field(endmarkerDocId, logNumberOfTexts, 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;
+// (*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 (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);
+
+#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();
+
+#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));
+#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
+
+ x = n - 2;
+ posOfSuccEndmarker = n-1;
for(ulong i=0; i<sampleLength; i++) {
+ // Find next sampled text position
+ while ((posOfSuccEndmarker - x) % samplerate != 0)
+ {
+ --x;
+ if (tsbuilder[x] == '\0')
+ posOfSuccEndmarker = x--;
+ }
assert((*positions)[i] < n);
- ulong j = sampled->rank((*positions)[i]);
- if (j==0) j=sampleLength;
- TextPosition textPos = (*tmpSuffix)[i];
- (*suffixDocId)[j-1] = DocIdAtTextPos(textStartPos, textPos);
+ 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] = textStorage->DocIdAtTextPos(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]];
+ (*suffixes)[j-1] = textPos - textStorage->TextStartPos((*suffixDocId)[j-1]);
+ --x;
+ if (tsbuilder[x] == '\0')
+ posOfSuccEndmarker = x--;
}
- // FIXME Temp, remove
- delete tmpSuffix;
+
delete positions;
-// delete textLength;
- delete textStartPos;
+
+ /**
+ * Second pass: check tables
+ */
+/* p=bwtEndPos;
+ textId = numberOfTexts;
+ for (ulong i=n-1;i<ulongmax;i--) {
+ x=(i==n-1)?0:i+1;
+
+ if (sampled->access(p)) {
+ ulong j = sampled->rank1(p)-1;
+ assert((*suffixDocId)[j] == DocIdAtTextPos(textStartPos, x));
+
+ // calculate offset from text start:
+ assert((*suffixes)[j] == x - (*textStartPos)[(*suffixDocId)[j]]);
+ }
+
+ uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
+
+ 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;
+ }
+ assert(textId == 0);
+ delete textStartPos
+*/
+
+#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!
+
+#ifdef DEBUG_MEMUSAGE
+ std::cerr << "max heap usage after Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
+#endif
}
projects / SXSI / TextCollection.git / blobdiff