boost/algorithm/searching/boyer_moore.hpp
/* Copyright (c) Marshall Clow 2010-2012. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) For more information, see http://www.boost.org */ #ifndef BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP #define BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP #include <iterator> // for std::iterator_traits #include <boost/config.hpp> #include <boost/assert.hpp> #include <boost/static_assert.hpp> #include <boost/range/begin.hpp> #include <boost/range/end.hpp> #include <boost/core/enable_if.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/algorithm/searching/detail/bm_traits.hpp> #include <boost/algorithm/searching/detail/debugging.hpp> namespace boost { namespace algorithm { /* A templated version of the boyer-moore searching algorithm. References: http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/ http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf Explanations: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm http://www.movsd.com/bm.htm http://www.cs.ucdavis.edu/~gusfield/cs224f09/bnotes.pdf The Boyer-Moore search algorithm uses two tables, a "bad character" table to tell how far to skip ahead when it hits a character that is not in the pattern, and a "good character" table to tell how far to skip ahead when it hits a mismatch on a character that _is_ in the pattern. Requirements: * Random access iterators * The two iterator types (patIter and corpusIter) must "point to" the same underlying type and be comparable. * Additional requirements may be imposed but the skip table, such as: ** Numeric type (array-based skip table) ** Hashable type (map-based skip table) */ template <typename patIter, typename traits = detail::BM_traits<patIter> > class boyer_moore { typedef typename std::iterator_traits<patIter>::difference_type difference_type; public: boyer_moore ( patIter first, patIter last ) : pat_first ( first ), pat_last ( last ), k_pattern_length ( std::distance ( pat_first, pat_last )), skip_ ( k_pattern_length, -1 ), suffix_ ( k_pattern_length + 1 ) { this->build_skip_table ( first, last ); this->build_suffix_table ( first, last ); } ~boyer_moore () {} /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last ) /// \brief Searches the corpus for the pattern that was passed into the constructor /// /// \param corpus_first The start of the data to search (Random Access Iterator) /// \param corpus_last One past the end of the data to search /// template <typename corpusIter> std::pair<corpusIter, corpusIter> operator () ( corpusIter corpus_first, corpusIter corpus_last ) const { BOOST_STATIC_ASSERT (( boost::is_same< typename std::iterator_traits<patIter>::value_type, typename std::iterator_traits<corpusIter>::value_type>::value )); if ( corpus_first == corpus_last ) return std::make_pair(corpus_last, corpus_last); // if nothing to search, we didn't find it! if ( pat_first == pat_last ) return std::make_pair(corpus_first, corpus_first); // empty pattern matches at start const difference_type k_corpus_length = std::distance ( corpus_first, corpus_last ); // If the pattern is larger than the corpus, we can't find it! if ( k_corpus_length < k_pattern_length ) return std::make_pair(corpus_last, corpus_last); // Do the search return this->do_search ( corpus_first, corpus_last ); } template <typename Range> std::pair<typename boost::range_iterator<Range>::type, typename boost::range_iterator<Range>::type> operator () ( Range &r ) const { return (*this) (boost::begin(r), boost::end(r)); } private: /// \cond DOXYGEN_HIDE patIter pat_first, pat_last; const difference_type k_pattern_length; typename traits::skip_table_t skip_; std::vector <difference_type> suffix_; /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last, Pred p ) /// \brief Searches the corpus for the pattern that was passed into the constructor /// /// \param corpus_first The start of the data to search (Random Access Iterator) /// \param corpus_last One past the end of the data to search /// \param p A predicate used for the search comparisons. /// template <typename corpusIter> std::pair<corpusIter, corpusIter> do_search ( corpusIter corpus_first, corpusIter corpus_last ) const { /* ---- Do the matching ---- */ corpusIter curPos = corpus_first; const corpusIter lastPos = corpus_last - k_pattern_length; difference_type j, k, m; while ( curPos <= lastPos ) { /* while ( std::distance ( curPos, corpus_last ) >= k_pattern_length ) { */ // Do we match right where we are? j = k_pattern_length; while ( pat_first [j-1] == curPos [j-1] ) { j--; // We matched - we're done! if ( j == 0 ) return std::make_pair(curPos, curPos + k_pattern_length); } // Since we didn't match, figure out how far to skip forward k = skip_ [ curPos [ j - 1 ]]; m = j - k - 1; if ( k < j && m > suffix_ [ j ] ) curPos += m; else curPos += suffix_ [ j ]; } return std::make_pair(corpus_last, corpus_last); // We didn't find anything } void build_skip_table ( patIter first, patIter last ) { for ( std::size_t i = 0; first != last; ++first, ++i ) skip_.insert ( *first, i ); } template<typename Iter, typename Container> void compute_bm_prefix ( Iter first, Iter last, Container &prefix ) { const std::size_t count = std::distance ( first, last ); BOOST_ASSERT ( count > 0 ); BOOST_ASSERT ( prefix.size () == count ); prefix[0] = 0; std::size_t k = 0; for ( std::size_t i = 1; i < count; ++i ) { BOOST_ASSERT ( k < count ); while ( k > 0 && ( first[k] != first[i] )) { BOOST_ASSERT ( k < count ); k = prefix [ k - 1 ]; } if ( first[k] == first[i] ) k++; prefix [ i ] = k; } } void build_suffix_table ( patIter first, patIter last ) { const std::size_t count = (std::size_t) std::distance ( first, last ); if ( count > 0 ) { // empty pattern std::vector<typename std::iterator_traits<patIter>::value_type> reversed(count); (void) std::reverse_copy ( first, last, reversed.begin ()); std::vector<difference_type> prefix (count); compute_bm_prefix ( first, last, prefix ); std::vector<difference_type> prefix_reversed (count); compute_bm_prefix ( reversed.begin (), reversed.end (), prefix_reversed ); for ( std::size_t i = 0; i <= count; i++ ) suffix_[i] = count - prefix [count-1]; for ( std::size_t i = 0; i < count; i++ ) { const std::size_t j = count - prefix_reversed[i]; const difference_type k = i - prefix_reversed[i] + 1; if (suffix_[j] > k) suffix_[j] = k; } } } /// \endcond }; /* Two ranges as inputs gives us four possibilities; with 2,3,3,4 parameters Use a bit of TMP to disambiguate the 3-argument templates */ /// \fn boyer_moore_search ( corpusIter corpus_first, corpusIter corpus_last, /// patIter pat_first, patIter pat_last ) /// \brief Searches the corpus for the pattern. /// /// \param corpus_first The start of the data to search (Random Access Iterator) /// \param corpus_last One past the end of the data to search /// \param pat_first The start of the pattern to search for (Random Access Iterator) /// \param pat_last One past the end of the data to search for /// template <typename patIter, typename corpusIter> std::pair<corpusIter, corpusIter> boyer_moore_search ( corpusIter corpus_first, corpusIter corpus_last, patIter pat_first, patIter pat_last ) { boyer_moore<patIter> bm ( pat_first, pat_last ); return bm ( corpus_first, corpus_last ); } template <typename PatternRange, typename corpusIter> std::pair<corpusIter, corpusIter> boyer_moore_search ( corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern ) { typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; boyer_moore<pattern_iterator> bm ( boost::begin(pattern), boost::end (pattern)); return bm ( corpus_first, corpus_last ); } template <typename patIter, typename CorpusRange> typename boost::disable_if_c< boost::is_same<CorpusRange, patIter>::value, std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> > ::type boyer_moore_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last ) { boyer_moore<patIter> bm ( pat_first, pat_last ); return bm (boost::begin (corpus), boost::end (corpus)); } template <typename PatternRange, typename CorpusRange> std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> boyer_moore_search ( CorpusRange &corpus, const PatternRange &pattern ) { typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; boyer_moore<pattern_iterator> bm ( boost::begin(pattern), boost::end (pattern)); return bm (boost::begin (corpus), boost::end (corpus)); } // Creator functions -- take a pattern range, return an object template <typename Range> boost::algorithm::boyer_moore<typename boost::range_iterator<const Range>::type> make_boyer_moore ( const Range &r ) { return boost::algorithm::boyer_moore <typename boost::range_iterator<const Range>::type> (boost::begin(r), boost::end(r)); } template <typename Range> boost::algorithm::boyer_moore<typename boost::range_iterator<Range>::type> make_boyer_moore ( Range &r ) { return boost::algorithm::boyer_moore <typename boost::range_iterator<Range>::type> (boost::begin(r), boost::end(r)); } }} #endif // BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP