LevenshteinMatchingAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/simplify/UnreachableStatesRemover.h>
#include <string/LinearString.h>
#include <string/WildcardLinearString.h>
#include <stringology/matching/HammingMatchingAutomaton.h>
 
 
namespace stringology {
 
namespace matching {
 
class LevenshteinMatchingAutomaton {
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> > LevenshteinMatchingAutomaton::construct(const string::LinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    auto hamming_matching_automaton = stringology::matching::HammingMatchingAutomaton::construct(pattern, allowed_errors);
 
    automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > result (hamming_matching_automaton);
 
    for (unsigned int j = 0; j<allowed_errors; j++) {
        for (unsigned int i = j; i<pattern.getContent().size(); i++) {
            auto from = ext::make_pair(i, j);
            auto to = ext::make_pair(i + 1, j + 1);
 
            // add diagonal transition representing deletion
            result.addTransition(from, to);
 
            if (i == j) {
                continue;
            }
 
            to = ext::make_pair(i, j + 1);
 
            for (const SymbolType& symbol : pattern.getAlphabet()) {
                // add horizontal transition representing insertion
                result.addTransition(from, symbol, to);
            }
        }
    }
 
    return result;
}
 
 
template < class SymbolType >
automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > LevenshteinMatchingAutomaton::construct(const string::WildcardLinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    auto hamming_matching_automaton = stringology::matching::HammingMatchingAutomaton::construct(pattern, allowed_errors);
 
    automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > result (hamming_matching_automaton);
 
    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<pattern.getContent().size(); i++) {
            auto from = ext::make_pair(i, j);
            auto to = ext::make_pair(i + 1, j + 1);
 
            // add diagonal transition representing deletion
            result.addTransition(from, to);
 
            if (i == j) {
                continue;
            }
 
            to = ext::make_pair(i, j + 1);
 
            for (const SymbolType& symbol : alphabet_without_wildcard) {
                // add horizontal transition representing insertion
                result.addTransition(from, symbol, to);
            }
        }
    }
 
    return result;
}
 
 
 
} /* namespace matching */
 
} /* namespace stringology */