LevenshteinBitParalelism.h

Go to the documentation of this file.

 
#pragma once
 
#include <exception>
#include <string/LinearString.h>
 
#include "BitParalelism.h"
 
namespace stringology {
 
namespace simulations {
 
class LevenshteinBitParalelism {
public:
    template <class SymbolType>
    static ext::set<unsigned int> search(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern, unsigned int errors);
};
 
 
template <class SymbolType>
ext::set<unsigned int> LevenshteinBitParalelism::search(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern, unsigned int errors) {
  // preparation stage
  ext::set<SymbolType> common_alphabet = text.getAlphabet();
  common_alphabet.insert(pattern.getAlphabet().begin(), pattern.getAlphabet().end());
 
  ext::map<SymbolType, ext::vector<bool> > D_vectors = BitParalelism::constructDVectors(common_alphabet, pattern);
 
  ext::vector<bool> V_vector (pattern.getContent().size(), false);
  V_vector[pattern.getContent().size() - 1] = true;
 
  // computation part
  ext::set<unsigned int> result;
 
  ext::vector<ext::vector<bool> > B_vectors;
  for(unsigned int i=0; i<=errors; i++) {
    B_vectors.push_back(ext::vector<bool>(pattern.getContent().size(), false));
  }
 
  for(unsigned int l = 0; l <= errors; l++) {
    for(unsigned int j = l; j <= pattern.getContent().size(); j++) {
      B_vectors[l][j] = true;
    }
  }
 
  // 0-th column
  ext::vector<bool> b0 = ext::vector < bool > ( pattern.getContent().size(), true );
  for(unsigned int j=1; j<=errors; j++) {
    b0 <<= 1;
    if ( ! b0 [ pattern.getContent ( ).size ( ) - 1 ] ) {
      result.insert(0);
      break;
    }
  }
 
 
  for(unsigned int i=0; i<text.getContent().size(); i++) {
    ext::vector< ext::vector<bool> > previous_B_vectors = B_vectors;
 
    B_vectors[0] = (B_vectors[0] << 1) | D_vectors[text.getContent()[i]];
 
    for(unsigned int j=1; j<=errors; j++) {
      B_vectors[j] = ((previous_B_vectors[j] << 1) | D_vectors[text.getContent()[i]]) &
                     ( (previous_B_vectors[j-1] & B_vectors[j-1]) << 1) &
                     ( previous_B_vectors[j-1] | V_vector );
    }
 
    for (const auto & data : B_vectors) {
      if ( ! data [ pattern.getContent ( ).size ( ) - 1 ] ) {
        result.insert(i+1);
        break;
      }
    }
  }
 
  return result;
}
 
} // namespace simulations
 
} // namespace stringology