1 /******************************************************************************
2 * Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki *
4 * FMIndex implementation for the TextCollection interface *
6 * This program is free software; you can redistribute it and/or modify *
7 * it under the terms of the GNU Lesser General Public License as published *
8 * by the Free Software Foundation; either version 2 of the License, or *
9 * (at your option) any later version. *
11 * This program is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
14 * GNU Lesser General Public License for more details. *
16 * You should have received a copy of the GNU Lesser General Public License *
17 * along with this program; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *
20 *****************************************************************************/
23 //#define DEBUG_MEMUSAGE
25 #include "HeapProfiler.h" // FIXME remove
35 #include <cstring> // For strlen()
45 // Save file version info
46 const uchar FMIndex::versionFlag = 9;
49 * Constructor inits an empty dynamic FM-index.
50 * Samplerate defaults to TEXTCOLLECTION_DEFAULT_SAMPLERATE.
52 FMIndex::FMIndex(uchar * bwt, ulong length, unsigned samplerate_,
53 unsigned numberOfTexts_, ulong maxTextLength_, ulong numberOfSamples_,
54 CSA::DeltaVector & notIndexed, const string & niText, char tsType)
55 : n(length), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
56 suffixDocId(0), numberOfTexts(numberOfTexts_), maxTextLength(maxTextLength_), Doc(0)
58 makewavelet(bwt); // Deletes bwt!
61 CSA::DeltaVector::Iterator notIndexedIt(notIndexed);
63 // Make sampling tables
64 maketables(numberOfSamples_, tsType, notIndexedIt, niText);
67 bool FMIndex::EmptyText(DocId k) const
69 assert(k < (DocId)numberOfTexts);
70 return false; // Empty texts are not indexed
73 uchar * FMIndex::GetText(DocId k) const
75 assert(k < (DocId)numberOfTexts);
77 return textStorage->GetText(k);
78 /* TextPosition i = k;
81 // Reserve average string length to avoid reallocs
82 result.reserve(n/numberOfTexts);
84 uchar c = alphabetrank->access(i);
88 i = C[c]+alphabetrank->rank(c,i)-1;
90 c = alphabetrank->access(i); // "next" char.
93 // Convert to uchar (FIXME return string?)
95 uchar* res = new uchar[i+1];
97 for (ulong j = 0; j < i; ++j)
98 res[i-j-1] = result[j];
103 * Substring queries are supported via the pointer returned by TextStorage::GetText
104 uchar* FMIndex::GetText(DocId k, TextPosition i, TextPosition j) const
106 assert(k < (DocId)numberOfTexts);
107 assert(j < (*textLength)[k]);
112 // Start position of k'th text
113 ulong start = (*textStartPos)[k];
115 return Substring(i + start, j-i+1);
120 /******************************************************************
121 * Existential queries
123 bool FMIndex::IsPrefix(uchar const * pattern) const
125 TextPosition m = strlen((char *)pattern);
129 TextPosition sp = 0, ep = 0;
130 Search(pattern, m, &sp, &ep);
132 // Check for end-marker(s) in result interval
133 if (CountEndmarkers(sp, ep))
138 bool FMIndex::IsPrefix(uchar const * pattern, DocId begin, DocId end) const
140 TextPosition m = strlen((char *)pattern);
144 TextPosition sp = 0, ep = 0;
145 Search(pattern, m, &sp, &ep);
147 // Check for end-marker(s) in result interval
148 if (CountEndmarkers(sp, ep, begin, end))
154 bool FMIndex::IsSuffix(uchar const *pattern) const
156 // Here counting is as fast as IsSuffix():
157 if (CountSuffix(pattern) > 0)
162 bool FMIndex::IsSuffix(uchar const *pattern, DocId begin, DocId end) const
164 // Here counting is as fast as IsSuffix():
165 if (CountSuffix(pattern, begin, end) > 0)
170 bool FMIndex::IsEqual(uchar const *pattern) const
172 TextPosition m = std::strlen((char *)pattern);
174 return false; // No empty texts exists
176 TextPosition sp = 0, ep = 0;
177 // Match including end-marker
178 Search(pattern, m+1, &sp, &ep);
180 // Check for end-marker(s) in result interval
181 if (CountEndmarkers(sp, ep))
186 bool FMIndex::IsEqual(uchar const *pattern, DocId begin, DocId end) const
188 TextPosition m = std::strlen((char *)pattern);
190 return false; // No empty texts exists
192 TextPosition sp = 0, ep = 0;
193 // Match including end-marker
194 Search(pattern, m+1, &sp, &ep, begin, end);
196 // Check for end-marker(s) in result interval
197 if (CountEndmarkers(sp, ep))
202 bool FMIndex::IsContains(uchar const * pattern) const
204 TextPosition m = strlen((char *)pattern);
208 TextPosition sp = 0, ep = 0;
209 // Just check if pattern exists somewhere
210 ulong count = Search(pattern, m, &sp, &ep);
217 bool FMIndex::IsContains(uchar const * pattern, DocId begin, DocId end) const
219 // Here counting is as fast as existential querying
220 if (CountContains(pattern, begin, end) > 0)
221 return true; // FIXME No need to filter result set
225 bool FMIndex::IsLessThan(uchar const * pattern) const
227 if (CountLessThan(pattern) > 0)
232 bool FMIndex::IsLessThan(uchar const * pattern, DocId begin, DocId end) const
234 if (CountLessThan(pattern, begin, end) > 0)
239 /******************************************************************
242 ulong FMIndex::Count(uchar const * pattern) const
244 TextPosition m = strlen((char *)pattern);
248 TextPosition sp = 0, ep = 0;
249 unsigned count = (unsigned) Search(pattern, m, &sp, &ep);
253 unsigned FMIndex::CountPrefix(uchar const * pattern) const
255 TextPosition m = strlen((char *)pattern);
257 return numberOfTexts;
259 TextPosition sp = 0, ep = 0;
260 Search(pattern, m, &sp, &ep);
262 // Count end-markers in result interval
263 return CountEndmarkers(sp, ep);
266 unsigned FMIndex::CountPrefix(uchar const * pattern, DocId begin, DocId end) const
268 TextPosition m = strlen((char *)pattern);
270 return numberOfTexts;
272 TextPosition sp = 0, ep = 0;
273 Search(pattern, m, &sp, &ep);
275 // Count end-markers in result interval
276 return CountEndmarkers(sp, ep, begin, end);
279 unsigned FMIndex::CountSuffix(uchar const * pattern) const
281 TextPosition m = strlen((char *)pattern);
283 return numberOfTexts;
285 TextPosition sp = 0, ep = 0;
286 // Search with end-marker
287 unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep);
292 unsigned FMIndex::CountSuffix(uchar const * pattern, DocId begin, DocId end) const
294 TextPosition m = strlen((char *)pattern);
296 return numberOfTexts;
298 TextPosition sp = 0, ep = 0;
299 // Search with end-marker
300 unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep, begin, end);
305 unsigned FMIndex::CountEqual(uchar const *pattern) const
307 TextPosition m = strlen((char const *)pattern);
309 return 0; // No empty texts.
311 TextPosition sp = 0, ep = 0;
312 // Match including end-marker
313 Search(pattern, m+1, &sp, &ep);
315 // Count end-markers in result interval
316 return CountEndmarkers(sp, ep);
319 unsigned FMIndex::CountEqual(uchar const *pattern, DocId begin, DocId end) const
321 TextPosition m = strlen((char const *)pattern);
323 return 0; // No empty texts.
325 TextPosition sp = 0, ep = 0;
326 // Match including end-marker
327 Search(pattern, m+1, &sp, &ep, begin, end);
329 // Count end-markers in result interval
330 return CountEndmarkers(sp, ep); // Already within [begin, end]
333 unsigned FMIndex::CountContains(uchar const * pattern) const
335 TextPosition m = strlen((char const *)pattern);
337 return numberOfTexts; // Total number of texts.
339 // Here counting is as slow as fetching the result set
340 // because we have to filter out occ's that fall within same document.
341 TextCollection::document_result result = Contains(pattern);
342 return result.size();
345 unsigned FMIndex::CountContains(uchar const * pattern, DocId begin, DocId end) const
347 TextPosition m = strlen((char const *)pattern);
349 return numberOfTexts; // Total number of texts.
351 // Here counting is as slow as fetching the result set
352 // because we have to filter out occ's that fall within same document.
353 TextCollection::document_result result = Contains(pattern, begin, end);
354 return result.size();
357 // Less than or equal
358 unsigned FMIndex::CountLessThan(uchar const * pattern) const
360 TextPosition m = strlen((char const *)pattern);
362 return 0; // No empty texts.
364 TextPosition sp = 0, ep = 0;
365 SearchLessThan(pattern, m, &sp, &ep);
367 // Count end-markers in result interval
368 return CountEndmarkers(sp, ep);
371 unsigned FMIndex::CountLessThan(uchar const * pattern, DocId begin, DocId end) const
373 TextPosition m = strlen((char const *)pattern);
375 return 0; // No empty texts.
377 TextPosition sp = 0, ep = 0;
378 SearchLessThan(pattern, m, &sp, &ep);
380 // Count end-markers in result interval
381 return CountEndmarkers(sp, ep, begin, end);
385 * Document reporting queries
387 TextCollection::document_result FMIndex::Prefix(uchar const * pattern) const
389 TextPosition m = strlen((char *)pattern);
391 return TextCollection::document_result(); // FIXME Should return all 1...k
393 TextPosition sp = 0, ep = 0;
394 Search(pattern, m, &sp, &ep);
396 // Iterate through end-markers in [sp,ep]:
397 return EnumerateEndmarkers(sp, ep);
400 TextCollection::document_result FMIndex::Prefix(uchar const * pattern, DocId begin, DocId end) const
402 TextPosition m = strlen((char *)pattern);
404 return TextCollection::document_result(); // FIXME Should return all 1...k
406 TextPosition sp = 0, ep = 0;
407 Search(pattern, m, &sp, &ep);
409 // Return end-markers in [sp,ep] and [begin, end]:
410 return EnumerateEndmarkers(sp, ep, begin, end);
413 TextCollection::document_result FMIndex::Suffix(uchar const * pattern) const
415 TextPosition m = strlen((char *)pattern);
417 return TextCollection::document_result(); // FIXME Should return all 1...k
419 TextPosition sp = 0, ep = 0;
420 // Search with end-marker
421 Search(pattern, m+1, &sp, &ep);
423 TextCollection::document_result result;
424 result.reserve(ep-sp+1); // Try to avoid reallocation.
426 // Check each occurrence
427 for (; sp <= ep; ++sp)
431 uchar c = alphabetrank->access(i);
432 while (c != '\0' && !sampled->access(i))
434 i = C[c]+alphabetrank->rank(c,i)-1;
435 c = alphabetrank->access(i);
437 // Assert: c == '\0' OR sampled->IsBitSet(i)
441 // Rank among the end-markers in BWT
442 unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
443 result.push_back(Doc->access(endmarkerRank));
445 else // Sampled position
447 DocId docId = (*suffixDocId)[sampled->rank1(i)-1];
448 result.push_back(docId);
455 TextCollection::document_result FMIndex::Suffix(uchar const * pattern, DocId begin, DocId end) const
457 TextPosition m = strlen((char *)pattern);
459 return TextCollection::document_result(); // FIXME Should return all 1...k
461 TextPosition sp = 0, ep = 0;
462 // Search with end-marker
463 Search(pattern, m+1, &sp, &ep, begin, end);
465 TextCollection::document_result result;
466 result.reserve(ep-sp+1); // Try to avoid reallocation.
468 // Check each occurrence, already within [begin, end]
469 for (; sp <= ep; ++sp)
473 uchar c = alphabetrank->access(i);
474 while (c != '\0' && !sampled->access(i))
476 i = C[c]+alphabetrank->rank(c,i)-1;
477 c = alphabetrank->access(i);
479 // Assert: c == '\0' OR sampled->IsBitSet(i)
483 // Rank among the end-markers in BWT
484 unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
485 result.push_back(Doc->access(endmarkerRank));
487 else // Sampled position
489 DocId docId = (*suffixDocId)[sampled->rank1(i)-1];
490 result.push_back(docId);
498 TextCollection::document_result FMIndex::Equal(uchar const *pattern) const
500 TextPosition m = strlen((char const *)pattern);
502 return TextCollection::document_result(); // FIXME Should return all empty texts
504 TextPosition sp = 0, ep = 0;
505 // Match including end-marker
506 Search(pattern, m+1, &sp, &ep);
508 // Report end-markers in result interval
509 return EnumerateEndmarkers(sp, ep);
512 TextCollection::document_result FMIndex::Equal(uchar const *pattern, DocId begin, DocId end) const
514 TextPosition m = strlen((char const *)pattern);
516 return TextCollection::document_result(); // FIXME Should return all empty texts
518 TextPosition sp = 0, ep = 0;
519 // Match including end-marker
520 Search(pattern, m+1, &sp, &ep, begin, end);
522 // Report end-markers in result interval
523 return EnumerateEndmarkers(sp, ep, begin, end);
527 TextCollection::document_result FMIndex::Contains(uchar const * pattern) const
529 TextPosition m = strlen((char *)pattern);
531 return TextCollection::document_result();
533 TextPosition sp = 0, ep = 0;
534 // Search all occurrences
535 Search(pattern, m, &sp, &ep);
537 // We want unique document indentifiers, using std::set to collect them
538 std::set<DocId> resultSet;
539 EnumerateDocuments(resultSet, sp, ep);
541 // Convert std::set to std::vector
542 TextCollection::document_result result(resultSet.begin(), resultSet.end());
546 TextCollection::document_result FMIndex::Contains(uchar const * pattern, DocId begin, DocId end) const
548 TextPosition m = strlen((char *)pattern);
550 return TextCollection::document_result();
552 TextPosition sp = 0, ep = 0;
553 // Search all occurrences
554 Search(pattern, m, &sp, &ep);
556 // We want unique document indentifiers, using std::set to collect them
557 std::set<DocId> resultSet;
558 EnumerateDocuments(resultSet, sp, ep, begin, end);
560 // Convert std::set to std::vector
561 TextCollection::document_result result(resultSet.begin(), resultSet.end());
568 * * FIXME Lessthan or equal
570 TextCollection::document_result FMIndex::LessThan(uchar const * pattern) const
572 TextPosition m = strlen((char *)pattern);
574 return TextCollection::document_result(); // empty result set
576 TextPosition sp = 0, ep = 0;
577 SearchLessThan(pattern, m, &sp, &ep);
579 // Report end-markers in result interval
580 return EnumerateEndmarkers(sp, ep);
583 TextCollection::document_result FMIndex::LessThan(uchar const * pattern, DocId begin, DocId end) const
585 TextPosition m = strlen((char *)pattern);
587 return TextCollection::document_result(); // empty result set
589 TextPosition sp = 0, ep = 0;
590 SearchLessThan(pattern, m, &sp, &ep);
592 // Iterate through end-markers in [sp,ep] and [begin, end]:
593 return EnumerateEndmarkers(sp, ep, begin, end);
597 TextCollection::document_result FMIndex::KMismaches(uchar const * pattern, unsigned k) const
599 TextPosition m = strlen((char *)pattern);
601 return TextCollection::document_result(); // empty result set
603 suffix_range_vector ranges;
604 kmismatches(ranges, pattern, 0, n-1, m, k);
605 std::set<DocId> resultSet;
607 for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
608 // Iterate through docs in [sp,ep]:
609 EnumerateDocuments(resultSet, (*it).first, (*it).second);
611 // Convert std::set to std::vector
612 TextCollection::document_result result(resultSet.begin(), resultSet.end());
616 TextCollection::document_result FMIndex::KErrors(uchar const * pattern, unsigned k) const
618 TextPosition m = strlen((char *)pattern);
620 return TextCollection::document_result(); // empty result set
622 suffix_range_vector ranges;
623 ulong *dd = new ulong[m+1];
624 for (ulong i=0;i<m+1;i++)
626 kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
629 std::set<DocId> resultSet;
630 for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
631 // Iterate through docs in [sp,ep]:
632 EnumerateDocuments(resultSet, (*it).first, (*it).second);
634 // Convert std::set to std::vector
635 TextCollection::document_result result(resultSet.begin(), resultSet.end());
641 * Full result set queries
643 TextCollection::full_result FMIndex::FullContains(uchar const * pattern) const
645 TextPosition m = strlen((char *)pattern);
647 return full_result(); // FIXME Throw exception?
649 TextPosition sp = 0, ep = 0;
650 // Search all occurrences
651 Search(pattern, m, &sp, &ep);
654 result.reserve(ep-sp+1); // Try to avoid reallocation.
655 EnumeratePositions(result, sp, ep);
660 TextCollection::full_result FMIndex::FullContains(uchar const * pattern, DocId begin, DocId end) const
662 TextPosition m = strlen((char *)pattern);
664 return full_result(); // FIXME Throw exception?
666 TextPosition sp = 0, ep = 0;
667 // Search all occurrences
668 Search(pattern, m, &sp, &ep);
671 result.reserve(ep-sp+1); // Try to avoid reallocation.
672 EnumeratePositions(result, sp, ep, begin, end);
677 TextCollection::full_result FMIndex::FullKMismatches(uchar const * pattern, unsigned k) const
679 TextPosition m = strlen((char *)pattern);
681 return TextCollection::full_result(); // empty result set
683 suffix_range_vector ranges;
684 ulong count = kmismatches(ranges, pattern, 0, n-1, m, k);
686 TextCollection::full_result result;
687 result.reserve(count); // avoid reallocation.
688 for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
689 // Iterate through docs in [sp,ep]:
690 EnumeratePositions(result, (*it).first, (*it).second);
694 TextCollection::full_result FMIndex::FullKErrors(uchar const * pattern, unsigned k) const
696 TextPosition m = strlen((char *)pattern);
698 return TextCollection::full_result(); // empty result set
700 suffix_range_vector ranges;
701 ulong *dd = new ulong[m+1];
702 for (unsigned i=0;i<m+1;i++)
704 ulong count = kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
707 TextCollection::full_result result;
708 result.reserve(count); // avoid reallocation.
709 for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
710 // Iterate through docs in [sp,ep]:
711 EnumeratePositions(result, (*it).first, (*it).second);
717 * Save index to a file handle
719 * Throws a std::runtime_error exception on i/o error.
720 * First byte that is saved represents the version number of the save file.
721 * In this version files, the data fields are:
727 TextPosition bwtEndPos;
728 static_sequence * alphabetrank;
730 BlockArray *suffixes;
731 BlockArray *suffixDocId;
732 unsigned numberOfTexts;
734 static_sequence *docId;
736 * The second parameter (filename's prefix) is ignored.
738 void FMIndex::Save(FILE *file, char const *ignored) const
740 const char type = 'F';
742 if (std::fwrite(&type, 1, 1, file) != 1)
743 throw std::runtime_error("FMIndex::Save(): file write error (type flag).");
745 // Saving version info:
746 if (std::fwrite(&versionFlag, 1, 1, file) != 1)
747 throw std::runtime_error("FMIndex::Save(): file write error (version flag).");
749 if (std::fwrite(&(this->n), sizeof(TextPosition), 1, file) != 1)
750 throw std::runtime_error("FMIndex::Save(): file write error (n).");
751 if (std::fwrite(&(this->samplerate), sizeof(unsigned), 1, file) != 1)
752 throw std::runtime_error("FMIndex::Save(): file write error (samplerate).");
754 for(ulong i = 0; i < 256; ++i)
755 if (std::fwrite(this->C + i, sizeof(unsigned), 1, file) != 1)
756 throw std::runtime_error("FMIndex::Save(): file write error (C table).");
758 if (std::fwrite(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
759 throw std::runtime_error("FMIndex::Save(): file write error (bwt end position).");
761 alphabetrank->save(file);
763 suffixes->Save(file);
764 suffixDocId->Save(file);
766 if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
767 throw std::runtime_error("FMIndex::Save(): file write error (numberOfTexts).");
768 if (std::fwrite(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
769 throw std::runtime_error("FMIndex::Save(): file write error (maxTextLength).");
772 textStorage->Save(file);
778 * Load index from a file handle
780 * Throws a std::runtime_error exception on i/o error.
781 * For more info, see FMIndex::Save().
783 * index_mode_t is defined in TextCollection.h and
784 * defaults to both the index and "naive" text.
786 * Note: Samplerate can not be changed during load.
788 FMIndex::FMIndex(FILE *file, index_mode_t im, unsigned samplerate_)
789 : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
790 suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0)
792 // NB: Type byte has already been read from input
795 if (std::fread(&verFlag, 1, 1, file) != 1)
796 throw std::runtime_error("FMIndex::Load(): file read error (version flag).");
797 if (verFlag != FMIndex::versionFlag)
798 throw std::runtime_error("FMIndex::Load(): invalid save file version.");
800 if (std::fread(&(this->n), sizeof(TextPosition), 1, file) != 1)
801 throw std::runtime_error("FMIndex::Load(): file read error (n).");
802 if (std::fread(&samplerate, sizeof(unsigned), 1, file) != 1)
803 throw std::runtime_error("FMIndex::Load(): file read error (samplerate).");
804 // FIXME samplerate can not be changed during load.
805 // if (this->samplerate == 0)
806 // this->samplerate = samplerate;
808 for(ulong i = 0; i < 256; ++i)
809 if (std::fread(this->C + i, sizeof(unsigned), 1, file) != 1)
810 throw std::runtime_error("FMIndex::Load(): file read error (C table).");
812 if (std::fread(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
813 throw std::runtime_error("FMIndex::Load(): file read error (bwt end position).");
815 alphabetrank = static_sequence::load(file);
816 if (im == index_mode_text_only) { delete alphabetrank; alphabetrank = 0; }
818 sampled = static_bitsequence::load(file);
819 if (im == index_mode_text_only) { delete sampled; sampled = 0; }
820 suffixes = new BlockArray(file);
821 if (im == index_mode_text_only) { delete suffixes; suffixes = 0; }
822 suffixDocId = new BlockArray(file);
823 if (im == index_mode_text_only) { delete suffixDocId; suffixDocId = 0; }
825 if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
826 throw std::runtime_error("FMIndex::Load(): file read error (numberOfTexts).");
827 if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
828 throw std::runtime_error("FMIndex::Load(): file read error (maxTextLength).");
830 Doc = new ArrayDoc(file); //static_sequence::load(file);
831 if (im == index_mode_text_only) { delete Doc; Doc = 0; }
833 textStorage = TextStorage::Load(file);
835 // FIXME Construct data structures with new samplerate
842 * Rest of the functions follow...
844 ulong FMIndex::searchPrefix(uchar const *pattern, ulong i, ulong *sp, ulong *ep) const
847 while (*sp<=*ep && i>=1)
849 c = (int)pattern[--i];
850 *sp = C[c]+alphabetrank->rank(c,*sp-1);
851 *ep = C[c]+alphabetrank->rank(c,*ep)-1;
854 return *ep - *sp + 1;
860 ulong FMIndex::kmismatches(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k) const
865 result.push_back(std::make_pair(sp,ep));
875 sum = searchPrefix(pattern, j, &sp, &ep);
877 result.push_back(std::make_pair(sp, ep));
880 vector<int> chars = alphabetrank->accessAll(sp, ep);
881 for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
884 continue; // skip '\0'
886 spnew = C[c]+alphabetrank->rank(c,sp-1);
887 epnew = C[c]+alphabetrank->rank(c,ep)-1;
888 if (c!=pattern[j-1]) knew = (int)k-1; else knew = k;
889 if (knew>=0) sum += kmismatches(result, pattern, spnew, epnew, j-1, knew);
894 //first call kerrors(pattern,1,n,m+k,k,d,m), where d[i]=i
895 ulong FMIndex::kerrors(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k, ulong const *d, ulong m) const
898 if (d[m]<=k) // range of suffixes with at most k-errors found
901 result.push_back(std::make_pair(sp, ep));
902 sum += (sp<=ep)?ep-sp+1:0ul;
906 ulong *dnew = new ulong[m+1];
911 vector<int> chars = alphabetrank->accessAll(sp, ep);
912 for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
915 continue; // skip '\0'
917 spnew = C[c]+alphabetrank->rank(c,sp-1);
918 epnew = C[c]+alphabetrank->rank(c,ep)-1;
919 if (spnew>epnew) continue;
922 for (p=1; p<=m; p++) {
923 dnew[p]=myminofthree(d[p]+1,dnew[p-1]+1,(c==pattern[m-p])?d[p-1]:(d[p-1]+1));
924 if (dnew[p]<lowerbound)
925 lowerbound = dnew[p];
928 sum += kerrors(result, pattern, spnew, epnew, j-1, k,dnew,m);
935 ulong FMIndex::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
937 // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
938 int c = (int)pattern[m-1];
940 TextPosition sp = C[c];
941 TextPosition ep = C[c+1]-1;
942 while (sp<=ep && i>=1)
944 // printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
945 c = (int)pattern[--i];
946 sp = C[c]+alphabetrank->rank(c,sp-1);
947 ep = C[c]+alphabetrank->rank(c,ep)-1;
957 ulong FMIndex::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult, DocId begin, DocId end) const
959 // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
960 int c = (int)pattern[m-1];
961 assert(c == 0); // Start from endmarkers
963 TextPosition sp = begin;
964 TextPosition ep = end;
965 while (sp<=ep && i>=1)
967 // printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
968 c = (int)pattern[--i];
969 sp = C[c]+alphabetrank->rank(c,sp-1);
970 ep = C[c]+alphabetrank->rank(c,ep)-1;
981 ulong FMIndex::SearchLessThan(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
983 // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
984 uint c = (int)pattern[m-1];
987 TextPosition ep = C[c+1]-1;
988 while (sp<=ep && i>=1)
990 // printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
991 c = (int)pattern[--i];
992 uint result = alphabetrank->rankLessThan(c,ep);
1007 FMIndex::~FMIndex() {
1008 delete alphabetrank;
1016 void FMIndex::makewavelet(uchar *bwt)
1025 if (C[i]>0) {min = i; break;}
1026 for (i=255;i>=min;--i)
1027 if (C[i]>0) {max = i; break;}
1029 ulong prev=C[0], temp;
1031 for (i=1;i<256;i++) {
1036 // this->codetable = node::makecodetable(bwt,n);
1037 // alphabetrank = new THuffAlphabetRank(bwt,n, this->codetable,0);
1039 //alphabetrank = new RLWaveletTree(bwt, n); // Deletes bwt!
1040 // std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1042 #ifdef DEBUG_MEMUSAGE
1043 std::cerr << "max heap usage before WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1044 HeapProfiler::ResetMaxHeapConsumption();
1047 alphabet_mapper * am = new alphabet_mapper_none();
1048 static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(8); //rrr02(8); // FIXME samplerate?
1049 wt_coder * wtc = new wt_coder_huff(bwt,n,am);//binary(bwt,n,am); // FIXME Huffman shape
1050 alphabetrank = new static_sequence_wvtree(bwt,n,wtc,bmb,am);
1052 bwt = 0; // already deleted
1054 #ifdef DEBUG_MEMUSAGE
1055 std::cerr << "heap usage after WT: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1056 std::cerr << "max heap usage after WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1060 void FMIndex::maketables(ulong sampleLength, char tsType, CSA::DeltaVector::Iterator & notIndexedIt, const string & niText)
1062 // Calculate BWT end-marker position (of last inserted text)
1065 uint alphabetrank_i_tmp = 0;
1066 uchar c = alphabetrank->access(i, alphabetrank_i_tmp);
1069 i = C[c]+alphabetrank_i_tmp-1;
1070 c = alphabetrank->access(i, alphabetrank_i_tmp);
1073 this->bwtEndPos = i;
1076 #ifdef DEBUG_MEMUSAGE
1077 std::cerr << "heap usage before BWT traverse: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
1078 HeapProfiler::ResetMaxHeapConsumption();
1081 // Build up array for text starting positions
1082 // BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n));
1083 // (*textStartPos)[0] = 0;
1085 // Mapping from end-markers to doc ID's:
1086 unsigned logNumberOfTexts = Tools::CeilLog2(numberOfTexts);
1087 // uint *endmarkerDocId = new uint[(numberOfTexts * logNumberOfTexts)/(8*sizeof(uint)) + 1];
1088 BlockArray *endmarkerDocId = new BlockArray(numberOfTexts, logNumberOfTexts);
1090 BlockArray* positions = new BlockArray(sampleLength, Tools::CeilLog2(this->n));
1091 uint *sampledpositions = new uint[n/(sizeof(uint)*8)+1];
1092 for (ulong i = 0; i < n / (sizeof(uint)*8) + 1; i++)
1093 sampledpositions[i] = 0;
1095 ulong x,p=bwtEndPos;
1096 ulong sampleCount = 0;
1097 // Keeping track of text position of prev. end-marker seen
1098 ulong posOfSuccEndmarker = n-1;
1099 DocId textId = numberOfTexts;
1102 uint alphabetrank_i_tmp =0;
1104 // Text length = n + number of bytes not indexed.
1105 TextStorageBuilder tsbuilder(n + niText.length());
1106 ulong tsb_i = n + niText.length(); // Iterator from text length to 0.
1107 string::const_reverse_iterator nit_i = niText.rbegin(); // Iterator through non-indexed texts
1109 for (ulong i=n-1;i<ulongmax;i--) {
1110 // i substitutes SA->GetPos(i)
1113 uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
1115 tsbuilder[--tsb_i] = c; // Build TextStorage
1117 if ((posOfSuccEndmarker - i) % samplerate == 0 && c != '\0')
1119 set_field(sampledpositions,1,p,1);
1120 (*positions)[sampleCount] = p;
1126 unsigned prevTextId = textId; // Cache textId value.
1129 * At first c == '\0' it holds that (prevTextId == numberOfTexts), thus,
1130 * we have to search for the first text that is actually *indexed*
1131 * to get correct prevTextId.
1133 if (prevTextId == numberOfTexts)
1136 while (notIndexedIt.isSet(prevTextId))
1138 // Now prevTextId points to the first indexed Doc ID.
1142 * Insert non-indexed texts
1144 while (notIndexedIt.isSet(textId))
1147 tsbuilder[tsb_i] = *nit_i;
1150 } while (nit_i != niText.rend() && *nit_i != '\0');
1152 tsbuilder[tsb_i] = '\0';
1159 // Record the order of end-markers in BWT:
1160 ulong endmarkerRank = alphabetrank_i_tmp - 1;
1161 //set_field(endmarkerDocId, logNumberOfTexts, endmarkerRank, (textId + 1) % numberOfTexts);
1162 (*endmarkerDocId)[endmarkerRank] = prevTextId % numberOfTexts;
1164 // Store text length and text start position:
1165 if (textId < (DocId)numberOfTexts - 1)
1167 // (*textStartPos)[textId + 1] = x; // x-1 is text position of end-marker.
1169 posOfSuccEndmarker = i;
1172 // LF-mapping from '\0' does not work with this (pseudo) BWT.
1173 // Correct LF-mapping to the last char of the previous text:
1174 p = textId - notIndexedIt.rank(textId);
1176 else // Now c != '\0', do LF-mapping:
1177 p = C[c]+alphabetrank_i_tmp-1;
1179 while (textId > 0 && notIndexedIt.isSet(textId-1))
1183 tsbuilder[tsb_i] = *nit_i;
1185 } while (nit_i != niText.rend() && *nit_i != '\0');
1188 assert(textId == 0);
1190 assert(nit_i == niText.rend());
1192 #ifdef DEBUG_MEMUSAGE
1193 std::cerr << "heap usage before tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
1194 HeapProfiler::ResetMaxHeapConsumption();
1197 textStorage = tsbuilder.InitTextStorage(tsType);
1199 #ifdef DEBUG_MEMUSAGE
1200 std::cerr << "heap usage after tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
1201 HeapProfiler::ResetMaxHeapConsumption();
1204 sampled = new static_bitsequence_rrr02(sampledpositions, n, 16);
1205 delete [] sampledpositions;
1206 assert(sampleCount == sampleLength);
1207 assert(sampled->rank1(n-1) == sampleLength);
1209 #ifdef DEBUG_MEMUSAGE
1210 std::cerr << "heap usage after sampled bit vector: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
1211 HeapProfiler::ResetMaxHeapConsumption();
1214 // Suffixes store an offset from the text start position
1215 suffixes = new BlockArray(sampleLength, Tools::CeilLog2(maxTextLength));
1216 suffixDocId = new BlockArray(sampleLength, Tools::CeilLog2(numberOfTexts));
1218 x = n + niText.length() - 2;
1219 textId = numberOfTexts - 1;
1220 posOfSuccEndmarker = x + 1;
1221 for(ulong i = 0; i < sampleLength; i ++) {
1222 // Find next sampled text position
1223 while ((posOfSuccEndmarker - x) % samplerate != 0
1224 || notIndexedIt.isSet(textId)) // Loop over non-indexed
1228 if (textStorage->IsEndmarker(x))
1230 posOfSuccEndmarker = x--;
1234 assert((*positions)[i] < n);
1235 ulong j = sampled->rank1((*positions)[i]);
1237 assert(j != 0); // if (j==0) j=sampleLength;
1239 TextPosition textPos = (x==n-1)?0:x+1;
1240 (*suffixDocId)[j-1] = textId; // textStorage->DocIdAtTextPos(textPos);
1241 assert(textStorage->DocIdAtTextPos(textPos) == textId);
1243 assert((*suffixDocId)[j-1] < numberOfTexts);
1244 // calculate offset from text start:
1245 (*suffixes)[j-1] = textPos - textStorage->TextStartPos((*suffixDocId)[j-1]);
1247 if (x != ~0lu && textStorage->IsEndmarker(x))
1249 posOfSuccEndmarker = x--;
1256 #ifdef DEBUG_MEMUSAGE
1257 std::cerr << "heap usage after sampled arrays: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
1258 HeapProfiler::ResetMaxHeapConsumption();
1261 #ifdef DEBUG_MEMUSAGE
1262 std::cerr << "max heap usage before Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1263 HeapProfiler::ResetMaxHeapConsumption();
1266 /*alphabet_mapper * am = new alphabet_mapper_none();
1267 static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(32); // FIXME samplerate?
1268 Doc = new static_sequence_wvtree_noptrs(endmarkerDocId, numberOfTexts, logNumberOfTexts, bmb, am, true);
1270 // delete [] endmarkerDocId; // already deleted in static_sequence_wvtree_noptrs!
1272 Doc = new ArrayDoc(endmarkerDocId);
1274 #ifdef DEBUG_MEMUSAGE
1275 std::cerr << "max heap usage after Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1281 * Finds document identifier for given text position
1283 * Starting text position of the document is stored into second parameter.
1284 * Binary searching on text starting positions.
1286 TextCollection::DocId FMIndex::DocIdAtTextPos(BlockArray* textStartPos, TextPosition i) const
1291 DocId b = numberOfTexts - 1;
1294 DocId c = a + (b - a)/2;
1295 if ((*textStartPos)[c] > i)
1297 else if ((*textStartPos)[c+1] > i)
1303 assert(a < (DocId)numberOfTexts);
1304 assert(i >= (*textStartPos)[a]);
1305 assert(i < (a == (DocId)numberOfTexts - 1 ? n : (*textStartPos)[a+1]));