HammingMatchingAutomaton.h

Go to the documentation of this file.

 
/*
*/
 
#pragma once
 
#include <automaton/FSM/NFA.h>
#include <string/LinearString.h>
#include <string/WildcardLinearString.h>
 
namespace stringology {
 
namespace matching {
 
class HammingMatchingAutomaton {
public:
    template < class SymbolType >
    static automaton::NFA < SymbolType, ext::pair<unsigned int, unsigned int> > construct(const string::LinearString < SymbolType > & pattern, unsigned int allowed_errors);
 
    template < class SymbolType >
    static automaton::NFA < SymbolType, ext::pair<unsigned int, unsigned int> > construct(const string::WildcardLinearString < SymbolType > & pattern, unsigned int allowed_errors);
};
 
template < class SymbolType >
automaton::NFA < SymbolType, ext::pair<unsigned int, unsigned int> > HammingMatchingAutomaton::construct(const string::LinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    auto initial_state = ext::make_pair(0, 0);
 
    automaton::NFA < SymbolType, ext::pair<unsigned int, unsigned int > > result ( initial_state );
    result.setInputAlphabet(pattern.getAlphabet());
 
    // add k+1 paralel automatas (sfoeco type = exact matching) (where k is allowed_errors)
    for (unsigned int j = 0; j<allowed_errors + 1; j++) {
        for (unsigned int i = j; i<pattern.getContent().size() + 1; i++) {
            result.addState(ext::make_pair(i, j));
            if (i == pattern.getContent().size()) {
                result.addFinalState(ext::make_pair(i, j));
            }
        }
    }
 
    for (const SymbolType& symbol : pattern.getAlphabet()) {
        result.addTransition(initial_state, symbol, initial_state);
    }
 
    for (unsigned int j = 0; j < allowed_errors + 1; 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);
            result.addTransition(from, pattern.getContent()[i], to);
        }
    }
 
    // add diagonal addTransition
    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);
 
            for ( const SymbolType & symbol : pattern.getAlphabet()) {
                if (symbol != pattern.getContent()[i]) {
                    result.addTransition(from, symbol, to);
                }
            }
        }
    }
 
    // remove all inaccessible states from state
    return result;
}
 
 
template < class SymbolType >
automaton::NFA < SymbolType, ext::pair<unsigned int, unsigned int> > HammingMatchingAutomaton::construct(const string::WildcardLinearString < SymbolType > & pattern, unsigned int allowed_errors) {
    auto initial_state = ext::make_pair(0, 0);
 
    automaton::NFA < SymbolType, ext::pair<unsigned int, unsigned int > > result ( initial_state );
    result.setInputAlphabet(pattern.getAlphabet());
 
    const SymbolType & wildcard = pattern.getWildcardSymbol();
    ext::set<SymbolType> alphabet_without_wildcard = pattern.getAlphabet();
    alphabet_without_wildcard.erase(wildcard);
 
    // add k+1 paralel automatas (sfoeco type = exact matching) (where k is allowed_errors)
    for (unsigned int j = 0; j<allowed_errors + 1; j++) {
        for (unsigned int i = j; i<pattern.getContent().size() + 1; i++) {
            result.addState(ext::make_pair(i, j));
            if (i == pattern.getContent().size()) {
                result.addFinalState(ext::make_pair(i, j));
            }
        }
    }
 
    for (const SymbolType& symbol : alphabet_without_wildcard) {
        result.addTransition(initial_state, symbol, initial_state);
    }
 
    for (unsigned int j = 0; j < allowed_errors + 1; 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);
            if (pattern.getContent()[i] == pattern.getWildcardSymbol()) {
                for (const SymbolType& symbol : alphabet_without_wildcard) {
                    result.addTransition(from, symbol, to);
                }
            } else {
                result.addTransition(from, pattern.getContent()[i], to);
            }
        }
    }
 
    // add diagonal addTransition
    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);
 
            if (pattern.getContent()[i] != wildcard) {
                for ( const SymbolType & symbol : alphabet_without_wildcard ) {
                    if (symbol != pattern.getContent()[i]) {
                        result.addTransition(from, symbol, to);
                    }
                }
            }
        }
    }
 
    return result;
}
 
} /* namespace matching */
 
} /* namespace stringology */