GeneralizedLevenshteinSequenceMatchingAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/EpsilonNFA.h>
#include <stringology/matching/GeneralizedLevenshteinMatchingAutomaton.h>
#include <string/LinearString.h>
 
 
namespace stringology {
 
namespace matching {
 
class GeneralizedLevenshteinSequenceMatchingAutomaton {
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> > GeneralizedLevenshteinSequenceMatchingAutomaton::construct(const string::LinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    auto result = stringology::matching::GeneralizedLevenshteinMatchingAutomaton::construct(pattern, allowed_errors);
 
    for (unsigned int j = 0; j<allowed_errors + 1; j++) {
        for (unsigned int i = j; i<pattern.getContent().size(); i++) {
            auto current_state = ext::make_pair(i, j);
 
            for (const SymbolType & symbol : pattern.getAlphabet()) {
                if (symbol != pattern.getContent()[i]) {
                    result.addTransition(current_state, symbol, current_state);
                }
            }
        }
    }
 
    for (unsigned int j = 0; j<allowed_errors; j++) {
        for (unsigned int i = j; i + 1 < pattern.getContent().size(); i++) {
            auto transpose_state = ext::make_pair(pattern.getContent().size()+1+i, j);
 
            for (const SymbolType & symbol : pattern.getAlphabet()) {
                if (symbol != pattern.getContent()[i]) {
                    result.addTransition(transpose_state, symbol, transpose_state);
                }
            }
        }
    }
 
    return result;
}
 
template < class SymbolType >
automaton::EpsilonNFA < SymbolType, ext::pair<unsigned int, unsigned int> > GeneralizedLevenshteinSequenceMatchingAutomaton::construct(const string::WildcardLinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    auto result = stringology::matching::GeneralizedLevenshteinMatchingAutomaton::construct(pattern, allowed_errors);
 
    const SymbolType& wildcard = pattern.getWildcardSymbol();
    ext::set<SymbolType> alphabet_without_wildcard = pattern.getAlphabet();
    alphabet_without_wildcard.erase(wildcard);
 
    for (unsigned int j = 0; j<allowed_errors + 1; j++) {
        for (unsigned int i = j; i<pattern.getContent().size(); i++) {
            auto current_state = ext::make_pair(i, j);
 
            if (pattern.getContent()[i] != wildcard) {
                for (const SymbolType & symbol : alphabet_without_wildcard) {
                    if (symbol != pattern.getContent()[i]) {
                        result.addTransition(current_state, symbol, current_state);
                    }
                }
            }
        }
    }
 
    for (unsigned int j = 0; j<allowed_errors; j++) {
        for (unsigned int i = j; i + 1 < pattern.getContent().size(); i++) {
            if (pattern.getContent()[i] == wildcard) {
                continue;
            }
 
            auto transpose_state = ext::make_pair(pattern.getContent().size()+1+i, j);
 
            for (const SymbolType & symbol : alphabet_without_wildcard) {
                if (symbol != pattern.getContent()[i]) {
                    result.addTransition(transpose_state, symbol, transpose_state);
                }
            }
        }
    }
 
    return result;
}
 
 
 
} /* namespace matching */
 
} /* namespace stringology */