ApproximateCoversComputation.h

Go to the documentation of this file.

 
#pragma once
 
#include <string/LinearString.h>
#include <automaton/FSM/NFA.h>
#include <stringology/indexing/NondeterministicApproximateSuffixAutomatonForHammingDistance.h>
#include <numeric>
 
namespace stringology::cover {
 
class ApproximateCoversComputation {
public:
    template < class SymbolType >
    static ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > compute ( const string::LinearString < SymbolType > & pattern, unsigned k, bool restricted = false );
 
    template < class SymbolType >
    static ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > compute ( const string::LinearString < SymbolType > & pattern, unsigned k );
 
private:
    template < class SymbolType >
    static unsigned smallestDistanceCover ( ext::set < ext::pair < unsigned, unsigned > > subset, const ext::vector < SymbolType > & coverCandidate );
 
    template < class SymbolType >
    static ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > processState ( const ext::set < ext::pair < unsigned, unsigned > > & previousState, ext::vector < SymbolType > & lfactor, unsigned previousDepth, unsigned k, const automaton::NFA<SymbolType, ext::pair<unsigned, unsigned> > & approximateSuffixNDA, const string::LinearString < SymbolType > & pattern, bool restricted );
};
 
template < class SymbolType >
ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > ApproximateCoversComputation::compute ( const string::LinearString < SymbolType > & pattern, unsigned k ) {
    return ApproximateCoversComputation::compute ( pattern, k, false );
}
 
template < class SymbolType >
ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > ApproximateCoversComputation::compute ( const string::LinearString < SymbolType > & pattern, unsigned k, bool restricted ) {
    automaton::NFA < SymbolType, ext::pair < unsigned, unsigned > > approximateSuffixNDA = stringology::indexing::NondeterministicApproximateSuffixAutomatonForHammingDistance::construct ( pattern, k );
 
    ext::set < ext::pair < unsigned, unsigned > > initialState ( { approximateSuffixNDA.getInitialState ( ) } );
    ext::vector < SymbolType > lfactor;
    unsigned depth = 0;
 
    return processState ( initialState, lfactor, depth, k, approximateSuffixNDA, pattern, restricted );
}
 
template < class SymbolType >
ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > ApproximateCoversComputation::processState ( const ext::set < ext::pair < unsigned, unsigned > > & previousState, ext::vector < SymbolType > & lfactor, unsigned previousDepth, unsigned k, const automaton::NFA < SymbolType, ext::pair < unsigned, unsigned > > & approximateSuffixNDA, const string::LinearString < SymbolType > & pattern, bool restricted ) {
    ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > resultSet;
 
    for ( const SymbolType & symbol : pattern.getAlphabet ( ) ) {
        ext::set < ext::pair < unsigned, unsigned > > newState;
        unsigned depth = previousDepth + 1;
 
        for ( const auto & state : previousState ) {
            auto transition_range = approximateSuffixNDA.getTransitions ( ).equal_range ( ext::make_pair ( state, symbol ) );
            for ( const auto & it : transition_range ) {
                newState.insert ( it.second );
            }
        }
 
        bool levelZero = restricted && std::any_of ( newState.begin ( ), newState.end ( ), [] ( const ext::pair < unsigned, unsigned > & state ) { return state.second == 0; } );
 
        if ( newState.size ( ) > 1 && ( restricted == levelZero ) ) { // lfactor(newState) is a k-approximately repeating factor
            if ( newState.begin ( ) -> first == depth ) { // newState is k-approximate prefix
                lfactor.push_back ( symbol );
 
                if ( newState.rbegin ( ) -> first == pattern.getContent ( ).size ( ) ) { // The state is final ; safe (at least 2 elements)
                    bool isCover = true;
                    auto it = std::next ( newState.rbegin ( ) );
                    auto prev = newState.rbegin ( );
 
                    for ( ; it != newState.rend ( ); ++ it, ++ prev ) {
                        if ( prev -> first - it -> first > lfactor.size ( ) ) {
                            isCover = false;
                            break;
                        }
                    }
 
                    if ( isCover ) {
                        unsigned l = smallestDistanceCover ( newState, lfactor );
                        if  ( lfactor.size ( ) > l ) {
                            resultSet.insert ( ext::make_pair ( string::LinearString < SymbolType > ( lfactor ), l ) );
                        }
                    }
                }
 
                ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > resultSet2 = processState ( newState, lfactor, depth, k, approximateSuffixNDA, pattern, restricted );
                resultSet.insert ( resultSet2.begin ( ), resultSet2.end ( ) );
 
                lfactor.pop_back( );
            }
        }
    }
    return resultSet;
}
 
template < class SymbolType >
unsigned ApproximateCoversComputation::smallestDistanceCover ( ext::set < ext::pair < unsigned, unsigned > > subset, const ext::vector < SymbolType > & coverCandidate ) {
    unsigned lmin;
    unsigned lmax;
    unsigned l;
 
    lmin = std::max ( subset.begin ( ) -> second, subset.rbegin ( ) -> second );
    lmax = std::accumulate ( subset.begin ( ), subset.end ( ), subset.begin ( ) -> second, [ ] ( unsigned cMax, const ext::pair < unsigned, unsigned > & e ) { return std::max ( cMax, e.second ); } );
    l = lmax;
 
    while ( l > lmin ) {
        auto it = std::next ( subset.begin ( ) );
        auto prev = subset.begin ( );
        auto last = std::prev ( subset.end ( ) );
        while ( it != subset.end ( ) ) {
            // erase elements with level(e) = l, but not first nor last element
            if ( it != last && it -> second == l ) {
                it = subset.erase ( it );
            } else {
                if ( it -> first - prev -> first > coverCandidate.size ( ) ) // neighbouring depth is not <= coverCandidate.size
                    return l;
 
                prev = it ++;
            }
        }
 
        l = l - 1;
    }
 
    return l;
}
 
} /* namespace stringology::cover */