diff options
Diffstat (limited to 'boost/algorithm/searching/boyer_moore.hpp')
-rw-r--r-- | boost/algorithm/searching/boyer_moore.hpp | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/boost/algorithm/searching/boyer_moore.hpp b/boost/algorithm/searching/boyer_moore.hpp new file mode 100644 index 0000000000..958f0b8d0c --- /dev/null +++ b/boost/algorithm/searching/boyer_moore.hpp @@ -0,0 +1,268 @@ +/* + 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/assert.hpp> +#include <boost/static_assert.hpp> + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +#include <boost/utility/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: boostinspect:noascii (test tool complains) + http://en.wikipedia.org/wiki/Boyer–Moore_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> + 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 corpus_last; // if nothing to search, we didn't find it! + if ( pat_first == pat_last ) return 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 corpus_last; + + // Do the search + return this->do_search ( corpus_first, corpus_last ); + } + + template <typename Range> + 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> + 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 curPos; + } + + // 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 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 pat_first, Iter pat_last, Container &prefix ) { + const std::size_t count = std::distance ( pat_first, pat_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 && ( pat_first[k] != pat_first[i] )) { + BOOST_ASSERT ( k < count ); + k = prefix [ k - 1 ]; + } + + if ( pat_first[k] == pat_first[i] ) + k++; + prefix [ i ] = k; + } + } + + void build_suffix_table ( patIter pat_first, patIter pat_last ) { + const std::size_t count = (std::size_t) std::distance ( pat_first, pat_last ); + + if ( count > 0 ) { // empty pattern + std::vector<typename std::iterator_traits<patIter>::value_type> reversed(count); + (void) std::reverse_copy ( pat_first, pat_last, reversed.begin ()); + + std::vector<difference_type> prefix (count); + compute_bm_prefix ( pat_first, pat_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> + 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> + 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::lazy_disable_if_c< + boost::is_same<CorpusRange, patIter>::value, typename boost::range_iterator<CorpusRange> > + ::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> + 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 |