LevenshteinDynamicProgramming.h

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <limits.h>
 
#include <string/LinearString.h>
 
namespace stringology {
 
namespace simulations {
 
class LevenshteinDynamicProgramming {
public:
    template <class SymbolType>
    static ext::vector<ext::vector<unsigned int>> compute_table(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern);
 
    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::vector<ext::vector<unsigned int>> LevenshteinDynamicProgramming::compute_table(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern) {
  ext::vector< ext::vector <unsigned int> > table =
    ext::vector<ext::vector<unsigned int> > (
      pattern.getContent().size() + 1,
      ext::vector<unsigned int>(text.getContent().size() + 1, 0)
    );
 
  for(unsigned int j = 0; j <= pattern.getContent().size(); j++) {
    table[j][0] = j;
  }
 
  for(unsigned int i = 1; i<=text.getContent().size(); i++) {
    for(unsigned int j = 1; j<=pattern.getContent().size(); j++) {
        std::vector < unsigned int > values;
      if(pattern.getContent()[j-1] == text.getContent()[i-1]) {
        values.push_back ( table[j-1][i-1] );
      } else {
        values.push_back ( table[j-1][i-1] + 1 );
      }
 
      if(j < pattern.getContent().size()) {
        values.push_back ( table[j][i-1] + 1 );
      }
 
      values.push_back ( table[j-1][i] + 1 );
 
      table[j][i] = * std::min_element ( values.begin ( ), values.end ( ) );
    }
  }
 
  return table;
}
 
template <class SymbolType>
ext::set<unsigned int> LevenshteinDynamicProgramming::search(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern, unsigned int errors) {
  auto table = LevenshteinDynamicProgramming::compute_table(text, pattern);
 
  ext::set<unsigned int> result;
 
  //std::cerr << table << std::endl;
 
  for ( unsigned int i = 0; i <= text.getContent().size(); i++ ) {
    if ( table[pattern.getContent().size()][i] <= errors ) {
      result.insert(i);
    }
  }
 
  return result;
}
 
 
 
} // namespace simulations
 
} // namespace stringology