*****************************************************************************/
#include "TCImplementation.h"
-//#include "HeapProfiler.h" // FIXME remove
+#ifdef DEBUG_MEMUSAGE
+#include "HeapProfiler.h" // FIXME remove
+#endif
#include <iostream>
#include <map>
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);
}
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);
}
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);
}
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);
}
}
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);
}
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);
}
}
// Match including end-marker
Search(pattern, m+1, &sp, &ep);
- TextCollection::document_result result;
-
// Report end-markers in result interval
return EnumerateEndmarkers(sp, ep);
}
// 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);
}
// 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))
+ while (c != '\0' && !sampled->access(i))
{
i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping
c = alphabetrank->access(i);
}
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);
}
// 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))
+ while (c != '\0' && !sampled->access(i))
{
i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping
c = alphabetrank->access(i);
}
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);
TextPosition sp = 0, ep = 0;
SearchLessThan(pattern, m, &sp, &ep);
- TextCollection::document_result result;
-
// Report end-markers in result interval
return EnumerateEndmarkers(sp, ep);
}
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);
}
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);
}
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));
}
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);
}
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));
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);
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);
{
// 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
// 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()
// 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
// 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;i<n/W+1;i++)
- sampledpositions[i]=0lu;
+ 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;
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)
+ 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);
+ set_field(sampledpositions,1,p,1);
(*positions)[sampleCount] = p;
(*tmpSuffix)[sampleCount] = x; // FIXME remove
sampleCount ++;
// 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;
}
// 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
for(ulong i=0; i<sampleLength; i++) {
assert((*positions)[i] < n);
- ulong j = sampled->rank((*positions)[i]);
+ ulong j = sampled->rank1((*positions)[i]);
+
if (j==0) j=sampleLength;
TextPosition textPos = (*tmpSuffix)[i];
(*suffixDocId)[j-1] = DocIdAtTextPos(textStartPos, textPos);
// 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);*/
}
projects / SXSI / TextCollection.git / blobdiff