X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=TCImplementation.cpp;h=09f6d248363623c6e0dfd6d2e3e24912e812dbfc;hb=6048d243439020acd3b5acf8654641cb9cef8e27;hp=2aec680c310b78138bac05cec0ece9b72c31ddab;hpb=e59bd57d53c2d9e5db4c22f2501a9789f62f46c1;p=SXSI%2FTextCollection.git diff --git a/TCImplementation.cpp b/TCImplementation.cpp index 2aec680..09f6d24 100644 --- a/TCImplementation.cpp +++ b/TCImplementation.cpp @@ -41,22 +41,22 @@ namespace SXSI { // Save file version info -const uchar TCImplementation::versionFlag = 6; +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_) + unsigned numberOfTexts_, ulong maxTextLength_, ulong numberOfSamples_, 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_); + maketables(numberOfSamples_, tsType); } bool TCImplementation::EmptyText(DocId k) const @@ -554,6 +554,11 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern return result; } + +/** + *** +* * FIXME Lessthan or equal + */ TextCollection::document_result TCImplementation::LessThan(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); @@ -581,7 +586,7 @@ TextCollection::document_result TCImplementation::LessThan(uchar const * pattern } -TextCollection::document_result TCImplementation::Kmismaches(uchar const * pattern, unsigned k) const +TextCollection::document_result TCImplementation::KMismaches(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -600,7 +605,7 @@ TextCollection::document_result TCImplementation::Kmismaches(uchar const * patte return result; } -TextCollection::document_result TCImplementation::Kerrors(uchar const * pattern, unsigned k) const +TextCollection::document_result TCImplementation::KErrors(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -661,7 +666,7 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern return result; } -TextCollection::full_result TCImplementation::FullKmismatches(uchar const * pattern, unsigned k) const +TextCollection::full_result TCImplementation::FullKMismatches(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -678,7 +683,7 @@ TextCollection::full_result TCImplementation::FullKmismatches(uchar const * patt return result; } -TextCollection::full_result TCImplementation::FullKerrors(uchar const * pattern, unsigned k) const +TextCollection::full_result TCImplementation::FullKErrors(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -763,6 +768,9 @@ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0), suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0) { +// Tools::StartTimer(); +// std::cout << std::endl << "Loading..."<< std::endl; + uchar verFlag = 0; if (std::fread(&verFlag, 1, 1, file) != 1) throw std::runtime_error("TCImplementation::Load(): file read error (version flag)."); @@ -784,7 +792,9 @@ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) if (std::fread(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1) throw std::runtime_error("TCImplementation::Load(): file read error (bwt end position)."); +// std::cout << "Loading alphabet rank (" << Tools::GetTime() << " s)." << std::endl; alphabetrank = static_sequence::load(file); +// std::cout << "Loading samples (" << Tools::GetTime() << " s)." << std::endl; sampled = static_bitsequence::load(file); suffixes = new BlockArray(file); suffixDocId = new BlockArray(file); @@ -794,8 +804,12 @@ TCImplementation::TCImplementation(FILE *file, unsigned samplerate_) if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1) throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength)."); - Doc = static_sequence::load(file); - textStorage = new TextStorage(file); +// std::cout << "Loading Doc (" << Tools::GetTime() << " s)." << std::endl; + Doc = new ArrayDoc(file); //static_sequence::load(file); +// std::cout << "Loading text storage (" << Tools::GetTime() << " s)." << std::endl; + textStorage = TextStorage::Load(file); + +// std::cout << "Loading done(" << Tools::GetTime() << " s)." << std::endl; // FIXME Construct data structures with new samplerate //maketables(); @@ -859,20 +873,20 @@ ulong TCImplementation::kmismatches(suffix_range_vector &result, uchar const *pa //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)); - return (sp<=ep)?ep-sp+1:0ul; + sum += (sp<=ep)?ep-sp+1:0ul; } if (sp>ep || j==0) - return 0; + return sum; 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) { @@ -1010,8 +1024,8 @@ void TCImplementation::makewavelet(uchar *bwt) #endif alphabet_mapper * am = new alphabet_mapper_none(); - static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(8); // FIXME samplerate? - wt_coder * wtc = new wt_coder_binary(bwt,n,am); + 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 @@ -1022,7 +1036,7 @@ void TCImplementation::makewavelet(uchar *bwt) #endif } -void TCImplementation::maketables(ulong sampleLength) +void TCImplementation::maketables(ulong sampleLength, char tsType) { // Calculate BWT end-marker position (of last inserted text) { @@ -1049,7 +1063,8 @@ void TCImplementation::maketables(ulong sampleLength) // Mapping from end-markers to doc ID's: unsigned logNumberOfTexts = Tools::CeilLog2(numberOfTexts); - uint *endmarkerDocId = new uint[(numberOfTexts * logNumberOfTexts)/(8*sizeof(uint)) + 1]; +// 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]; @@ -1088,7 +1103,8 @@ void TCImplementation::maketables(ulong sampleLength) // Record the order of end-markers in BWT: ulong endmarkerRank = alphabetrank_i_tmp - 1; - set_field(endmarkerDocId, logNumberOfTexts, endmarkerRank, (textId + 1) % numberOfTexts); + //set_field(endmarkerDocId, logNumberOfTexts, endmarkerRank, (textId + 1) % numberOfTexts); + (*endmarkerDocId)[endmarkerRank] = (textId + 1) % numberOfTexts; // Store text length and text start position: if (textId < (DocId)numberOfTexts - 1) @@ -1110,7 +1126,7 @@ void TCImplementation::maketables(ulong sampleLength) HeapProfiler::ResetMaxHeapConsumption(); #endif - textStorage = tsbuilder.InitTextStorage(); + 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; @@ -1131,11 +1147,6 @@ void TCImplementation::maketables(ulong sampleLength) 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; iIsEndmarker(x)) posOfSuccEndmarker = x--; } assert((*positions)[i] < n); @@ -1158,12 +1170,17 @@ void TCImplementation::maketables(ulong sampleLength) // calculate offset from text start: (*suffixes)[j-1] = textPos - textStorage->TextStartPos((*suffixDocId)[j-1]); --x; - if (tsbuilder[x] == '\0') + if (x != ~0lu && textStorage->IsEndmarker(x)) posOfSuccEndmarker = x--; } 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 + /** * Second pass: check tables */ @@ -1200,12 +1217,14 @@ void TCImplementation::maketables(ulong sampleLength) HeapProfiler::ResetMaxHeapConsumption(); #endif - alphabet_mapper * am = new alphabet_mapper_none(); + /*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 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