+++ /dev/null
-/******************************************************************************
- * Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki *
- * *
- * *
- * 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. *
- *****************************************************************************/
-#include "TCImplementation.h"
-
-//#define DEBUG_MEMUSAGE
-#ifdef DEBUG_MEMUSAGE
-#include "HeapProfiler.h" // FIXME remove
-#endif
-
-#include <iostream>
-#include <map>
-#include <set>
-#include <vector>
-#include <utility>
-#include <stdexcept>
-#include <cassert>
-#include <cstring> // For strlen()
-using std::vector;
-using std::pair;
-using std::make_pair;
-using std::map;
-using std::string;
-namespace SXSI
-{
-
-// Save file version info
-const uchar TCImplementation::versionFlag = 8;
-
-/**
- * Constructor inits an empty dynamic FM-index.
- * Samplerate defaults to TEXTCOLLECTION_DEFAULT_SAMPLERATE.
- */
-TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerate_,
- unsigned numberOfTexts_, ulong maxTextLength_, ulong numberOfSamples_,
- CSA::DeltaVector & notIndexed, const string & niText, char tsType)
- : n(length), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
- suffixDocId(0), numberOfTexts(numberOfTexts_), maxTextLength(maxTextLength_), Doc(0)
-{
- makewavelet(bwt); // Deletes bwt!
- bwt = 0;
-
- // Make sampling tables
- maketables(numberOfSamples_, tsType, notIndexed, niText);
-}
-
-bool TCImplementation::EmptyText(DocId k) const
-{
- assert(k < (DocId)numberOfTexts);
- return false; // Empty texts are not indexed
-}
-
-uchar * TCImplementation::GetText(DocId k) const
-{
- assert(k < (DocId)numberOfTexts);
-
- return textStorage->GetText(k);
-/* TextPosition i = k;
-
- string result;
- // Reserve average string length to avoid reallocs
- result.reserve(n/numberOfTexts);
-
- uchar c = alphabetrank->access(i);
- while (c != '\0')
- {
- result.push_back(c);
- i = C[c]+alphabetrank->rank(c,i)-1;
-
- c = alphabetrank->access(i); // "next" char.
- }
-
- // Convert to uchar (FIXME return string?)
- i = result.size();
- uchar* res = new uchar[i+1];
- res[i] = '\0';
- for (ulong j = 0; j < i; ++j)
- res[i-j-1] = result[j];
- return res;*/
-}
-
-/*
- * Substring queries are supported via the pointer returned by TextStorage::GetText
-uchar* TCImplementation::GetText(DocId k, TextPosition i, TextPosition j) const
-{
- assert(k < (DocId)numberOfTexts);
- assert(j < (*textLength)[k]);
- assert(i <= j);
-
- ulong textRank = 0;
-
- // Start position of k'th text
- ulong start = (*textStartPos)[k];
-
- return Substring(i + start, j-i+1);
- }*/
-
-
-
-/******************************************************************
- * Existential queries
- */
-bool TCImplementation::IsPrefix(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return true;
-
- TextPosition sp = 0, ep = 0;
- Search(pattern, m, &sp, &ep);
-
- // Check for end-marker(s) in result interval
- if (CountEndmarkers(sp, ep))
- return true;
- return false;
-}
-
-bool TCImplementation::IsPrefix(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return true;
-
- TextPosition sp = 0, ep = 0;
- Search(pattern, m, &sp, &ep);
-
- // Check for end-marker(s) in result interval
- if (CountEndmarkers(sp, ep, begin, end))
- return true;
- return false;
-}
-
-
-bool TCImplementation::IsSuffix(uchar const *pattern) const
-{
- // Here counting is as fast as IsSuffix():
- if (CountSuffix(pattern) > 0)
- return true;
- return false;
-}
-
-bool TCImplementation::IsSuffix(uchar const *pattern, DocId begin, DocId end) const
-{
- // Here counting is as fast as IsSuffix():
- if (CountSuffix(pattern, begin, end) > 0)
- return true;
- return false;
-}
-
-bool TCImplementation::IsEqual(uchar const *pattern) const
-{
- TextPosition m = std::strlen((char *)pattern);
- if (m == 0)
- return false; // No empty texts exists
-
- TextPosition sp = 0, ep = 0;
- // Match including end-marker
- Search(pattern, m+1, &sp, &ep);
-
- // Check for end-marker(s) in result interval
- if (CountEndmarkers(sp, ep))
- return true;
- return false;
-}
-
-bool TCImplementation::IsEqual(uchar const *pattern, DocId begin, DocId end) const
-{
- TextPosition m = std::strlen((char *)pattern);
- if (m == 0)
- return false; // No empty texts exists
-
- TextPosition sp = 0, ep = 0;
- // Match including end-marker
- Search(pattern, m+1, &sp, &ep, begin, end);
-
- // Check for end-marker(s) in result interval
- if (CountEndmarkers(sp, ep))
- return true;
- return false;
-}
-
-bool TCImplementation::IsContains(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return true;
-
- TextPosition sp = 0, ep = 0;
- // Just check if pattern exists somewhere
- ulong count = Search(pattern, m, &sp, &ep);
-
- if (count > 0)
- return true;
- return false;
-}
-
-bool TCImplementation::IsContains(uchar const * pattern, DocId begin, DocId end) const
-{
- // Here counting is as fast as existential querying
- if (CountContains(pattern, begin, end) > 0)
- return true; // FIXME No need to filter result set
- return false;
-}
-
-bool TCImplementation::IsLessThan(uchar const * pattern) const
-{
- if (CountLessThan(pattern) > 0)
- return true;
- return false;
-}
-
-bool TCImplementation::IsLessThan(uchar const * pattern, DocId begin, DocId end) const
-{
- if (CountLessThan(pattern, begin, end) > 0)
- return true;
- return false;
-}
-
-/******************************************************************
- * Counting queries
- */
-ulong TCImplementation::Count(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return 0;
-
- TextPosition sp = 0, ep = 0;
- unsigned count = (unsigned) Search(pattern, m, &sp, &ep);
- return count;
-}
-
-unsigned TCImplementation::CountPrefix(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return numberOfTexts;
-
- TextPosition sp = 0, ep = 0;
- Search(pattern, m, &sp, &ep);
-
- // Count end-markers in result interval
- return CountEndmarkers(sp, ep);
-}
-
-unsigned TCImplementation::CountPrefix(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return numberOfTexts;
-
- TextPosition sp = 0, ep = 0;
- Search(pattern, m, &sp, &ep);
-
- // Count end-markers in result interval
- return CountEndmarkers(sp, ep, begin, end);
-}
-
-unsigned TCImplementation::CountSuffix(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return numberOfTexts;
-
- TextPosition sp = 0, ep = 0;
- // Search with end-marker
- unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep);
-
- return count;
-}
-
-unsigned TCImplementation::CountSuffix(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return numberOfTexts;
-
- TextPosition sp = 0, ep = 0;
- // Search with end-marker
- unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep, begin, end);
-
- return count;
-}
-
-unsigned TCImplementation::CountEqual(uchar const *pattern) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return 0; // No empty texts.
-
- TextPosition sp = 0, ep = 0;
- // Match including end-marker
- Search(pattern, m+1, &sp, &ep);
-
- // Count end-markers in result interval
- return CountEndmarkers(sp, ep);
-}
-
-unsigned TCImplementation::CountEqual(uchar const *pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return 0; // No empty texts.
-
- TextPosition sp = 0, ep = 0;
- // Match including end-marker
- Search(pattern, m+1, &sp, &ep, begin, end);
-
- // Count end-markers in result interval
- return CountEndmarkers(sp, ep); // Already within [begin, end]
-}
-
-unsigned TCImplementation::CountContains(uchar const * pattern) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return numberOfTexts; // Total number of texts.
-
- // Here counting is as slow as fetching the result set
- // because we have to filter out occ's that fall within same document.
- TextCollection::document_result result = Contains(pattern);
- return result.size();
-}
-
-unsigned TCImplementation::CountContains(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return numberOfTexts; // Total number of texts.
-
- // Here counting is as slow as fetching the result set
- // because we have to filter out occ's that fall within same document.
- TextCollection::document_result result = Contains(pattern, begin, end);
- return result.size();
-}
-
-// Less than or equal
-unsigned TCImplementation::CountLessThan(uchar const * pattern) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return 0; // No empty texts.
-
- TextPosition sp = 0, ep = 0;
- SearchLessThan(pattern, m, &sp, &ep);
-
- // Count end-markers in result interval
- return CountEndmarkers(sp, ep);
-}
-
-unsigned TCImplementation::CountLessThan(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return 0; // No empty texts.
-
- TextPosition sp = 0, ep = 0;
- SearchLessThan(pattern, m, &sp, &ep);
-
- // Count end-markers in result interval
- return CountEndmarkers(sp, ep, begin, end);
-}
-
-/**
- * Document reporting queries
- */
-TextCollection::document_result TCImplementation::Prefix(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all 1...k
-
- TextPosition sp = 0, ep = 0;
- Search(pattern, m, &sp, &ep);
-
- // Iterate through end-markers in [sp,ep]:
- return EnumerateEndmarkers(sp, ep);
-}
-
-TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all 1...k
-
- TextPosition sp = 0, ep = 0;
- Search(pattern, m, &sp, &ep);
-
- // Return end-markers in [sp,ep] and [begin, end]:
- return EnumerateEndmarkers(sp, ep, begin, end);
-}
-
-TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all 1...k
-
- TextPosition sp = 0, ep = 0;
- // Search with end-marker
- Search(pattern, m+1, &sp, &ep);
-
- TextCollection::document_result result;
- result.reserve(ep-sp+1); // Try to avoid reallocation.
-
- // Check each occurrence
- for (; sp <= ep; ++sp)
- {
- TextPosition i = sp;
-
- uchar c = alphabetrank->access(i);
- while (c != '\0' && !sampled->access(i))
- {
- i = C[c]+alphabetrank->rank(c,i)-1;
- c = alphabetrank->access(i);
- }
- // Assert: c == '\0' OR sampled->IsBitSet(i)
-
- if (c == '\0')
- {
- // Rank among the end-markers in BWT
- unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
- result.push_back(Doc->access(endmarkerRank));
- }
- else // Sampled position
- {
- DocId docId = (*suffixDocId)[sampled->rank1(i)-1];
- result.push_back(docId);
- }
- }
-
- return result;
-}
-
-TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all 1...k
-
- TextPosition sp = 0, ep = 0;
- // Search with end-marker
- Search(pattern, m+1, &sp, &ep, begin, end);
-
- TextCollection::document_result result;
- result.reserve(ep-sp+1); // Try to avoid reallocation.
-
- // Check each occurrence, already within [begin, end]
- for (; sp <= ep; ++sp)
- {
- TextPosition i = sp;
-
- uchar c = alphabetrank->access(i);
- while (c != '\0' && !sampled->access(i))
- {
- i = C[c]+alphabetrank->rank(c,i)-1;
- c = alphabetrank->access(i);
- }
- // Assert: c == '\0' OR sampled->IsBitSet(i)
-
- if (c == '\0')
- {
- // Rank among the end-markers in BWT
- unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
- result.push_back(Doc->access(endmarkerRank));
- }
- else // Sampled position
- {
- DocId docId = (*suffixDocId)[sampled->rank1(i)-1];
- result.push_back(docId);
- }
- }
-
- return result;
-}
-
-
-TextCollection::document_result TCImplementation::Equal(uchar const *pattern) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all empty texts
-
- TextPosition sp = 0, ep = 0;
- // Match including end-marker
- Search(pattern, m+1, &sp, &ep);
-
- // Report end-markers in result interval
- return EnumerateEndmarkers(sp, ep);
-}
-
-TextCollection::document_result TCImplementation::Equal(uchar const *pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char const *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all empty texts
-
- TextPosition sp = 0, ep = 0;
- // Match including end-marker
- Search(pattern, m+1, &sp, &ep, begin, end);
-
- // Report end-markers in result interval
- return EnumerateEndmarkers(sp, ep, begin, end);
-}
-
-
-TextCollection::document_result TCImplementation::Contains(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result();
-
- TextPosition sp = 0, ep = 0;
- // Search all occurrences
- Search(pattern, m, &sp, &ep);
-
- // We want unique document indentifiers, using std::set to collect them
- std::set<DocId> resultSet;
- EnumerateDocuments(resultSet, sp, ep);
-
- // Convert std::set to std::vector
- TextCollection::document_result result(resultSet.begin(), resultSet.end());
- return result;
-}
-
-TextCollection::document_result TCImplementation::Contains(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result();
-
- TextPosition sp = 0, ep = 0;
- // Search all occurrences
- Search(pattern, m, &sp, &ep);
-
- // We want unique document indentifiers, using std::set to collect them
- std::set<DocId> resultSet;
- EnumerateDocuments(resultSet, sp, ep, begin, end);
-
- // Convert std::set to std::vector
- TextCollection::document_result result(resultSet.begin(), resultSet.end());
- return result;
-}
-
-
-/**
- ***
-* * FIXME Lessthan or equal
- */
-TextCollection::document_result TCImplementation::LessThan(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // empty result set
-
- TextPosition sp = 0, ep = 0;
- SearchLessThan(pattern, m, &sp, &ep);
-
- // Report end-markers in result interval
- return EnumerateEndmarkers(sp, ep);
-}
-
-TextCollection::document_result TCImplementation::LessThan(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // empty result set
-
- TextPosition sp = 0, ep = 0;
- SearchLessThan(pattern, m, &sp, &ep);
-
- // Iterate through end-markers in [sp,ep] and [begin, end]:
- return EnumerateEndmarkers(sp, ep, begin, end);
-}
-
-
-TextCollection::document_result TCImplementation::KMismaches(uchar const * pattern, unsigned k) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // empty result set
-
- suffix_range_vector ranges;
- kmismatches(ranges, pattern, 0, n-1, m, k);
- std::set<DocId> resultSet;
-
- for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
- // Iterate through docs in [sp,ep]:
- EnumerateDocuments(resultSet, (*it).first, (*it).second);
-
- // Convert std::set to std::vector
- TextCollection::document_result result(resultSet.begin(), resultSet.end());
- return result;
-}
-
-TextCollection::document_result TCImplementation::KErrors(uchar const * pattern, unsigned k) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::document_result(); // empty result set
-
- suffix_range_vector ranges;
- ulong *dd = new ulong[m+1];
- for (ulong i=0;i<m+1;i++)
- dd[i]=i;
- kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
- delete [] dd;
-
- std::set<DocId> resultSet;
- for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
- // Iterate through docs in [sp,ep]:
- EnumerateDocuments(resultSet, (*it).first, (*it).second);
-
- // Convert std::set to std::vector
- TextCollection::document_result result(resultSet.begin(), resultSet.end());
- return result;
-}
-
-
-/**
- * Full result set queries
- */
-TextCollection::full_result TCImplementation::FullContains(uchar const * pattern) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return full_result(); // FIXME Throw exception?
-
- TextPosition sp = 0, ep = 0;
- // Search all occurrences
- Search(pattern, m, &sp, &ep);
-
- full_result result;
- result.reserve(ep-sp+1); // Try to avoid reallocation.
- EnumeratePositions(result, sp, ep);
-
- return result;
-}
-
-TextCollection::full_result TCImplementation::FullContains(uchar const * pattern, DocId begin, DocId end) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return full_result(); // FIXME Throw exception?
-
- TextPosition sp = 0, ep = 0;
- // Search all occurrences
- Search(pattern, m, &sp, &ep);
-
- full_result result;
- result.reserve(ep-sp+1); // Try to avoid reallocation.
- EnumeratePositions(result, sp, ep, begin, end);
-
- return result;
-}
-
-TextCollection::full_result TCImplementation::FullKMismatches(uchar const * pattern, unsigned k) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::full_result(); // empty result set
-
- suffix_range_vector ranges;
- ulong count = kmismatches(ranges, pattern, 0, n-1, m, k);
-
- TextCollection::full_result result;
- result.reserve(count); // avoid reallocation.
- for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
- // Iterate through docs in [sp,ep]:
- EnumeratePositions(result, (*it).first, (*it).second);
- return result;
-}
-
-TextCollection::full_result TCImplementation::FullKErrors(uchar const * pattern, unsigned k) const
-{
- TextPosition m = strlen((char *)pattern);
- if (m == 0)
- return TextCollection::full_result(); // empty result set
-
- suffix_range_vector ranges;
- ulong *dd = new ulong[m+1];
- for (unsigned i=0;i<m+1;i++)
- dd[i]=i;
- ulong count = kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
- delete [] dd;
-
- TextCollection::full_result result;
- result.reserve(count); // avoid reallocation.
- for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
- // Iterate through docs in [sp,ep]:
- EnumeratePositions(result, (*it).first, (*it).second);
- return result;
-}
-
-
-/**
- * Save index to a file handle
- *
- * 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;
- TextPosition n;
- unsigned samplerate;
- unsigned C[256];
- TextPosition bwtEndPos;
- static_sequence * alphabetrank;
- BSGAP *sampled;
- BlockArray *suffixes;
- BlockArray *suffixDocId;
- unsigned numberOfTexts;
- ulong maxTextLength;
- static_sequence *docId;
- */
-void TCImplementation::Save(FILE *file) const
-{
- // Saving version info:
- if (std::fwrite(&versionFlag, 1, 1, file) != 1)
- throw std::runtime_error("TCImplementation::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).");
- if (std::fwrite(&(this->samplerate), sizeof(unsigned), 1, file) != 1)
- throw std::runtime_error("TCImplementation::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).");
-
- if (std::fwrite(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
- throw std::runtime_error("TCImplementation::Save(): file write error (bwt end position).");
-
- alphabetrank->save(file);
- sampled->save(file);
- suffixes->Save(file);
- suffixDocId->Save(file);
-
- if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
- throw std::runtime_error("TCImplementation::Save(): file write error (numberOfTexts).");
- if (std::fwrite(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("TCImplementation::Save(): file write error (maxTextLength).");
-
- Doc->save(file);
- textStorage->Save(file);
- fflush(file);
-}
-
-
-/**
- * Load index from a file handle
- *
- * Throws a std::runtime_error exception on i/o error.
- * For more info, see TCImplementation::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_)
- : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
- suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0)
-{
- uchar verFlag = 0;
- if (std::fread(&verFlag, 1, 1, file) != 1)
- throw std::runtime_error("TCImplementation::Load(): file read error (version flag).");
- if (verFlag != TCImplementation::versionFlag)
- throw std::runtime_error("TCImplementation::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).");
- if (std::fread(&samplerate, sizeof(unsigned), 1, file) != 1)
- throw std::runtime_error("TCImplementation::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).");
-
- if (std::fread(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
- throw std::runtime_error("TCImplementation::Load(): file read error (bwt end position).");
-
- alphabetrank = static_sequence::load(file);
- if (im == index_mode_text_only) { delete alphabetrank; alphabetrank = 0; }
-
- sampled = static_bitsequence::load(file);
- if (im == index_mode_text_only) { delete sampled; sampled = 0; }
- suffixes = new BlockArray(file);
- if (im == index_mode_text_only) { delete suffixes; suffixes = 0; }
- suffixDocId = new BlockArray(file);
- 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).");
- if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
- throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength).");
-
- Doc = new ArrayDoc(file); //static_sequence::load(file);
- if (im == index_mode_text_only) { delete Doc; Doc = 0; }
-
- textStorage = TextStorage::Load(file);
-
- // FIXME Construct data structures with new samplerate
- //maketables();
-}
-
-
-
-/**
- * Rest of the functions follow...
- */
-ulong TCImplementation::searchPrefix(uchar const *pattern, ulong i, ulong *sp, ulong *ep) const
-{
- int c;
- while (*sp<=*ep && i>=1)
- {
- c = (int)pattern[--i];
- *sp = C[c]+alphabetrank->rank(c,*sp-1);
- *ep = C[c]+alphabetrank->rank(c,*ep)-1;
- }
- if (*sp<=*ep)
- return *ep - *sp + 1;
- else
- return 0;
-}
-
-
-ulong TCImplementation::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)
- {
- result.push_back(std::make_pair(sp,ep));
- return ep-sp+1;
- }
- int c;
- ulong spnew;
- ulong epnew;
- int knew;
- ulong sum=0;
- if (k==0)
- {
- sum = searchPrefix(pattern, j, &sp, &ep);
- if (sp<=ep)
- result.push_back(std::make_pair(sp, ep));
- return sum;
- }
- vector<int> chars = alphabetrank->accessAll(sp, ep);
- for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
- {
- if (*it == 0)
- continue; // skip '\0'
- c = *it;
- spnew = C[c]+alphabetrank->rank(c,sp-1);
- epnew = C[c]+alphabetrank->rank(c,ep)-1;
- if (c!=pattern[j-1]) knew = (int)k-1; else knew = k;
- if (knew>=0) sum += kmismatches(result, pattern, spnew, epnew, j-1, knew);
- }
- return sum;
-}
-
-//first call kerrors(pattern,1,n,m+k,k,d,m), where d[i]=i
-ulong TCImplementation::kerrors(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k, ulong const *d, ulong m) const
-{
- ulong sum=0;
- if (d[m]<=k) // range of suffixes with at most k-errors found
- {
- if (sp<=ep)
- result.push_back(std::make_pair(sp, ep));
- sum += (sp<=ep)?ep-sp+1:0ul;
- }
- if (sp>ep || j==0)
- return sum;
- ulong *dnew = new ulong[m+1];
- int c;
- ulong spnew;
- ulong p,lowerbound;
- ulong epnew;
- vector<int> chars = alphabetrank->accessAll(sp, ep);
- for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
- {
- if (*it == 0)
- continue; // skip '\0'
- c = *it;
- spnew = C[c]+alphabetrank->rank(c,sp-1);
- epnew = C[c]+alphabetrank->rank(c,ep)-1;
- if (spnew>epnew) continue;
- dnew[0]=m+k-j+1;
- lowerbound=k+1;
- for (p=1; p<=m; p++) {
- dnew[p]=myminofthree(d[p]+1,dnew[p-1]+1,(c==pattern[m-p])?d[p-1]:(d[p-1]+1));
- if (dnew[p]<lowerbound)
- lowerbound = dnew[p];
- }
- if (lowerbound<=k)
- sum += kerrors(result, pattern, spnew, epnew, j-1, k,dnew,m);
- }
- delete [] dnew;
- return sum;
-}
-
-
-ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
-{
- // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
- int c = (int)pattern[m-1];
- TextPosition i=m-1;
- TextPosition sp = C[c];
- TextPosition ep = C[c+1]-1;
- while (sp<=ep && i>=1)
- {
-// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
- c = (int)pattern[--i];
- sp = C[c]+alphabetrank->rank(c,sp-1);
- ep = C[c]+alphabetrank->rank(c,ep)-1;
- }
- *spResult = sp;
- *epResult = ep;
- if (sp<=ep)
- return ep - sp + 1;
- else
- return 0;
-}
-
-ulong TCImplementation::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];
- assert(c == 0); // Start from endmarkers
- TextPosition i=m-1;
- TextPosition sp = begin;
- TextPosition ep = end;
- while (sp<=ep && i>=1)
- {
-// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
- c = (int)pattern[--i];
- sp = C[c]+alphabetrank->rank(c,sp-1);
- ep = C[c]+alphabetrank->rank(c,ep)-1;
- }
- *spResult = sp;
- *epResult = ep;
- if (sp<=ep)
- return ep - sp + 1;
- else
- return 0;
-}
-
-
-ulong TCImplementation::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];
- TextPosition i=m-1;
- TextPosition sp = 1;
- TextPosition ep = C[c+1]-1;
- while (sp<=ep && i>=1)
- {
-// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
- c = (int)pattern[--i];
- uint result = alphabetrank->rankLessThan(c,ep);
- if (result == ~0u)
- ep = 0;
- else
- ep = C[c]+result-1;
- }
- *spResult = sp;
- *epResult = ep;
- if (sp<=ep)
- return ep - sp + 1;
- else
- return 0;
-}
-
-
-TCImplementation::~TCImplementation() {
- delete alphabetrank;
- delete sampled;
- delete suffixes;
- delete suffixDocId;
- delete Doc;
- delete textStorage;
-}
-
-void TCImplementation::makewavelet(uchar *bwt)
-{
- ulong i, min = 0,
- max;
- for (i=0;i<256;i++)
- C[i]=0;
- for (i=0;i<n;++i)
- C[(int)bwt[i]]++;
- for (i=0;i<256;i++)
- if (C[i]>0) {min = i; break;}
- for (i=255;i>=min;--i)
- if (C[i]>0) {max = i; break;}
-
- ulong prev=C[0], temp;
- C[0]=0;
- for (i=1;i<256;i++) {
- temp = C[i];
- C[i]=C[i-1]+prev;
- prev = temp;
- }
-// this->codetable = node::makecodetable(bwt,n);
-// alphabetrank = new THuffAlphabetRank(bwt,n, this->codetable,0);
-// delete [] bwt;
- //alphabetrank = new RLWaveletTree(bwt, n); // Deletes bwt!
-// std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "max heap usage before WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
- HeapProfiler::ResetMaxHeapConsumption();
-#endif
-
- alphabet_mapper * am = new alphabet_mapper_none();
- static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(8); //rrr02(8); // FIXME samplerate?
- wt_coder * wtc = new wt_coder_huff(bwt,n,am);//binary(bwt,n,am); // FIXME Huffman shape
- alphabetrank = new static_sequence_wvtree(bwt,n,wtc,bmb,am);
- delete bmb;
- bwt = 0; // already deleted
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "heap usage after WT: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
- std::cerr << "max heap usage after WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
-#endif
-}
-
-void TCImplementation::maketables(ulong sampleLength, char tsType, CSA::DeltaVector & notIndexed, const string & niText)
-{
- // Calculate BWT end-marker position (of last inserted text)
- {
- ulong i = 0;
- uint alphabetrank_i_tmp = 0;
- uchar c = alphabetrank->access(i, alphabetrank_i_tmp);
- while (c != '\0')
- {
- i = C[c]+alphabetrank_i_tmp-1;
- c = alphabetrank->access(i, alphabetrank_i_tmp);
- }
-
- this->bwtEndPos = i;
- }
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "heap usage before BWT traverse: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
- HeapProfiler::ResetMaxHeapConsumption();
-#endif
-
- // Build up array for text starting positions
-// BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n));
-// (*textStartPos)[0] = 0;
-
- // Mapping from end-markers to doc ID's:
- unsigned logNumberOfTexts = Tools::CeilLog2(numberOfTexts);
-// uint *endmarkerDocId = new uint[(numberOfTexts * logNumberOfTexts)/(8*sizeof(uint)) + 1];
- BlockArray *endmarkerDocId = new BlockArray(numberOfTexts, logNumberOfTexts);
-
- BlockArray* positions = new BlockArray(sampleLength, Tools::CeilLog2(this->n));
- uint *sampledpositions = new uint[n/(sizeof(uint)*8)+1];
- for (ulong i = 0; i < n / (sizeof(uint)*8) + 1; i++)
- sampledpositions[i] = 0;
-
- ulong x,p=bwtEndPos;
- ulong sampleCount = 0;
- // Keeping track of text position of prev. end-marker seen
- ulong posOfSuccEndmarker = n-1;
- DocId textId = numberOfTexts;
- ulong ulongmax = 0;
- ulongmax--;
- uint alphabetrank_i_tmp =0;
-
- // Text length = n + number of bytes not indexed.
- TextStorageBuilder tsbuilder(n + niText.length());
- ulong tsb_i = n + niText.length(); // Iterator from text length to 0.
- string::const_reverse_iterator nit_i = niText.rbegin(); // Iterator through non-indexed texts
-
- for (ulong i=n-1;i<ulongmax;i--) {
- // i substitutes SA->GetPos(i)
- x=(i==n-1)?0:i+1;
-
- uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
-
- tsbuilder[--tsb_i] = c; // Build TextStorage
-
- if ((posOfSuccEndmarker - i) % samplerate == 0 && c != '\0')
- {
- set_field(sampledpositions,1,p,1);
- (*positions)[sampleCount] = p;
- sampleCount ++;
- }
-
- if (c == '\0')
- {
- unsigned prevTextId = textId; // Cache textId value.
- --textId;
- /**
- * At first c == '\0' it holds that (prevTextId == numberOfTexts), thus,
- * we have to search for the first text that is actually *indexed*
- * to get correct prevTextId.
- */
- if (prevTextId == numberOfTexts)
- {
- prevTextId = 0;
- while (notIndexed.isSet(prevTextId))
- ++ prevTextId;
- // Now prevTextId points to the first indexed Doc ID.
- }
-
- /**
- * Insert non-indexed texts
- */
- while (notIndexed.isSet(textId))
- {
- do {
- tsbuilder[tsb_i] = *nit_i;
- -- tsb_i;
- ++ nit_i;
- } while (nit_i != niText.rend() && *nit_i != '\0');
-
- tsbuilder[tsb_i] = '\0';
-
- if (textId == 0)
- break;
- --textId;
- }
-
- // Record the order of end-markers in BWT:
- ulong endmarkerRank = alphabetrank_i_tmp - 1;
- //set_field(endmarkerDocId, logNumberOfTexts, endmarkerRank, (textId + 1) % numberOfTexts);
- (*endmarkerDocId)[endmarkerRank] = prevTextId % numberOfTexts;
-
- // Store text length and text start position:
- if (textId < (DocId)numberOfTexts - 1)
- {
-// (*textStartPos)[textId + 1] = x; // x-1 is text position of end-marker.
-
- posOfSuccEndmarker = i;
- }
-
- // LF-mapping from '\0' does not work with this (pseudo) BWT.
- // Correct LF-mapping to the last char of the previous text:
- p = textId - notIndexed.rank(textId);
- }
- else // Now c != '\0', do LF-mapping:
- p = C[c]+alphabetrank_i_tmp-1;
- }
- while (textId > 0 && notIndexed.isSet(textId-1))
- {
- do {
- -- tsb_i;
- tsbuilder[tsb_i] = *nit_i;
- ++ nit_i;
- } while (nit_i != niText.rend() && *nit_i != '\0');
- --textId;
- }
- assert(textId == 0);
- assert(tsb_i == 0);
- assert(nit_i == niText.rend());
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "heap usage before tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
- HeapProfiler::ResetMaxHeapConsumption();
-#endif
-
- textStorage = tsbuilder.InitTextStorage(tsType);
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "heap usage after tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
- HeapProfiler::ResetMaxHeapConsumption();
-#endif
-
- sampled = new static_bitsequence_rrr02(sampledpositions, n, 16);
- delete [] sampledpositions;
- assert(sampleCount == sampleLength);
- assert(sampled->rank1(n-1) == sampleLength);
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "heap usage after sampled bit vector: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
- HeapProfiler::ResetMaxHeapConsumption();
-#endif
-
- // Suffixes store an offset from the text start position
- suffixes = new BlockArray(sampleLength, Tools::CeilLog2(maxTextLength));
- suffixDocId = new BlockArray(sampleLength, Tools::CeilLog2(numberOfTexts));
-
- x = n + niText.length() - 2;
- textId = numberOfTexts - 1;
- posOfSuccEndmarker = x + 1;
- for(ulong i = 0; i < sampleLength; i ++) {
- // Find next sampled text position
- while ((posOfSuccEndmarker - x) % samplerate != 0
- || notIndexed.isSet(textId)) // Loop over non-indexed
- {
- --x;
- assert(x != ~0lu);
- if (textStorage->IsEndmarker(x))
- {
- posOfSuccEndmarker = x--;
- -- textId;
- }
- }
- assert((*positions)[i] < n);
- ulong j = sampled->rank1((*positions)[i]);
-
- assert(j != 0); // if (j==0) j=sampleLength;
-
- TextPosition textPos = (x==n-1)?0:x+1;
- (*suffixDocId)[j-1] = textId; // textStorage->DocIdAtTextPos(textPos);
- assert(textStorage->DocIdAtTextPos(textPos) == textId);
-
- assert((*suffixDocId)[j-1] < numberOfTexts);
- // calculate offset from text start:
- (*suffixes)[j-1] = textPos - textStorage->TextStartPos((*suffixDocId)[j-1]);
- --x;
- if (x != ~0lu && textStorage->IsEndmarker(x))
- {
- posOfSuccEndmarker = x--;
- -- textId;
- }
- }
-
- delete positions;
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "heap usage after sampled arrays: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " << HeapProfiler::GetHeapConsumption() << " / " << HeapProfiler::GetMaxHeapConsumption() << std::endl;
- HeapProfiler::ResetMaxHeapConsumption();
-#endif
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "max heap usage before Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
- HeapProfiler::ResetMaxHeapConsumption();
-#endif
-
- /*alphabet_mapper * am = new alphabet_mapper_none();
- static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(32); // FIXME samplerate?
- Doc = new static_sequence_wvtree_noptrs(endmarkerDocId, numberOfTexts, logNumberOfTexts, bmb, am, true);
- delete bmb;*/
- // delete [] endmarkerDocId; // already deleted in static_sequence_wvtree_noptrs!
-
- Doc = new ArrayDoc(endmarkerDocId);
-
-#ifdef DEBUG_MEMUSAGE
- std::cerr << "max heap usage after Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
-#endif
-}
-
-
-/**
- * Finds document identifier for given text position
- *
- * 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
-{
- assert(i < n);
-
- DocId a = 0;
- DocId b = numberOfTexts - 1;
- while (a < b)
- {
- DocId c = a + (b - a)/2;
- if ((*textStartPos)[c] > i)
- b = c - 1;
- else if ((*textStartPos)[c+1] > i)
- return c;
- else
- a = c + 1;
- }
-
- assert(a < (DocId)numberOfTexts);
- assert(i >= (*textStartPos)[a]);
- assert(i < (a == (DocId)numberOfTexts - 1 ? n : (*textStartPos)[a+1]));
- return a;
-}
-
-
-} // namespace SXSI
-
projects / SXSI / TextCollection.git / blobdiff