GeneralizedLevenshteinMatchingAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/EpsilonNFA.h>
#include <string/LinearString.h>
#include <string/WildcardLinearString.h>
#include <stringology/matching/LevenshteinMatchingAutomaton.h>
 
 
namespace stringology {
 
namespace matching {
 
class GeneralizedLevenshteinMatchingAutomaton {
public:
    template < class SymbolType >
    static automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > construct(const string::LinearString < SymbolType > & pattern, unsigned int allowed_errors);
 
    template < class SymbolType >
    static automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > construct(const string::WildcardLinearString < SymbolType > & pattern, unsigned int allowed_errors);
};
 
 
template < class SymbolType >
automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > GeneralizedLevenshteinMatchingAutomaton::construct(const string::LinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > result = stringology::matching::LevenshteinMatchingAutomaton::construct(pattern, allowed_errors);
 
    for (unsigned int j = 0; j<allowed_errors; j++) {
        for (unsigned int i = j; i + 1 < pattern.getContent().size(); i++) {
            auto from = ext::make_pair(i, j);
            auto transpose_state = ext::make_pair(pattern.getContent().size()+1+i, j);
            auto to = ext::make_pair(i+2, j+1);
 
            result.addState(transpose_state);
            result.addTransition(from, pattern.getContent()[i+1], transpose_state);
            result.addTransition(transpose_state, pattern.getContent()[i], to);
        }
    }
 
    return result;
}
 
template < class SymbolType >
automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > GeneralizedLevenshteinMatchingAutomaton::construct(const string::WildcardLinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    auto result = stringology::matching::LevenshteinMatchingAutomaton::construct(pattern, allowed_errors);
 
    ext::set<SymbolType> alphabet_without_wildcard = pattern.getAlphabet();
    alphabet_without_wildcard.erase(pattern.getWildcardSymbol());
 
    for (unsigned int j = 0; j<allowed_errors; j++) {
        for (unsigned int i = j; i + 1 < pattern.getContent().size(); i++) {
            auto from = ext::make_pair(i, j);
            auto transpose_state = ext::make_pair(pattern.getContent().size()+1+i, j);
            auto to = ext::make_pair(i+2, j+1);
 
            result.addState(transpose_state);
            if (pattern.getContent()[i+1] == pattern.getWildcardSymbol() ) {
                for(const SymbolType & symbol : alphabet_without_wildcard) {
                    result.addTransition(from, symbol, transpose_state);
                }
            } else {
                result.addTransition(from, pattern.getContent()[i+1], transpose_state);
            }
 
            if (pattern.getContent()[i] == pattern.getWildcardSymbol()) {
                for(const SymbolType & symbol : alphabet_without_wildcard) {
                    result.addTransition(transpose_state, symbol, to);
                }
            } else {
                result.addTransition(transpose_state, pattern.getContent()[i], to);
            }
        }
    }
 
    return result;
}
 
 
} /* namespace matching */
 
} /* namespace stringology */