From 89dc22aee980ba16f757cd9a7f77478c2da50051 Mon Sep 17 00:00:00 2001 From: nvalimak Date: Wed, 27 Oct 2010 13:36:59 +0000 Subject: [PATCH] Added SWCSA git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/TextCollection@925 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- TCImplementation.cpp => FMIndex.cpp | 160 +++++++------ TCImplementation.h => FMIndex.h | 19 +- FMIndexBuilder.cpp | 146 ++++++++++++ FMIndexBuilder.h | 85 +++++++ SWCSABuilder.h | 118 ++++++++++ SWCSAWrapper.h | 352 ++++++++++++++++++++++++++++ TextCollection.cpp | 22 +- TextCollection.h | 12 +- TextCollectionBuilder.cpp | 152 ++---------- TextCollectionBuilder.h | 43 ++-- TextStorage.h | 9 + dependencies.mk | 69 +++--- incbwt/dependencies.mk | 33 ++- makefile | 2 +- testTextCollection.cpp | 2 +- 15 files changed, 927 insertions(+), 297 deletions(-) rename TCImplementation.cpp => FMIndex.cpp (85%) rename TCImplementation.h => FMIndex.h (97%) create mode 100644 FMIndexBuilder.cpp create mode 100644 FMIndexBuilder.h create mode 100644 SWCSABuilder.h create mode 100644 SWCSAWrapper.h diff --git a/TCImplementation.cpp b/FMIndex.cpp similarity index 85% rename from TCImplementation.cpp rename to FMIndex.cpp index 1a29f25..297604b 100644 --- a/TCImplementation.cpp +++ b/FMIndex.cpp @@ -1,6 +1,7 @@ /****************************************************************************** * Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki * * * + * FMIndex implementation for the TextCollection interface * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU Lesser General Public License as published * @@ -17,7 +18,7 @@ * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * *****************************************************************************/ -#include "TCImplementation.h" +#include "FMIndex.h" //#define DEBUG_MEMUSAGE #ifdef DEBUG_MEMUSAGE @@ -37,17 +38,18 @@ using std::pair; using std::make_pair; using std::map; using std::string; + namespace SXSI { // Save file version info -const uchar TCImplementation::versionFlag = 8; +const uchar FMIndex::versionFlag = 9; /** * Constructor inits an empty dynamic FM-index. * Samplerate defaults to TEXTCOLLECTION_DEFAULT_SAMPLERATE. */ -TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerate_, +FMIndex::FMIndex(uchar * bwt, ulong length, unsigned samplerate_, unsigned numberOfTexts_, ulong maxTextLength_, ulong numberOfSamples_, CSA::DeltaVector & notIndexed, const string & niText, char tsType) : n(length), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0), @@ -60,13 +62,13 @@ TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerat maketables(numberOfSamples_, tsType, notIndexed, niText); } -bool TCImplementation::EmptyText(DocId k) const +bool FMIndex::EmptyText(DocId k) const { assert(k < (DocId)numberOfTexts); return false; // Empty texts are not indexed } -uchar * TCImplementation::GetText(DocId k) const +uchar * FMIndex::GetText(DocId k) const { assert(k < (DocId)numberOfTexts); @@ -97,7 +99,7 @@ uchar * TCImplementation::GetText(DocId k) const /* * Substring queries are supported via the pointer returned by TextStorage::GetText -uchar* TCImplementation::GetText(DocId k, TextPosition i, TextPosition j) const +uchar* FMIndex::GetText(DocId k, TextPosition i, TextPosition j) const { assert(k < (DocId)numberOfTexts); assert(j < (*textLength)[k]); @@ -116,7 +118,7 @@ uchar* TCImplementation::GetText(DocId k, TextPosition i, TextPosition j) const /****************************************************************** * Existential queries */ -bool TCImplementation::IsPrefix(uchar const * pattern) const +bool FMIndex::IsPrefix(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -131,7 +133,7 @@ bool TCImplementation::IsPrefix(uchar const * pattern) const return false; } -bool TCImplementation::IsPrefix(uchar const * pattern, DocId begin, DocId end) const +bool FMIndex::IsPrefix(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -147,7 +149,7 @@ bool TCImplementation::IsPrefix(uchar const * pattern, DocId begin, DocId end) c } -bool TCImplementation::IsSuffix(uchar const *pattern) const +bool FMIndex::IsSuffix(uchar const *pattern) const { // Here counting is as fast as IsSuffix(): if (CountSuffix(pattern) > 0) @@ -155,7 +157,7 @@ bool TCImplementation::IsSuffix(uchar const *pattern) const return false; } -bool TCImplementation::IsSuffix(uchar const *pattern, DocId begin, DocId end) const +bool FMIndex::IsSuffix(uchar const *pattern, DocId begin, DocId end) const { // Here counting is as fast as IsSuffix(): if (CountSuffix(pattern, begin, end) > 0) @@ -163,7 +165,7 @@ bool TCImplementation::IsSuffix(uchar const *pattern, DocId begin, DocId end) co return false; } -bool TCImplementation::IsEqual(uchar const *pattern) const +bool FMIndex::IsEqual(uchar const *pattern) const { TextPosition m = std::strlen((char *)pattern); if (m == 0) @@ -179,7 +181,7 @@ bool TCImplementation::IsEqual(uchar const *pattern) const return false; } -bool TCImplementation::IsEqual(uchar const *pattern, DocId begin, DocId end) const +bool FMIndex::IsEqual(uchar const *pattern, DocId begin, DocId end) const { TextPosition m = std::strlen((char *)pattern); if (m == 0) @@ -195,7 +197,7 @@ bool TCImplementation::IsEqual(uchar const *pattern, DocId begin, DocId end) con return false; } -bool TCImplementation::IsContains(uchar const * pattern) const +bool FMIndex::IsContains(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -210,7 +212,7 @@ bool TCImplementation::IsContains(uchar const * pattern) const return false; } -bool TCImplementation::IsContains(uchar const * pattern, DocId begin, DocId end) const +bool FMIndex::IsContains(uchar const * pattern, DocId begin, DocId end) const { // Here counting is as fast as existential querying if (CountContains(pattern, begin, end) > 0) @@ -218,14 +220,14 @@ bool TCImplementation::IsContains(uchar const * pattern, DocId begin, DocId end) return false; } -bool TCImplementation::IsLessThan(uchar const * pattern) const +bool FMIndex::IsLessThan(uchar const * pattern) const { if (CountLessThan(pattern) > 0) return true; return false; } -bool TCImplementation::IsLessThan(uchar const * pattern, DocId begin, DocId end) const +bool FMIndex::IsLessThan(uchar const * pattern, DocId begin, DocId end) const { if (CountLessThan(pattern, begin, end) > 0) return true; @@ -235,7 +237,7 @@ bool TCImplementation::IsLessThan(uchar const * pattern, DocId begin, DocId end) /****************************************************************** * Counting queries */ -ulong TCImplementation::Count(uchar const * pattern) const +ulong FMIndex::Count(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -246,7 +248,7 @@ ulong TCImplementation::Count(uchar const * pattern) const return count; } -unsigned TCImplementation::CountPrefix(uchar const * pattern) const +unsigned FMIndex::CountPrefix(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -259,7 +261,7 @@ unsigned TCImplementation::CountPrefix(uchar const * pattern) const return CountEndmarkers(sp, ep); } -unsigned TCImplementation::CountPrefix(uchar const * pattern, DocId begin, DocId end) const +unsigned FMIndex::CountPrefix(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -272,7 +274,7 @@ unsigned TCImplementation::CountPrefix(uchar const * pattern, DocId begin, DocId return CountEndmarkers(sp, ep, begin, end); } -unsigned TCImplementation::CountSuffix(uchar const * pattern) const +unsigned FMIndex::CountSuffix(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -285,7 +287,7 @@ unsigned TCImplementation::CountSuffix(uchar const * pattern) const return count; } -unsigned TCImplementation::CountSuffix(uchar const * pattern, DocId begin, DocId end) const +unsigned FMIndex::CountSuffix(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -298,7 +300,7 @@ unsigned TCImplementation::CountSuffix(uchar const * pattern, DocId begin, DocId return count; } -unsigned TCImplementation::CountEqual(uchar const *pattern) const +unsigned FMIndex::CountEqual(uchar const *pattern) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -312,7 +314,7 @@ unsigned TCImplementation::CountEqual(uchar const *pattern) const return CountEndmarkers(sp, ep); } -unsigned TCImplementation::CountEqual(uchar const *pattern, DocId begin, DocId end) const +unsigned FMIndex::CountEqual(uchar const *pattern, DocId begin, DocId end) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -326,7 +328,7 @@ unsigned TCImplementation::CountEqual(uchar const *pattern, DocId begin, DocId e return CountEndmarkers(sp, ep); // Already within [begin, end] } -unsigned TCImplementation::CountContains(uchar const * pattern) const +unsigned FMIndex::CountContains(uchar const * pattern) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -338,7 +340,7 @@ unsigned TCImplementation::CountContains(uchar const * pattern) const return result.size(); } -unsigned TCImplementation::CountContains(uchar const * pattern, DocId begin, DocId end) const +unsigned FMIndex::CountContains(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -351,7 +353,7 @@ unsigned TCImplementation::CountContains(uchar const * pattern, DocId begin, Doc } // Less than or equal -unsigned TCImplementation::CountLessThan(uchar const * pattern) const +unsigned FMIndex::CountLessThan(uchar const * pattern) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -364,7 +366,7 @@ unsigned TCImplementation::CountLessThan(uchar const * pattern) const return CountEndmarkers(sp, ep); } -unsigned TCImplementation::CountLessThan(uchar const * pattern, DocId begin, DocId end) const +unsigned FMIndex::CountLessThan(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -380,7 +382,7 @@ unsigned TCImplementation::CountLessThan(uchar const * pattern, DocId begin, Doc /** * Document reporting queries */ -TextCollection::document_result TCImplementation::Prefix(uchar const * pattern) const +TextCollection::document_result FMIndex::Prefix(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -393,7 +395,7 @@ TextCollection::document_result TCImplementation::Prefix(uchar const * pattern) return EnumerateEndmarkers(sp, ep); } -TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, DocId begin, DocId end) const +TextCollection::document_result FMIndex::Prefix(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -406,7 +408,7 @@ TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, return EnumerateEndmarkers(sp, ep, begin, end); } -TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) const +TextCollection::document_result FMIndex::Suffix(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -448,7 +450,7 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) return result; } -TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, DocId begin, DocId end) const +TextCollection::document_result FMIndex::Suffix(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -491,7 +493,7 @@ TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, } -TextCollection::document_result TCImplementation::Equal(uchar const *pattern) const +TextCollection::document_result FMIndex::Equal(uchar const *pattern) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -505,7 +507,7 @@ TextCollection::document_result TCImplementation::Equal(uchar const *pattern) co return EnumerateEndmarkers(sp, ep); } -TextCollection::document_result TCImplementation::Equal(uchar const *pattern, DocId begin, DocId end) const +TextCollection::document_result FMIndex::Equal(uchar const *pattern, DocId begin, DocId end) const { TextPosition m = strlen((char const *)pattern); if (m == 0) @@ -520,7 +522,7 @@ TextCollection::document_result TCImplementation::Equal(uchar const *pattern, Do } -TextCollection::document_result TCImplementation::Contains(uchar const * pattern) const +TextCollection::document_result FMIndex::Contains(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -539,7 +541,7 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern return result; } -TextCollection::document_result TCImplementation::Contains(uchar const * pattern, DocId begin, DocId end) const +TextCollection::document_result FMIndex::Contains(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -563,7 +565,7 @@ TextCollection::document_result TCImplementation::Contains(uchar const * pattern *** * * FIXME Lessthan or equal */ -TextCollection::document_result TCImplementation::LessThan(uchar const * pattern) const +TextCollection::document_result FMIndex::LessThan(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -576,7 +578,7 @@ TextCollection::document_result TCImplementation::LessThan(uchar const * pattern return EnumerateEndmarkers(sp, ep); } -TextCollection::document_result TCImplementation::LessThan(uchar const * pattern, DocId begin, DocId end) const +TextCollection::document_result FMIndex::LessThan(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -590,7 +592,7 @@ TextCollection::document_result TCImplementation::LessThan(uchar const * pattern } -TextCollection::document_result TCImplementation::KMismaches(uchar const * pattern, unsigned k) const +TextCollection::document_result FMIndex::KMismaches(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -609,7 +611,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 FMIndex::KErrors(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -636,7 +638,7 @@ TextCollection::document_result TCImplementation::KErrors(uchar const * pattern, /** * Full result set queries */ -TextCollection::full_result TCImplementation::FullContains(uchar const * pattern) const +TextCollection::full_result FMIndex::FullContains(uchar const * pattern) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -653,7 +655,7 @@ TextCollection::full_result TCImplementation::FullContains(uchar const * pattern return result; } -TextCollection::full_result TCImplementation::FullContains(uchar const * pattern, DocId begin, DocId end) const +TextCollection::full_result FMIndex::FullContains(uchar const * pattern, DocId begin, DocId end) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -670,7 +672,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 FMIndex::FullKMismatches(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -687,7 +689,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 FMIndex::FullKErrors(uchar const * pattern, unsigned k) const { TextPosition m = strlen((char *)pattern); if (m == 0) @@ -714,8 +716,9 @@ TextCollection::full_result TCImplementation::FullKErrors(uchar const * pattern, * * Throws a std::runtime_error exception on i/o error. * First byte that is saved represents the version number of the save file. - * In version 2 files, the data fields are: - * uchar versionFlag; + * In this version files, the data fields are: + * uchar type; + uchar versionFlag; TextPosition n; unsigned samplerate; unsigned C[256]; @@ -727,24 +730,31 @@ TextCollection::full_result TCImplementation::FullKErrors(uchar const * pattern, unsigned numberOfTexts; ulong maxTextLength; static_sequence *docId; + * + * The second parameter (filename's prefix) is ignored. */ -void TCImplementation::Save(FILE *file) const +void FMIndex::Save(FILE *file, char const *ignored) const { + const char type = 'F'; + // Saving type info: + if (std::fwrite(&type, 1, 1, file) != 1) + throw std::runtime_error("FMIndex::Save(): file write error (type flag)."); + // Saving version info: if (std::fwrite(&versionFlag, 1, 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (version flag)."); + throw std::runtime_error("FMIndex::Save(): file write error (version flag)."); if (std::fwrite(&(this->n), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (n)."); + throw std::runtime_error("FMIndex::Save(): file write error (n)."); if (std::fwrite(&(this->samplerate), sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (samplerate)."); + throw std::runtime_error("FMIndex::Save(): file write error (samplerate)."); for(ulong i = 0; i < 256; ++i) if (std::fwrite(this->C + i, sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (C table)."); + throw std::runtime_error("FMIndex::Save(): file write error (C table)."); if (std::fwrite(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (bwt end position)."); + throw std::runtime_error("FMIndex::Save(): file write error (bwt end position)."); alphabetrank->save(file); sampled->save(file); @@ -752,9 +762,9 @@ void TCImplementation::Save(FILE *file) const suffixDocId->Save(file); if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (numberOfTexts)."); + throw std::runtime_error("FMIndex::Save(): file write error (numberOfTexts)."); if (std::fwrite(&(this->maxTextLength), sizeof(ulong), 1, file) != 1) - throw std::runtime_error("TCImplementation::Save(): file write error (maxTextLength)."); + throw std::runtime_error("FMIndex::Save(): file write error (maxTextLength)."); Doc->save(file); textStorage->Save(file); @@ -766,37 +776,39 @@ void TCImplementation::Save(FILE *file) const * Load index from a file handle * * Throws a std::runtime_error exception on i/o error. - * For more info, see TCImplementation::Save(). + * For more info, see FMIndex::Save(). * * index_mode_t is defined in TextCollection.h and * defaults to both the index and "naive" text. * * Note: Samplerate can not be changed during load. */ -TCImplementation::TCImplementation(FILE *file, index_mode_t im, unsigned samplerate_) +FMIndex::FMIndex(FILE *file, index_mode_t im, unsigned samplerate_) : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0), suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0) { + // NB: Type byte has already been read from input + uchar verFlag = 0; if (std::fread(&verFlag, 1, 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (version flag)."); - if (verFlag != TCImplementation::versionFlag) - throw std::runtime_error("TCImplementation::Load(): invalid save file version."); + throw std::runtime_error("FMIndex::Load(): file read error (version flag)."); + if (verFlag != FMIndex::versionFlag) + throw std::runtime_error("FMIndex::Load(): invalid save file version."); if (std::fread(&(this->n), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (n)."); + throw std::runtime_error("FMIndex::Load(): file read error (n)."); if (std::fread(&samplerate, sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (samplerate)."); + throw std::runtime_error("FMIndex::Load(): file read error (samplerate)."); // FIXME samplerate can not be changed during load. // if (this->samplerate == 0) // this->samplerate = samplerate; for(ulong i = 0; i < 256; ++i) if (std::fread(this->C + i, sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (C table)."); + throw std::runtime_error("FMIndex::Load(): file read error (C table)."); if (std::fread(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (bwt end position)."); + throw std::runtime_error("FMIndex::Load(): file read error (bwt end position)."); alphabetrank = static_sequence::load(file); if (im == index_mode_text_only) { delete alphabetrank; alphabetrank = 0; } @@ -809,9 +821,9 @@ TCImplementation::TCImplementation(FILE *file, index_mode_t im, unsigned sampler if (im == index_mode_text_only) { delete suffixDocId; suffixDocId = 0; } if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (numberOfTexts)."); + throw std::runtime_error("FMIndex::Load(): file read error (numberOfTexts)."); if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1) - throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength)."); + throw std::runtime_error("FMIndex::Load(): file read error (maxTextLength)."); Doc = new ArrayDoc(file); //static_sequence::load(file); if (im == index_mode_text_only) { delete Doc; Doc = 0; } @@ -827,7 +839,7 @@ TCImplementation::TCImplementation(FILE *file, index_mode_t im, unsigned sampler /** * Rest of the functions follow... */ -ulong TCImplementation::searchPrefix(uchar const *pattern, ulong i, ulong *sp, ulong *ep) const +ulong FMIndex::searchPrefix(uchar const *pattern, ulong i, ulong *sp, ulong *ep) const { int c; while (*sp<=*ep && i>=1) @@ -843,7 +855,7 @@ ulong TCImplementation::searchPrefix(uchar const *pattern, ulong i, ulong *sp, u } -ulong TCImplementation::kmismatches(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k) const +ulong FMIndex::kmismatches(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k) const { if (sp>ep) return 0; if (j == 0) @@ -878,7 +890,7 @@ 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 FMIndex::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 @@ -918,7 +930,7 @@ ulong TCImplementation::kerrors(suffix_range_vector &result, uchar const *patter } -ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const +ulong FMIndex::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) int c = (int)pattern[m-1]; @@ -940,7 +952,7 @@ ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPositi return 0; } -ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult, DocId begin, DocId end) const +ulong FMIndex::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult, DocId begin, DocId end) const { // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i) int c = (int)pattern[m-1]; @@ -964,7 +976,7 @@ ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPositi } -ulong TCImplementation::SearchLessThan(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const +ulong FMIndex::SearchLessThan(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const { // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i) uint c = (int)pattern[m-1]; @@ -990,7 +1002,7 @@ ulong TCImplementation::SearchLessThan(uchar const * pattern, TextPosition m, Te } -TCImplementation::~TCImplementation() { +FMIndex::~FMIndex() { delete alphabetrank; delete sampled; delete suffixes; @@ -999,7 +1011,7 @@ TCImplementation::~TCImplementation() { delete textStorage; } -void TCImplementation::makewavelet(uchar *bwt) +void FMIndex::makewavelet(uchar *bwt) { ulong i, min = 0, max; @@ -1043,7 +1055,7 @@ void TCImplementation::makewavelet(uchar *bwt) #endif } -void TCImplementation::maketables(ulong sampleLength, char tsType, CSA::DeltaVector & notIndexed, const string & niText) +void FMIndex::maketables(ulong sampleLength, char tsType, CSA::DeltaVector & notIndexed, const string & niText) { // Calculate BWT end-marker position (of last inserted text) { @@ -1269,7 +1281,7 @@ void TCImplementation::maketables(ulong sampleLength, char tsType, CSA::DeltaVec * Starting text position of the document is stored into second parameter. * Binary searching on text starting positions. */ -TextCollection::DocId TCImplementation::DocIdAtTextPos(BlockArray* textStartPos, TextPosition i) const +TextCollection::DocId FMIndex::DocIdAtTextPos(BlockArray* textStartPos, TextPosition i) const { assert(i < n); diff --git a/TCImplementation.h b/FMIndex.h similarity index 97% rename from TCImplementation.h rename to FMIndex.h index ff5dff3..e12be99 100644 --- a/TCImplementation.h +++ b/FMIndex.h @@ -1,6 +1,7 @@ /****************************************************************************** * Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki * * * + * FMIndex implementation for the TextCollection interface * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU Lesser General Public License as published * @@ -18,8 +19,8 @@ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * *****************************************************************************/ -#ifndef _TCImplementation_H_ -#define _TCImplementation_H_ +#ifndef _FMIndex_H_ +#define _FMIndex_H_ #include "incbwt/bits/deltavector.h" @@ -58,11 +59,11 @@ namespace SXSI * Implementation of the TextCollection interface * */ -class TCImplementation : public SXSI::TextCollection { +class FMIndex : public SXSI::TextCollection { public: - TCImplementation(uchar *, ulong, unsigned, unsigned, ulong, ulong, - CSA::DeltaVector &, const std::string &, char); - ~TCImplementation(); + FMIndex(uchar *, ulong, unsigned, unsigned, ulong, ulong, + CSA::DeltaVector &, const std::string &, char); + ~FMIndex(); bool EmptyText(DocId) const; @@ -140,8 +141,8 @@ public: full_result FullKErrors(uchar const *, unsigned) const; // Index from/to disk - TCImplementation(FILE *, index_mode_t, unsigned); - void Save(FILE *) const; + FMIndex(FILE *, index_mode_t, unsigned); + void Save(FILE *, char const *) const; private: typedef std::vector > suffix_range_vector; @@ -379,7 +380,7 @@ private: } } -}; // class TCImplementation +}; // class FMIndex } // namespace SXSI diff --git a/FMIndexBuilder.cpp b/FMIndexBuilder.cpp new file mode 100644 index 0000000..ea52224 --- /dev/null +++ b/FMIndexBuilder.cpp @@ -0,0 +1,146 @@ +#include "incbwt/rlcsa_builder.h" +#include "incbwt/bits/deltavector.h" + +#include "FMIndexBuilder.h" +#include "FMIndex.h" + +using std::string; + +namespace SXSI +{ + +struct TCBuilderRep +{ + unsigned samplerate; + CSA::RLCSABuilder * sa; + + ulong n; + // Total number of texts in the collection + unsigned numberOfTexts; + // Length of the longest text + ulong maxTextLength; + ulong numberOfSamples; + + CSA::DeltaEncoder *notIndexed; // Doc IDs of those texts that are excluded from index. + string niText; // Texts that are not indexed. + +#ifdef TCB_TEST_BWT + DynFMI *dynFMI; +#endif +}; + +/** + * Init text collection + * + */ +FMIndexBuilder::FMIndexBuilder(unsigned samplerate, ulong estimatedInputLength) + : p_(new struct TCBuilderRep()) +{ + p_->n = 0; + p_->samplerate = samplerate; + p_->numberOfTexts = 0; + p_->numberOfSamples = 0; + p_->maxTextLength = 0; + p_->notIndexed = new CSA::DeltaEncoder(32); // Block size of 32 + p_->niText = ""; + + // Current params: 8 bytes, no samples, buffer size n/10 bytes. + // Buffer size is always at least 15MB: + if (estimatedInputLength < TEXTCOLLECTION_DEFAULT_INPUT_LENGTH) + estimatedInputLength = TEXTCOLLECTION_DEFAULT_INPUT_LENGTH; + p_->sa = new CSA::RLCSABuilder(8, 0, estimatedInputLength/10); + assert(p_->sa->isOk()); + +#ifdef TCB_TEST_BWT + uchar temp[256]; + for (unsigned i = 0; i < 255; ++i) + temp[i] = i+1; + temp[255] = 0; + p_->dynFMI = new DynFMI(temp, 1, 255, false); +#endif +} + +FMIndexBuilder::~FMIndexBuilder() +{ +#ifdef TCB_TEST_BWT + delete p_->dynFMI; +#endif + + delete p_->sa; + delete p_->notIndexed; + delete p_; +} + +void FMIndexBuilder::InsertText(uchar const * text, bool index) +{ + TextCollection::TextPosition m = std::strlen((char *)text) + 1; + if (m <= 1) + { + // FIXME indexing empty texts + std::cerr << "FMIndexBuilder::InsertText() error: can not index empty texts!" << std::endl; + exit(1); + } + + p_->numberOfTexts ++; + + if (index) + { + /** + * Insert text into the index + */ + p_->n += m; + p_->numberOfSamples += (m-1)/p_->samplerate; + + if (m > p_->maxTextLength) + p_->maxTextLength = m; // Store length of the longest text seen so far. + + p_->sa->insertSequence((char*)text, m-1, 0); + assert(p_->sa->isOk()); + } + else + { + /** + * Insert text only to TextStorage + */ + p_->notIndexed->setBit(p_->numberOfTexts - 1); + p_->niText.append((const char *)text, m); + } +} + + +TextCollection * FMIndexBuilder::InitTextCollection(char type) +{ + uchar * bwt = 0; + CSA::usint length = 0; + if (p_->numberOfTexts == 0) + { + p_->numberOfTexts ++; // Add one empty text + bwt = new uchar[2]; + bwt[0] = '\0'; + bwt[1] = '\0'; + length = 1; + p_->maxTextLength = 1; + } + else + { + bwt = (uchar *)p_->sa->getBWT(length); + delete p_->sa; + p_->sa = 0; + + assert(length == p_->n); + } + + p_->notIndexed->setBit(p_->numberOfTexts); // FIXME CSA::DeltaVector can not be all 0's + CSA::DeltaVector deltav = CSA::DeltaVector(*p_->notIndexed, p_->numberOfTexts+1); + delete p_->notIndexed; + p_->notIndexed = 0; + + TextCollection *result = new FMIndex(bwt, (ulong)length, + p_->samplerate, p_->numberOfTexts, p_->maxTextLength, p_->numberOfSamples, + deltav, p_->niText, type); + + return result; +} + + +} // namespace SXSI diff --git a/FMIndexBuilder.h b/FMIndexBuilder.h new file mode 100644 index 0000000..a18540b --- /dev/null +++ b/FMIndexBuilder.h @@ -0,0 +1,85 @@ +/****************************************************************************** + * Copyright (C) 2009 by Niko Valimaki * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU Lesser General Public License as published * + * by the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * + ******************************************************************************/ + +#ifndef _SXSI_FMIndexBuilder_h_ +#define _SXSI_FMIndexBuilder_h_ + +#include "TextCollectionBuilder.h" +#include "TextStorage.h" +#include "Tools.h" // Defines ulong and uchar. + +#include +#include +#include // Defines std::pair. +#include // Defines std::strlen, added by Kim + +// Un-comment to compare BWT against a BWT generated from class dynFMI: +//#define TCB_TEST_BWT + + +namespace SXSI +{ + struct TCBuilderRep; // Pimpl + + /** + * Build an instance of the TextCollection class. + */ + class FMIndexBuilder : public TextCollectionBuilder + { + public: + FMIndexBuilder(unsigned samplerate, ulong estimatedInputLength); + + virtual ~FMIndexBuilder(); + + /** + * Insert text + * + * Must be a zero-terminated string from alphabet [1,255]. + * Can not be called after makeStatic(). + * The i'th text insertion gets an identifier value i-1. + * In other words, document identifiers start from 0. + * + * Second parameter tells if the text will be added to the + * index also. If false, text is added only to the TextCollection + * and can not be searched for. + */ + virtual void InsertText(uchar const *, bool index = true); + /** + * Make static + * + * Convert to a static collection. + * New texts can not be inserted after this operation. + * + * TextStorage type defaults to TYPE_PLAIN_TEXT, another + * possible type is TYPE_LZ_INDEX. + */ + virtual TextCollection * InitTextCollection(char type = TextStorage::TYPE_PLAIN_TEXT); + + private: + FMIndexBuilder(); + + // Using Pimpl idiom to hide RLCSA implementation. + struct TCBuilderRep * p_; + + // No copy constructor or assignment + FMIndexBuilder(FMIndexBuilder const&); + FMIndexBuilder& operator = (FMIndexBuilder const&); + }; +} +#endif diff --git a/SWCSABuilder.h b/SWCSABuilder.h new file mode 100644 index 0000000..e60bf02 --- /dev/null +++ b/SWCSABuilder.h @@ -0,0 +1,118 @@ +/****************************************************************************** + * Copyright (C) 2009 by Niko Valimaki * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU Lesser General Public License as published * + * by the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * + ******************************************************************************/ + +#ifndef _SXSI_SWCSABuilder_h_ +#define _SXSI_SWCSABuilder_h_ + +#include "TextCollectionBuilder.h" +#include "TextStorage.h" +#include "Tools.h" // Defines ulong and uchar. +#include "SWCSAWrapper.h" + +#include +#include // Defines std::pair. +#include // Defines std::strlen, added by Kim + +namespace SXSI +{ + /** + * Build an instance of the TextCollection class. + */ + class SWCSABuilder : public TextCollectionBuilder + { + public: + SWCSABuilder(unsigned sampler) + : text(""), samplerate(sampler), numberOfTexts(0) + { /* NOP */ } + + virtual ~SWCSABuilder() + { /* NOP */ } + + /** + * Insert text + * + * Must be a zero-terminated string from alphabet [1,255]. + * Can not be called after makeStatic(). + * The i'th text insertion gets an identifier value i-1. + * In other words, document identifiers start from 0. + * + * All texts must be inserted into the index! + * The default (FMIndex) text collection supports non-indexed texts. + */ + virtual void InsertText(uchar const *t, bool index = true) + { + if (strlen((char const *) t) == 0) + { + std::cerr << "SWCSABuilder::InsertText(): Can not index empty texts!" << std::endl; + std::exit(1); + } + assert(index); + if (!index) + { + std::cerr << "SWCSABuilder::InsertText(): The implementation of SWCSA does not support non-indexed texts" + << std::endl << "Use the default (FMIndex) text collection instead." << std::endl; + std::exit(1); + } + text.append((char const *) t, strlen((char const *) t) + 1); // +1 for 0-byte. + ++ numberOfTexts; + } + + /** + * Make static + * + * Convert to a static collection. + * New texts can not be inserted after this operation. + * + * + */ + virtual TextCollection * InitTextCollection(char type = TextStorage::TYPE_PLAIN_TEXT) + { + assert(type == TextStorage::TYPE_PLAIN_TEXT); + if (type != TextStorage::TYPE_PLAIN_TEXT) + { + std::cerr << "SWCSABuilder::InitTextCollection(): The implementation of SWCSA supports only TextStorage::TYPE_PLAIN_TEXT" + << std::endl << "Use the default (FMIndex) text collection instead." << std::endl; + std::exit(1); + } + + ulong n = text.size(); + uchar *t = new uchar[n]; // FIXME uses temporarily too much space + ulong l = text.copy((char *)t, n); + if (l != n) + { + std::cerr << "SWCSABuilder::InitTextCollection(): copy failed!" << std::endl; + std::exit(1); + } + text.clear(); + return new SWCSAWrapper(t, n, samplerate, numberOfTexts); // This will delete [] t. + } + + + private: + SWCSABuilder(); + std::string text; + unsigned samplerate; + unsigned numberOfTexts; + + // No copy constructor or assignment + SWCSABuilder(SWCSABuilder const&); + SWCSABuilder& operator = (SWCSABuilder const&); + }; +} +#endif diff --git a/SWCSAWrapper.h b/SWCSAWrapper.h new file mode 100644 index 0000000..731fc83 --- /dev/null +++ b/SWCSAWrapper.h @@ -0,0 +1,352 @@ +/****************************************************************************** + * Copyright (C) 2010 by Niko Välimäki * + * * + * FMIndex implementation for the TextCollection interface * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU Lesser General Public License as published * + * by the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * + *****************************************************************************/ + +#ifndef _SWCSAWrapper_H_ +#define _SWCSAWrapper_H_ + +#include "TextCollection.h" + +#include "TextStorage.h" + +#include "incbwt/bits/deltavector.h" +// Re-define word size to ulong: +#undef W +#if __WORDSIZE == 64 +# define W 64 +#else +# define W 32 +#endif + +#define SWCSAWRAPPER_VERSION_FLAG 101 + +#include "swcsa/utils/defValues.h" +#include "swcsa/utils/valstring.h" +#include "swcsa/interface.h" + +#include +#include + +namespace SXSI +{ + +/** + * Partial implementation of the TextCollection interface + * + * Supports index construction, save, load and simple search. + * Use FMIndex implementation for full support. + */ +class SWCSAWrapper : public SXSI::TextCollection { +public: + SWCSAWrapper(uchar * text, ulong length, unsigned samplerate, + unsigned numberOfTexts_) + : index(0), offsets(0), n(length), seSize(0), numberOfTexts(numberOfTexts_) + { + // Inicializes the arrays used to detect if a char is valid or not. + StartValid(); + + // Delta encoded bitvector of text offsets. + CSA::DeltaEncoder encoder(32); + encoder.setBit(0); // Start of the first text. + + // Construct offset map from words to text elements + seSize = 0; + { + uchar const *pbeg,*pend; + + pbeg = text; + pend = text+length; + + while (pbeg = pend) {size++;} // a unique BLANK at the end of the file. + else { + if (_Valid [*pbeg] ) { + while ( (sizerank(seSize - 1) << std::endl; + + char opt[100]; + snprintf(opt, 99, "sA=%u;sAinv=%u;sPsi=%u", samplerate, samplerate, samplerate); + + int r = build_index(text, n, opt, &index); + if (r) + { + std::cout << "SWCSAWrapper error: " << error_index(r) << std::endl; + std::exit(r); + } + } + + ~SWCSAWrapper() + { + int r = free_index (index); + if (r) + { + std::cout << "SWCSAWrapper destructor error: " << error_index(r) << std::endl; + std::exit(r); + } + index = 0; + delete offsets; offsets = 0; + } + + bool EmptyText(DocId k) const + { + assert(k < (DocId)numberOfTexts); + return false; // Empty texts are not indexed + } + + /** + * Extracting one text. + * + * Call DeleteText() for each pointer returned by GetText() + * to avoid possible memory leaks. + */ + uchar * GetText(DocId i) const + { + return GetText(i, i); + } + void DeleteText(uchar *text) const + { + free(text); + } + + /** + * Returns a pointer to the beginning of texts i, i+1, ..., j. + * Texts are separated by a '\0' byte. + * + * Call DeleteText() for each pointer returned by GetText() + * to avoid possible memory leaks. + */ + uchar * GetText(DocId i, DocId j) const + { + ulong from, to, l; + uchar *text; + from = offsets->select(i); + to = offsets->select(i+1); // ADD one 1-bit in to end!!! + + int r = extractWords(index, from, to, &text, &l); + if (r) + { + std::cout << "SWCSAWrapper error: " << error_index(r) << std::endl; + std::exit(r); + } + text[l] = 0; + return text; + } + + bool IsPrefix(uchar const *) const { unsupported(); return false; }; + bool IsSuffix(uchar const *) const { unsupported(); return false; }; + bool IsEqual(uchar const *) const { unsupported(); return false; }; + bool IsContains(uchar const *) const { unsupported(); return false; }; + bool IsLessThan(uchar const *) const { unsupported(); return false; }; + + bool IsPrefix(uchar const *, DocId, DocId) const { unsupported(); return false; }; + bool IsSuffix(uchar const *, DocId, DocId) const { unsupported(); return false; }; + bool IsEqual(uchar const *, DocId, DocId) const { unsupported(); return false; }; + bool IsContains(uchar const *, DocId, DocId) const { unsupported(); return false; }; + bool IsLessThan(uchar const *, DocId, DocId) const { unsupported(); return false; }; + + ulong Count(uchar const *pattern) const + { + ulong occs = 0; + // FIXME Const correctness is broken! + int r = count (index, (uchar *)pattern, std::strlen((char const *)pattern), &occs); + if (r) + { + std::cout << "SWCSAWrapper::Count error " << error_index(r) << std::endl; + std::exit(r); + } + return occs; + } + unsigned CountPrefix(uchar const *) const { unsupported(); return 0; }; + unsigned CountSuffix(uchar const *) const { unsupported(); return 0; }; + unsigned CountEqual(uchar const *) const { unsupported(); return 0; }; + unsigned CountContains(uchar const *) const { unsupported(); return 0; }; + unsigned CountLessThan(const unsigned char*) const { unsupported(); return 0; }; + + unsigned CountPrefix(uchar const *, DocId, DocId) const { unsupported(); return 0; }; + unsigned CountSuffix(uchar const *, DocId, DocId) const { unsupported(); return 0; }; + unsigned CountEqual(uchar const *, DocId, DocId) const { unsupported(); return 0; }; + unsigned CountContains(uchar const *, DocId, DocId) const { unsupported(); return 0; }; + unsigned CountLessThan(uchar const *, DocId, DocId) const { unsupported(); return 0; }; + + // Definition of document_result is inherited from SXSI::TextCollection. + document_result Prefix(uchar const *) const { unsupported(); return document_result(); }; + document_result Suffix(uchar const *) const { unsupported(); return document_result(); }; + document_result Equal(uchar const *) const { unsupported(); return document_result(); }; + document_result Contains(uchar const *pattern) const + { + ulong *occ = 0, numocc = 0; + // FIXME Const correctness is broken! + int r = locateWord(index, (uchar *)pattern, std::strlen((char const *)pattern), &occ, &numocc, 0); + if (r) + { + std::cout << "SWCSAWrapper::Contains error: " << error_index(r) << std::endl; + std::exit(r); + } + + document_result dr; + dr.reserve(numocc+1); + for (ulong i = 0; i < numocc; ++i) + dr.push_back(offsets->rank(occ[i])-1); + + free(occ); + return dr; + } + document_result LessThan(uchar const *) const { unsupported(); return document_result(); }; + document_result KMismaches(uchar const *, unsigned) const { unsupported(); return document_result(); }; + document_result KErrors(uchar const *, unsigned) const { unsupported(); return document_result(); }; + + document_result Prefix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); }; + document_result Suffix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); }; + document_result Equal(uchar const *, DocId, DocId) const { unsupported(); return document_result(); }; + document_result Contains(uchar const *, DocId, DocId) const { unsupported(); return document_result(); }; + document_result LessThan(uchar const *, DocId, DocId) const { unsupported(); return document_result(); }; + + // Definition of full_result is inherited from SXSI::TextCollection. + full_result FullContains(uchar const *) const { unsupported(); return full_result(); }; + full_result FullContains(uchar const *, DocId, DocId) const { unsupported(); return full_result(); }; + full_result FullKMismatches(uchar const *, unsigned) const { unsupported(); return full_result(); }; + full_result FullKErrors(uchar const *, unsigned) const { unsupported(); return full_result(); }; + + // Index from/to disk + SWCSAWrapper(FILE *file, char const *filename) + : index(0), offsets(0), n(0), seSize(0), numberOfTexts(0) + { + uchar verFlag = 0; + if (std::fread(&verFlag, 1, 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Load(): file read error (version flag)."); + if (verFlag != SWCSAWRAPPER_VERSION_FLAG) + throw std::runtime_error("SWCSAWrapper::Load(): invalid save file version."); + + if (std::fread(&(this->n), sizeof(TextPosition), 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Load(): file read error (n)."); + if (std::fread(&seSize, sizeof(ulong), 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Load(): file read error (seSize)."); + if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1) + throw std::runtime_error("FMIndex::Load(): file read error (numberOfTexts)."); + + offsets = new CSA::DeltaVector(file); + + // FIXME Const correctness is broken! + int r = load_index((char *)filename, &index); + if (r) + { + std::cout << "SWCSAWrapper::Save error: " << error_index(r) << std::endl; + std::exit(r); + } + } + + void Save(FILE *file, char const *filename) const + { + const char type = 'W'; + // Saving type info: + if (std::fwrite(&type, 1, 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Save(): file write error (type flag)."); + + const uchar ver = SWCSAWRAPPER_VERSION_FLAG; + // Saving version info: + if (std::fwrite(&ver, 1, 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Save(): file write error (version flag)."); + + if (std::fwrite(&(this->n), sizeof(TextPosition), 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Save(): file write error (n)."); + if (std::fwrite(&(this->seSize), sizeof(ulong), 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Save(): file write error (seSize)."); + if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1) + throw std::runtime_error("SWCSAWrapper::Save(): file write error (numberOfTexts)."); + + offsets->writeTo(file); + + // FIXME Const correctness is broken! + int r = save_index(index, (char *)filename); + if (r) + { + std::cout << "SWCSAWrapper::Save error: " << error_index(r) << std::endl; + std::exit(r); + } + } + +private: + void *index; + CSA::DeltaVector *offsets; + + TextPosition n; + ulong seSize; + + // Total number of texts in the collection + unsigned numberOfTexts; + + void unsupported() const + { + std::cerr << std::endl << "-------------------------------------------------------------\n" + << "SWCSAWrapper: unsupported method!\nSee SWCSAWrapper.h for more details.\n" + << "The default index (FMIndex) implements this method!" << std::endl; + std::exit(5); + } +}; // class SWCSAWrapper + +} // namespace SXSI + +#endif diff --git a/TextCollection.cpp b/TextCollection.cpp index 2aef067..1755b6b 100644 --- a/TextCollection.cpp +++ b/TextCollection.cpp @@ -1,5 +1,6 @@ #include "TextCollection.h" -#include "TCImplementation.h" +#include "FMIndex.h" +#include "SWCSAWrapper.h" namespace SXSI { @@ -9,9 +10,22 @@ namespace SXSI * * See TCImplementation.h for more details. */ - TextCollection * TextCollection::Load(FILE *fp, index_mode_t im, unsigned samplerate) + TextCollection * TextCollection::Load(FILE *fp, char const *filename, index_mode_t im, unsigned samplerate) { - TextCollection *result = new TCImplementation(fp, im, samplerate); - return result; + char type = 0; + if (std::fread(&type, 1, 1, fp) != 1) + throw std::runtime_error("TextCollection::Load(): file read error (type flag)."); + switch (type) + { + case 'F': + return new FMIndex(fp, im, samplerate); + break; + case 'W': + return new SWCSAWrapper(fp, filename); + break; + } + + std::cerr << "TextCollection::Load(): invalid save file version or corrupted input file." << std::endl; + std::exit(1); } } diff --git a/TextCollection.h b/TextCollection.h index 2ea24ca..9c6591f 100644 --- a/TextCollection.h +++ b/TextCollection.h @@ -48,19 +48,25 @@ namespace SXSI /** * Load from a file * + * The second parameter is a prefix to be used for multiple + * files. (SWCSAWrapper uses multiple save files!) + * * New samplerate can be given, otherwise will use the one specified in the save file! * * Throws an exception if std::fread() fails. * */ - static TextCollection* Load(FILE *, index_mode_t = index_mode_default, unsigned samplerate = 0); + static TextCollection* Load(FILE *, char const *, index_mode_t = index_mode_default, unsigned samplerate = 0); /** * Save data structure into a file - * + * + * The second parameter is a prefix to be used for multiple + * files. (SWCSAWrapper uses multiple save files!) + * * Throws an exception if std::fwrite() fails. */ - virtual void Save(FILE *) const = 0; + virtual void Save(FILE *, char const *) const = 0; /** * Virtual destructor diff --git a/TextCollectionBuilder.cpp b/TextCollectionBuilder.cpp index 552abb1..6137406 100644 --- a/TextCollectionBuilder.cpp +++ b/TextCollectionBuilder.cpp @@ -1,146 +1,24 @@ -#include "incbwt/rlcsa_builder.h" -#include "incbwt/bits/deltavector.h" - #include "TextCollectionBuilder.h" -#include "TCImplementation.h" - -using std::string; +#include "FMIndexBuilder.h" +#include "SWCSABuilder.h" namespace SXSI { - -struct TCBuilderRep -{ - unsigned samplerate; - CSA::RLCSABuilder * sa; - - ulong n; - // Total number of texts in the collection - unsigned numberOfTexts; - // Length of the longest text - ulong maxTextLength; - ulong numberOfSamples; - - CSA::DeltaEncoder *notIndexed; // Doc IDs of those texts that are excluded from index. - string niText; // Texts that are not indexed. - -#ifdef TCB_TEST_BWT - DynFMI *dynFMI; -#endif -}; - -/** - * Init text collection - * - */ -TextCollectionBuilder::TextCollectionBuilder(unsigned samplerate, ulong estimatedInputLength) - : p_(new struct TCBuilderRep()) -{ - p_->n = 0; - p_->samplerate = samplerate; - p_->numberOfTexts = 0; - p_->numberOfSamples = 0; - p_->maxTextLength = 0; - p_->notIndexed = new CSA::DeltaEncoder(32); // Block size of 32 - p_->niText = ""; - - // Current params: 8 bytes, no samples, buffer size n/10 bytes. - // Buffer size is always at least 15MB: - if (estimatedInputLength < TEXTCOLLECTION_DEFAULT_INPUT_LENGTH) - estimatedInputLength = TEXTCOLLECTION_DEFAULT_INPUT_LENGTH; - p_->sa = new CSA::RLCSABuilder(8, 0, estimatedInputLength/10); - assert(p_->sa->isOk()); - -#ifdef TCB_TEST_BWT - uchar temp[256]; - for (unsigned i = 0; i < 255; ++i) - temp[i] = i+1; - temp[255] = 0; - p_->dynFMI = new DynFMI(temp, 1, 255, false); -#endif -} - -TextCollectionBuilder::~TextCollectionBuilder() -{ -#ifdef TCB_TEST_BWT - delete p_->dynFMI; -#endif - - delete p_->sa; - delete p_->notIndexed; - delete p_; -} - -void TextCollectionBuilder::InsertText(uchar const * text, bool index) -{ - TextCollection::TextPosition m = std::strlen((char *)text) + 1; - if (m <= 1) - { - // FIXME indexing empty texts - std::cerr << "TextCollectionBuilder::InsertText() error: can not index empty texts!" << std::endl; - exit(1); - } - - p_->numberOfTexts ++; - - if (index) - { - /** - * Insert text into the index - */ - p_->n += m; - p_->numberOfSamples += (m-1)/p_->samplerate; - - if (m > p_->maxTextLength) - p_->maxTextLength = m; // Store length of the longest text seen so far. - - p_->sa->insertSequence((char*)text, m-1, 0); - assert(p_->sa->isOk()); - } - else - { - /** - * Insert text only to TextStorage - */ - p_->notIndexed->setBit(p_->numberOfTexts - 1); - p_->niText.append((const char *)text, m); - } -} - - -TextCollection * TextCollectionBuilder::InitTextCollection(char type) +TextCollectionBuilder* TextCollectionBuilder::create(unsigned samplerate, + index_type_t type, + ulong estimatedInputLength) { - uchar * bwt = 0; - CSA::usint length = 0; - if (p_->numberOfTexts == 0) - { - p_->numberOfTexts ++; // Add one empty text - bwt = new uchar[2]; - bwt[0] = '\0'; - bwt[1] = '\0'; - length = 1; - p_->maxTextLength = 1; - } - else + switch (type) { - bwt = (uchar *)p_->sa->getBWT(length); - delete p_->sa; - p_->sa = 0; - - assert(length == p_->n); + case index_type_default: + return new FMIndexBuilder(samplerate, estimatedInputLength); + break; + case index_type_swcsa: + return new SWCSABuilder(samplerate); + break; } - - p_->notIndexed->setBit(p_->numberOfTexts); // FIXME CSA::DeltaVector can not be all 0's - CSA::DeltaVector deltav = CSA::DeltaVector(*p_->notIndexed, p_->numberOfTexts+1); - delete p_->notIndexed; - p_->notIndexed = 0; - - TextCollection *result = new TCImplementation(bwt, (ulong)length, - p_->samplerate, p_->numberOfTexts, p_->maxTextLength, p_->numberOfSamples, - deltav, p_->niText, type); - - return result; + std::cerr << "TextCollectionBuilder::create(): unknown type given: expecting enum value, type = " << type << std::endl; + std::exit(2); } - -} // namespace SXSI +} // Namespace SXSI diff --git a/TextCollectionBuilder.h b/TextCollectionBuilder.h index 6b3819a..43d4204 100644 --- a/TextCollectionBuilder.h +++ b/TextCollectionBuilder.h @@ -23,18 +23,10 @@ #include "TextCollection.h" #include "TextStorage.h" -#include "Tools.h" // Defines ulong and uchar. - -#include -#include -#include // Defines std::pair. -#include // Defines std::strlen, added by Kim - -// Un-comment to compare BWT against a BWT generated from class dynFMI: -//#define TCB_TEST_BWT +#include "Tools.h" // Default samplerate for suffix array samples -#define TEXTCOLLECTION_DEFAULT_SAMPLERATE 64 +#define TEXTCOLLECTION_DEFAULT_SAMPLERATE 32 // Default input length, used to calculate the buffer size. #define TEXTCOLLECTION_DEFAULT_INPUT_LENGTH (150 * 1024 * 1024) @@ -42,17 +34,23 @@ namespace SXSI { - struct TCBuilderRep; // Pimpl - /** - * Build an instance of the TextCollection class. + * Builder for an instance of the TextCollection class. */ class TextCollectionBuilder { public: - explicit TextCollectionBuilder(unsigned samplerate = TEXTCOLLECTION_DEFAULT_SAMPLERATE, - ulong estimatedInputLength = TEXTCOLLECTION_DEFAULT_INPUT_LENGTH); - ~TextCollectionBuilder(); + // Index type defaults to FM-index. + // SWCSA can be used for natural language inputs. + // NB: Current SWCSA uses a lot of memory during construction! + enum index_type_t { index_type_default, index_type_swcsa }; + + static TextCollectionBuilder* create(unsigned samplerate = TEXTCOLLECTION_DEFAULT_SAMPLERATE, + index_type_t type = index_type_default, + ulong estimatedInputLength = TEXTCOLLECTION_DEFAULT_INPUT_LENGTH); + + + virtual ~TextCollectionBuilder() { }; /** * Insert text @@ -66,7 +64,7 @@ namespace SXSI * index also. If false, text is added only to the TextCollection * and can not be searched for. */ - void InsertText(uchar const *, bool index = true); + virtual void InsertText(uchar const *, bool index = true) = 0; /** * Make static * @@ -76,15 +74,18 @@ namespace SXSI * TextStorage type defaults to TYPE_PLAIN_TEXT, another * possible type is TYPE_LZ_INDEX. */ - TextCollection * InitTextCollection(char type = TextStorage::TYPE_PLAIN_TEXT); + virtual TextCollection * InitTextCollection(char type = TextStorage::TYPE_PLAIN_TEXT) = 0; - private: - // Using Pimpl idiom to hide RLCSA implementation. - struct TCBuilderRep * p_; + protected: + // Protected constructor; use the static method TextCollectionBuilder::create() + TextCollectionBuilder() { }; + private: // No copy constructor or assignment TextCollectionBuilder(TextCollectionBuilder const&); TextCollectionBuilder& operator = (TextCollectionBuilder const&); }; + } + #endif diff --git a/TextStorage.h b/TextStorage.h index 24633fd..6294c6b 100644 --- a/TextStorage.h +++ b/TextStorage.h @@ -23,7 +23,16 @@ #include "TextCollection.h" #include "Tools.h" + #include "incbwt/bits/deltavector.h" +// Re-define word size to ulong: +#undef W +#if __WORDSIZE == 64 +# define W 64 +#else +# define W 32 +#endif + #include #include diff --git a/dependencies.mk b/dependencies.mk index c688689..24c4db6 100644 --- a/dependencies.mk +++ b/dependencies.mk @@ -1,39 +1,48 @@ BitRank.o: BitRank.cpp BitRank.h BlockArray.h Tools.h +FMIndex.o: FMIndex.cpp FMIndex.h incbwt/bits/deltavector.h \ + incbwt/bits/bitvector.h incbwt/bits/../misc/definitions.h \ + incbwt/bits/bitbuffer.h BitRank.h BlockArray.h Tools.h TextCollection.h \ + TextStorage.h ArrayDoc.h +FMIndexBuilder.o: FMIndexBuilder.cpp incbwt/rlcsa_builder.h \ + incbwt/rlcsa.h incbwt/bits/vectors.h incbwt/bits/deltavector.h \ + incbwt/bits/bitvector.h incbwt/bits/../misc/definitions.h \ + incbwt/bits/bitbuffer.h incbwt/bits/rlevector.h incbwt/sasamples.h \ + incbwt/misc/definitions.h incbwt/bits/bitbuffer.h \ + incbwt/bits/deltavector.h incbwt/misc/parameters.h \ + incbwt/misc/definitions.h incbwt/bits/deltavector.h FMIndexBuilder.h \ + TextCollectionBuilder.h TextCollection.h Tools.h TextStorage.h FMIndex.h \ + BitRank.h BlockArray.h ArrayDoc.h HeapProfiler.o: HeapProfiler.cpp HeapProfiler.h -TCImplementation.o: TCImplementation.cpp TCImplementation.h BitRank.h \ - BlockArray.h Tools.h TextCollection.h TextStorage.h \ - incbwt/bits/deltavector.h incbwt/bits/bitvector.h \ - incbwt/bits/../misc/definitions.h incbwt/bits/bitbuffer.h -TextCollection.o: TextCollection.cpp TextCollection.h Tools.h \ - TCImplementation.h BitRank.h BlockArray.h TextStorage.h \ - incbwt/bits/deltavector.h incbwt/bits/bitvector.h \ - incbwt/bits/../misc/definitions.h incbwt/bits/bitbuffer.h -TextCollectionBuilder.o: TextCollectionBuilder.cpp incbwt/rlcsa_builder.h \ - incbwt/rlcsa.h incbwt/bits/vectors.h incbwt/bits/deltavector.h \ - incbwt/bits/bitvector.h incbwt/bits/../misc/definitions.h \ - incbwt/bits/bitbuffer.h incbwt/bits/rlevector.h incbwt/sasamples.h \ - incbwt/misc/definitions.h incbwt/bits/bitbuffer.h \ - incbwt/bits/deltavector.h incbwt/misc/parameters.h \ - incbwt/misc/definitions.h TextCollectionBuilder.h TextCollection.h \ - Tools.h TCImplementation.h BitRank.h BlockArray.h TextStorage.h \ - incbwt/bits/deltavector.h +TextCollection.o: TextCollection.cpp TextCollection.h Tools.h FMIndex.h \ + incbwt/bits/deltavector.h incbwt/bits/bitvector.h \ + incbwt/bits/../misc/definitions.h incbwt/bits/bitbuffer.h BitRank.h \ + BlockArray.h TextStorage.h ArrayDoc.h SWCSAWrapper.h \ + swcsa/utils/defValues.h swcsa/utils/valstring.h swcsa/interface.h +TextCollectionBuilder.o: TextCollectionBuilder.cpp \ + TextCollectionBuilder.h TextCollection.h Tools.h TextStorage.h \ + incbwt/bits/deltavector.h incbwt/bits/bitvector.h \ + incbwt/bits/../misc/definitions.h incbwt/bits/bitbuffer.h \ + FMIndexBuilder.h SWCSABuilder.h SWCSAWrapper.h swcsa/utils/defValues.h \ + swcsa/utils/valstring.h swcsa/interface.h +TextStorage.o: TextStorage.cpp TextStorage.h TextCollection.h Tools.h \ + incbwt/bits/deltavector.h incbwt/bits/bitvector.h \ + incbwt/bits/../misc/definitions.h incbwt/bits/bitbuffer.h \ + lzindex/lztrie.h lzindex/basics.h lzindex/trie.h lzindex/heap.h \ + lzindex/parentheses.h lzindex/bitmap.h lzindex/hash.h lzindex/nodemap.h \ + lzindex/position.h Tools.o: Tools.cpp Tools.h bittree.o: bittree.cpp bittree.h rbtree.h Tools.h dynFMI.o: dynFMI.cpp dynFMI.h bittree.h rbtree.h Tools.h rbtree.o: rbtree.cpp rbtree.h -test2dRange.o: test2dRange.cpp testTextCollection.o: testTextCollection.cpp TextCollectionBuilder.h \ - TextCollection.h Tools.h HeapProfiler.h -testTextCollection2.o: testTextCollection2.cpp TextCollection.h Tools.h \ - HeapProfiler.h -testTextCollection3.o: testTextCollection3.cpp TextCollectionBuilder.h \ - TextCollection.h Tools.h -testTextCollection4.o: testTextCollection4.cpp TCImplementation.h \ - BitRank.h BlockArray.h Tools.h TextCollection.h TextStorage.h \ - incbwt/bits/deltavector.h incbwt/bits/bitvector.h \ - incbwt/bits/../misc/definitions.h incbwt/bits/bitbuffer.h \ - HeapProfiler.h + TextCollection.h Tools.h TextStorage.h incbwt/bits/deltavector.h \ + incbwt/bits/bitvector.h incbwt/bits/../misc/definitions.h \ + incbwt/bits/bitbuffer.h HeapProfiler.h testTextCollection5.o: testTextCollection5.cpp HeapProfiler.h \ - TextCollectionBuilder.h TextCollection.h Tools.h + TextCollectionBuilder.h TextCollection.h Tools.h TextStorage.h \ + incbwt/bits/deltavector.h incbwt/bits/bitvector.h \ + incbwt/bits/../misc/definitions.h incbwt/bits/bitbuffer.h timeTextCollection.o: timeTextCollection.cpp TextCollectionBuilder.h \ - TextCollection.h Tools.h + TextCollection.h Tools.h TextStorage.h incbwt/bits/deltavector.h \ + incbwt/bits/bitvector.h incbwt/bits/../misc/definitions.h \ + incbwt/bits/bitbuffer.h diff --git a/incbwt/dependencies.mk b/incbwt/dependencies.mk index 49ec47b..415788b 100644 --- a/incbwt/dependencies.mk +++ b/incbwt/dependencies.mk @@ -1,27 +1,26 @@ rlcsa.o: rlcsa.cpp rlcsa.h bits/vectors.h bits/deltavector.h \ - bits/bitvector.h bits/../misc/definitions.h bits/bitbuffer.h \ - bits/rlevector.h sasamples.h misc/definitions.h bits/bitbuffer.h \ - bits/deltavector.h misc/parameters.h misc/definitions.h misc/utils.h \ - qsufsort/qsufsort.h qsufsort/../misc/definitions.h + bits/bitvector.h bits/../misc/definitions.h bits/bitbuffer.h \ + bits/rlevector.h sasamples.h misc/definitions.h bits/bitbuffer.h \ + bits/deltavector.h misc/parameters.h misc/definitions.h misc/utils.h \ + qsufsort/qsufsort.h qsufsort/../misc/definitions.h rlcsa_builder.o: rlcsa_builder.cpp rlcsa_builder.h rlcsa.h bits/vectors.h \ - bits/deltavector.h bits/bitvector.h bits/../misc/definitions.h \ - bits/bitbuffer.h bits/rlevector.h sasamples.h misc/definitions.h \ - bits/bitbuffer.h bits/deltavector.h misc/parameters.h \ - misc/definitions.h + bits/deltavector.h bits/bitvector.h bits/../misc/definitions.h \ + bits/bitbuffer.h bits/rlevector.h sasamples.h misc/definitions.h \ + bits/bitbuffer.h bits/deltavector.h misc/parameters.h misc/definitions.h sasamples.o: sasamples.cpp sasamples.h misc/definitions.h \ - bits/bitbuffer.h bits/../misc/definitions.h bits/deltavector.h \ - bits/bitvector.h bits/bitbuffer.h misc/utils.h misc/definitions.h + bits/bitbuffer.h bits/../misc/definitions.h bits/deltavector.h \ + bits/bitvector.h bits/bitbuffer.h misc/utils.h misc/definitions.h bitvector.o: bits/bitvector.cpp bits/bitvector.h \ - bits/../misc/definitions.h bits/bitbuffer.h + bits/../misc/definitions.h bits/bitbuffer.h deltavector.o: bits/deltavector.cpp bits/deltavector.h bits/bitvector.h \ - bits/../misc/definitions.h bits/bitbuffer.h + bits/../misc/definitions.h bits/bitbuffer.h rlevector.o: bits/rlevector.cpp bits/rlevector.h bits/bitvector.h \ - bits/../misc/definitions.h bits/bitbuffer.h bits/../misc/utils.h \ - bits/../misc/definitions.h + bits/../misc/definitions.h bits/bitbuffer.h bits/../misc/utils.h \ + bits/../misc/definitions.h vectors.o: bits/vectors.cpp bits/vectors.h bits/deltavector.h \ - bits/bitvector.h bits/../misc/definitions.h bits/bitbuffer.h \ - bits/rlevector.h bits/../misc/utils.h bits/../misc/definitions.h + bits/bitvector.h bits/../misc/definitions.h bits/bitbuffer.h \ + bits/rlevector.h bits/../misc/utils.h bits/../misc/definitions.h parameters.o: misc/parameters.cpp misc/parameters.h misc/definitions.h utils.o: misc/utils.cpp misc/utils.h misc/definitions.h qsufsort.o: qsufsort/qsufsort.c qsufsort/qsufsort.h \ - qsufsort/../misc/definitions.h + qsufsort/../misc/definitions.h diff --git a/makefile b/makefile index f12c965..6a8e159 100644 --- a/makefile +++ b/makefile @@ -8,7 +8,7 @@ LIBSWCSA = swcsa/swcsa.a dcover_obs = dcover/difference_cover.o -TextCollection_obs = TextCollection.o TextCollectionBuilder.o TCImplementation.o Tools.o BitRank.o \ +TextCollection_obs = TextCollection.o TextCollectionBuilder.o FMIndexBuilder.o FMIndex.o Tools.o \ TextStorage.o ${LIBRLCSA} ${LIBCDSA} ${LIBLZTRIE} ${LIBSWCSA} TCDebug_obs = bittree.o rbtree.o dynFMI.o diff --git a/testTextCollection.cpp b/testTextCollection.cpp index 82bf79e..a19d2b2 100644 --- a/testTextCollection.cpp +++ b/testTextCollection.cpp @@ -40,7 +40,7 @@ int main() int i = 0 ,j = 0; int heap_base = HeapProfiler::GetHeapConsumption(); std::cerr << "Initial heap usage : " << heap_base << "\n"; - TextCollectionBuilder *tcb = new TextCollectionBuilder(5); + TextCollectionBuilder *tcb = TextCollectionBuilder::create(5); heap_base = HeapProfiler::GetHeapConsumption (); std::cerr << "Heap usage after InitTextCollection : " << heap_base << "\n"; Tools::StartTimer(); -- 2.17.1