ApproximateSeedComputation.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/set>
#include <alib/pair>
#include <stringology/seed/DeterministicApproximateSuffixAutomatonForHammingDistanceFactory.h>
#include <string/LinearString.h>
#include <string/transform/StringReverse.h>
 
namespace stringology::seed
{
    using State = ext::set < ext::pair < unsigned, unsigned > >;
 
    class ApproximateSeedComputation
    {
    private:
        template<class SymbolType>
        static bool existsPrefix( const string::LinearString < SymbolType > & potentialSeed, const State & newState, unsigned distance,
                                  const automaton::DFA < SymbolType, State > & dSuffix,
                                  const string::LinearString < SymbolType > & pattern )
        {
            if ( dSuffix.getFinalStates().count( newState ) && newState.rbegin()->second <= distance )
                return true;
 
            auto statePtr = & dSuffix.getInitialState();
            for ( size_t pi = 0; pi < potentialSeed.size(); ++pi )
            {
                if ( pi >= pattern.getContent().size() - newState.rbegin()->first
                    && dSuffix.getFinalStates().count( *statePtr )
                    && ( *statePtr ).rbegin()->second <= distance )
                    return true;
 
                auto it_range = dSuffix.getTransitionsFromState( *statePtr );
                for ( auto tr = it_range.begin(); tr != it_range.end(); ++tr )
                {
                    if ( tr->first.second == potentialSeed.getContent().at( pi ) )
                    {
                        statePtr = & tr->second;
                        break;
                    }
                }
            }
            return false;
        }
 
        template<class SymbolType>
        static bool existsSuffix( const string::LinearString < SymbolType > & potentialSeed, const State & newState, unsigned distance,
                                 const automaton::DFA < SymbolType, State > & dSuffixReversed )
        {
            auto reversedPotentialSeed = string::transform::StringReverse::reverse ( potentialSeed );
 
            if ( newState.begin()->first == potentialSeed.size() && newState.begin()->second <= distance )
                return true;
 
 
            auto statePtr = & dSuffixReversed.getInitialState();
            for ( size_t si = 0; si < reversedPotentialSeed.size(); ++si )
            {
                if( si >= newState.begin()->first - potentialSeed.size()
                   && dSuffixReversed.getFinalStates().count( *statePtr )
                   && ( *statePtr ).rbegin()->second <= distance )
                    return true;
 
                auto it_range = dSuffixReversed.getTransitionsFromState( *statePtr );
                for ( auto tr = it_range.begin(); tr != it_range.end(); ++tr )
                {
                    if ( tr->first.second == reversedPotentialSeed.getContent().at( si ) )
                    {
                        statePtr = & tr->second;
                        break;
                    }
                }
            }
            return false;
        }
 
        template<class SymbolType>
        static bool coversMiddle( const string::LinearString < SymbolType > & potentialSeed, const State & newState )
        {
            auto firstIt = newState.begin();
            firstIt++;
            for ( auto secondIt = newState.begin(); firstIt != newState.end(); ++firstIt, ++secondIt )
            {
                if ( firstIt->first - secondIt->first > potentialSeed.size() )
                    return false;
            }
            return true;
        }
 
        template<class SymbolType>
        static bool isSeed( const string::LinearString < SymbolType > & potentialSeed, const State & newState, unsigned distance,
                            const automaton::DFA < SymbolType, State > & dSuffix,
                            const automaton::DFA < SymbolType, State > & dSuffixReversed,
                            const string::LinearString < SymbolType > & pattern )
        {
            if ( ! potentialSeed.empty()
                && coversMiddle( potentialSeed, newState )
                && existsPrefix( potentialSeed, newState, distance, dSuffix, pattern )
                && existsSuffix( potentialSeed, newState, distance, dSuffixReversed ) )
                return true;
            else
                return false;
        }
 
        template<class SymbolType>
        static unsigned
        smallestDistanceSeed( const string::LinearString < SymbolType > & seed, const State & newState, unsigned distance,
                              const automaton::DFA < SymbolType, State > & dSuffix,
                              const automaton::DFA < SymbolType, State > & dSuffixReversed,
                              const string::LinearString < SymbolType > & pattern )
        {
            if ( distance == 0 )
                return distance;
 
            unsigned dist = distance - 1;
            auto state = newState;
            for ( auto it = state.begin(); it != state.end(); )
            {
                if ( it->second > dist )
                    it = state.erase( it );
                else
                    it++;
            }
            while ( ! state.empty() && isSeed( seed, state, dist, dSuffix, dSuffixReversed, pattern ) )
            {
                if ( dist == 0 )
                    return dist;
 
                dist = dist - 1;
                for ( auto it = state.begin(); it != state.end(); )
                {
                    if ( it->second > dist )
                        it = state.erase(it);
                    else
                        it++;
                }
            }
            return dist + 1;
        }
 
        template<class SymbolType>
        static void DFS ( const State & state,
                          const string::LinearString < SymbolType > & lfactor,
                          const automaton::DFA < SymbolType, State > & dSuffix,
                          const automaton::DFA < SymbolType, State > & dSuffixReversed,
                          ext::set < ext::pair < string::LinearString < SymbolType > , unsigned > > & result,
                          const string::LinearString < SymbolType > & pattern,
                          unsigned distance,
                          bool restricted )
        {
            if ( ! restricted || std::any_of( state.begin(), state.end(), []( const auto & x ) -> bool { return x.second == 0; } ) )
            {
                /* check if lfactor is seed, add to result if so */
                if ( ( lfactor.size() < pattern.getContent().size() )
                    && isSeed( lfactor, state, distance, dSuffix, dSuffixReversed, pattern ) )
                {
                    unsigned d = smallestDistanceSeed( lfactor, state, distance, dSuffix, dSuffixReversed, pattern );
                    if ( lfactor.size() > d )
                        result.insert( ext::make_pair( string::LinearString < SymbolType > ( lfactor ), d ) );
                }
                /* going to next states */
                auto transitions = dSuffix.getTransitionsFromState( state );
                for ( const auto & tr : transitions )
                {
                    string::LinearString < SymbolType > lfactorCopy = lfactor;
                    lfactorCopy.appendSymbol( tr.first.second );
                    DFS( tr.second, lfactorCopy, dSuffix, dSuffixReversed, result, pattern, distance, restricted );
                }
            }
        }
 
 
    public:
        template<class SymbolType>
        static ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > compute (
            const string::LinearString < SymbolType > & pattern,
            unsigned distance,
            bool restricted )
        {
            auto dSuffix = DeterministicApproximateSuffixAutomatonForHammingDistanceFactory::construct( pattern, distance );
 
            string::LinearString < SymbolType > reversedPattern = string::transform::StringReverse::reverse ( pattern );
            auto dSuffixReversed = DeterministicApproximateSuffixAutomatonForHammingDistanceFactory::construct( reversedPattern, distance );
 
            ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > result;
 
            DFS( dSuffix.getInitialState(), string::LinearString < SymbolType > (dSuffix.getInputAlphabet(), {} ), dSuffix, dSuffixReversed, result, pattern, distance, restricted );
 
            return result;
        }
 
        template<class SymbolType>
        static ext::set < ext::pair < string::LinearString < SymbolType >, unsigned > > compute (
            const string::LinearString < SymbolType > & pattern,
            unsigned distance )
        {
            return ApproximateSeedComputation::compute( pattern, distance, false );
        }
    };
}