SequentialSampling.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/measure>
 
#include <alib/set>
#include <alib/vector>
 
#include <string/properties/PeriodicPrefix.h>
#include <string/LinearString.h>
 
 
namespace stringology {
 
    namespace exact {
 
        namespace {
            size_t div_up (const size_t &x ,const size_t  &y ) {
                return ( x % y == 1 ) ? x / y + 1 : x / y ;
            }
 
            template <class SymbolType>
            ext::set < unsigned > SimpleTextSearching ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern ) {
                ext::set<unsigned> occ;
                const auto & text = subject.getContent();
                const auto & pat = pattern.getContent();
                size_t n = text.size(), m = pat.size();
 
                size_t i = 0 ;
                while ( i <= n - m ) {
                    size_t j = 0 ;
                    while ( j < m && text[ i + j ] == pat[j] ) ++ j ;
                    if ( j == m  ) occ.insert(i) ;
                    i += div_up( j + 1 , 2 ) ;
                }
                return occ ;
            }
 
            // find first occurence i and return it, or -1
            template <class SymbolType>
            ssize_t SimpleTextSearchingFirst ( const ext::vector< SymbolType > & text, const ext::vector< SymbolType > & pat, const size_t & start) {
                size_t n = text.size(), m = pat.size();
 
                size_t i = start ;
                while ( i <= n - m ) {
                    size_t j = 0 ;
                    while ( j < m && text[ i + j ] == pat[j] ) ++ j ;
                    if ( j == m  ) return i ;
                    i += div_up( j + 1 , 2 ) ;
                }
                return -1;
            }
 
            template <class SymbolType>
            ext::set < unsigned > SeqSampling ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern, const size_t& p , const size_t& q ){
                ext::set<unsigned> occ;
                const auto & text = subject.getContent();
                const auto & pat = pattern.getContent();
                size_t n = text.size(), m = pat.size();
 
                size_t i = 0 ;
                while ( i <= n - m ) {
                    if ( text[i + p] != pat[p] || text[i + q] != pat[q] ) ++ i ;
                    else {
                        size_t j = 0 ;
                        while ( j < m && text[i + j] == pat[j] ) ++ j ;
                        if ( j == m ) occ.insert( i ) ;
                        if ( j < q - 1 ) i += p ;
                        else i += div_up( j + 1 , 2 ) ;
                    }
                }
                return occ ;
            }
 
            // finds the first occurence and return it
            template <class SymbolType>
            size_t SeqSamplingFirst ( const ext::vector< SymbolType > & text, const ext::vector < SymbolType > & pat, const size_t& p , const size_t& q , const size_t& start){
                size_t n = text.size(), m = pat.size();
 
                size_t i = start ;
                while ( i <= n - m ) {
                    if ( text[i + p] != pat[p] || text[i + q] != pat[q] ) ++ i ;
                    else {
                        size_t j = 0 ;
                        while ( j < m && text[i + j] == pat[j] ) ++ j ;
                        if ( j == m ) return i ;
                        if ( j < q - 1 ) i += p ;
                        else i += div_up(j + 1 , 2 );
                    }
                }
                return -1 ;
            }
 
            template <class SymbolType>
            ext::set < unsigned > Mix ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern, const size_t& per) {
                ext::set<unsigned> occ;
                const auto & text = subject.getContent();
                const auto & pat = pattern.getContent();
                size_t n = text.size(), m = pat.size();
 
                const ext::vector vv_ = ext::vector<SymbolType>( pat.begin() , pat.begin() + 2 * per - 1 ) ;
                ssize_t periodic_prefix , period ;
                ext::tie(periodic_prefix , period ) = string::properties::PeriodicPrefix::construct(string::LinearString ( vv_ ));
 
                ssize_t i = 0 ;
                while ( static_cast < size_t > ( i ) <= n - m ) {
                    if (periodic_prefix == -1) {
                        i = SimpleTextSearchingFirst(text, vv_ , i );
                    } else { i = SeqSamplingFirst(text, vv_ , periodic_prefix - period , periodic_prefix ,i  ); }
                    if ( i == -1 || static_cast < size_t > ( i ) > n - m ) return occ ;
                    size_t j = 2 * per - 1;
                    while (j < m && text[i + j] == pat[j]) ++j;
                    if (j == m) {
                        occ.insert(i);
                        i += per;
                    } else {
                        i += std::max ( j - per , static_cast < size_t > ( 1 ) ) ;
                    }
 
                }
                return occ ;
            }
        }
 
        class SequentialSampling{
        public:
            template < class SymbolType >
            static ext::set < unsigned > match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern );
 
        };
 
        template < class SymbolType >
        ext::set < unsigned > SequentialSampling::match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern ) {
            ssize_t periodic_prefix , period ;
            measurements::start ( "Preprocess", measurements::Type::PREPROCESS );
            ext::tie(periodic_prefix , period ) = string::properties::PeriodicPrefix::construct(pattern);
            measurements::end() ;
 
            measurements::start ( "Algorithm", measurements::Type::ALGORITHM );
            ext::set<unsigned> res ;
            if ( periodic_prefix == -1 ) {
                res = SimpleTextSearching( subject , pattern) ;
            } else if ( static_cast < size_t > ( periodic_prefix ) < pattern.getContent().size() ) {
                res = SeqSampling( subject, pattern , periodic_prefix - period, periodic_prefix ) ;
            } else res = Mix( subject, pattern, period ) ;
 
            measurements::end() ;
            return res ;
        }
 
 
    } /* namespace exact */
 
} /* namespace stringology */