1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Boyer-Moore-Horspool Search</title> 5<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../index.html" title="The Boost Algorithm Library"> 8<link rel="up" href="../../algorithm/Searching.html" title="Searching Algorithms"> 9<link rel="prev" href="../../algorithm/Searching.html" title="Searching Algorithms"> 10<link rel="next" href="KnuthMorrisPratt.html" title="Knuth-Morris-Pratt Search"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="../../algorithm/Searching.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../algorithm/Searching.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="KnuthMorrisPratt.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h3 class="title"> 27<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool"></a><a class="link" href="BoyerMooreHorspool.html" title="Boyer-Moore-Horspool Search">Boyer-Moore-Horspool 28 Search</a> 29</h3></div></div></div> 30<h5> 31<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h0"></a> 32 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.overview"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.overview">Overview</a> 33 </h5> 34<p> 35 The header file 'boyer_moore_horspool.hpp' contains an implementation of 36 the Boyer-Moore-Horspool algorithm for searching sequences of values. 37 </p> 38<p> 39 The Boyer-Moore-Horspool search algorithm was published by Nigel Horspool 40 in 1980. It is a refinement of the Boyer-Moore algorithm that trades space 41 for time. It uses less space for internal tables than Boyer-Moore, and has 42 poorer worst-case performance. 43 </p> 44<p> 45 The Boyer-Moore-Horspool algorithm cannot be used with comparison predicates 46 like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">search</span></code>. 47 </p> 48<h5> 49<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h1"></a> 50 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.interface"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.interface">Interface</a> 51 </h5> 52<p> 53 Nomenclature: I refer to the sequence being searched for as the "pattern", 54 and the sequence being searched in as the "corpus". 55 </p> 56<p> 57 For flexibility, the Boyer-Moore-Horspool algorithm has two interfaces; an 58 object-based interface and a procedural one. The object-based interface builds 59 the tables in the constructor, and uses operator () to perform the search. 60 The procedural interface builds the table and does the search all in one 61 step. If you are going to be searching for the same pattern in multiple corpora, 62 then you should use the object interface, and only build the tables once. 63 </p> 64<p> 65 Here is the object interface: 66</p> 67<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">patIter</span><span class="special">></span> 68<span class="keyword">class</span> <span class="identifier">boyer_moore_horspool</span> <span class="special">{</span> 69<span class="keyword">public</span><span class="special">:</span> 70 <span class="identifier">boyer_moore_horspool</span> <span class="special">(</span> <span class="identifier">patIter</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">patIter</span> <span class="identifier">last</span> <span class="special">);</span> 71 <span class="special">~</span><span class="identifier">boyer_moore_horspool</span> <span class="special">();</span> 72 73 <span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">corpusIter</span><span class="special">></span> 74 <span class="identifier">pair</span><span class="special"><</span><span class="identifier">corpusIter</span><span class="special">,</span> <span class="identifier">corpusIter</span><span class="special">></span> <span class="keyword">operator</span> <span class="special">()</span> <span class="special">(</span> <span class="identifier">corpusIter</span> <span class="identifier">corpus_first</span><span class="special">,</span> <span class="identifier">corpusIter</span> <span class="identifier">corpus_last</span> <span class="special">);</span> 75 <span class="special">};</span> 76</pre> 77<p> 78 </p> 79<p> 80 and here is the corresponding procedural interface: 81 </p> 82<p> 83</p> 84<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">patIter</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">corpusIter</span><span class="special">></span> 85<span class="identifier">pair</span><span class="special"><</span><span class="identifier">corpusIter</span><span class="special">,</span> <span class="identifier">corpusIter</span><span class="special">></span> <span class="identifier">boyer_moore_horspool_search</span> <span class="special">(</span> 86 <span class="identifier">corpusIter</span> <span class="identifier">corpus_first</span><span class="special">,</span> <span class="identifier">corpusIter</span> <span class="identifier">corpus_last</span><span class="special">,</span> 87 <span class="identifier">patIter</span> <span class="identifier">pat_first</span><span class="special">,</span> <span class="identifier">patIter</span> <span class="identifier">pat_last</span> <span class="special">);</span> 88</pre> 89<p> 90 </p> 91<p> 92 Each of the functions is passed two pairs of iterators. The first two define 93 the corpus and the second two define the pattern. Note that the two pairs 94 need not be of the same type, but they do need to "point" at the 95 same type. In other words, <code class="computeroutput"><span class="identifier">patIter</span><span class="special">::</span><span class="identifier">value_type</span></code> 96 and <code class="computeroutput"><span class="identifier">curpusIter</span><span class="special">::</span><span class="identifier">value_type</span></code> need to be the same type. 97 </p> 98<p> 99 The return value of the function is a pair of iterators pointing to the position 100 of the pattern in the corpus. If the pattern is empty, it returns at empty 101 range at the start of the corpus (<code class="computeroutput"><span class="identifier">corpus_first</span></code>, 102 <code class="computeroutput"><span class="identifier">corpus_first</span></code>). If the pattern 103 is not found, it returns at empty range at the end of the corpus (<code class="computeroutput"><span class="identifier">corpus_last</span></code>, <code class="computeroutput"><span class="identifier">corpus_last</span></code>). 104 </p> 105<h5> 106<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h2"></a> 107 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.compatibility_note"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.compatibility_note">Compatibility 108 Note</a> 109 </h5> 110<p> 111 Earlier versions of this searcher returned only a single iterator. As explained 112 in <a href="https://cplusplusmusings.wordpress.com/2016/02/01/sometimes-you-get-things-wrong/" target="_top">https://cplusplusmusings.wordpress.com/2016/02/01/sometimes-you-get-things-wrong/</a>, 113 this was a suboptimal interface choice, and has been changed, starting in 114 the 1.62.0 release. Old code that is expecting a single iterator return value 115 can be updated by replacing the return value of the searcher's <code class="computeroutput"><span class="keyword">operator</span> <span class="special">()</span></code> 116 with the <code class="computeroutput"><span class="special">.</span><span class="identifier">first</span></code> 117 field of the pair. 118 </p> 119<p> 120 Instead of: 121</p> 122<pre class="programlisting"><span class="identifier">iterator</span> <span class="identifier">foo</span> <span class="special">=</span> <span class="identifier">searcher</span><span class="special">(</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">b</span><span class="special">);</span> 123</pre> 124<p> 125 </p> 126<p> 127 you now write: 128</p> 129<pre class="programlisting"><span class="identifier">iterator</span> <span class="identifier">foo</span> <span class="special">=</span> <span class="identifier">searcher</span><span class="special">(</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">b</span><span class="special">).</span><span class="identifier">first</span><span class="special">;</span> 130</pre> 131<p> 132 </p> 133<h5> 134<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h3"></a> 135 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.performance"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.performance">Performance</a> 136 </h5> 137<p> 138 The execution time of the Boyer-Moore-Horspool algorithm is linear in the 139 size of the string being searched; it can have a significantly lower constant 140 factor than many other search algorithms: it doesn't need to check every 141 character of the string to be searched, but rather skips over some of them. 142 Generally the algorithm gets faster as the pattern being searched for becomes 143 longer. Its efficiency derives from the fact that with each unsuccessful 144 attempt to find a match between the search string and the text it is searching, 145 it uses the information gained from that attempt to rule out as many positions 146 of the text as possible where the string cannot match. 147 </p> 148<h5> 149<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h4"></a> 150 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.memory_use"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.memory_use">Memory 151 Use</a> 152 </h5> 153<p> 154 The algorithm an internal table that has one entry for each member of the 155 "alphabet" in the pattern. For (8-bit) character types, this table 156 contains 256 entries. 157 </p> 158<h5> 159<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h5"></a> 160 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.complexity"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.complexity">Complexity</a> 161 </h5> 162<p> 163 The worst-case performance is <span class="emphasis"><em>O(m x n)</em></span>, where <span class="emphasis"><em>m</em></span> 164 is the length of the pattern and <span class="emphasis"><em>n</em></span> is the length of 165 the corpus. The average time is <span class="emphasis"><em>O(n)</em></span>. The best case 166 performance is sub-linear, and is, in fact, identical to Boyer-Moore, but 167 the initialization is quicker and the internal loop is simpler than Boyer-Moore. 168 </p> 169<h5> 170<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h6"></a> 171 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.exception_safety"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.exception_safety">Exception 172 Safety</a> 173 </h5> 174<p> 175 Both the object-oriented and procedural versions of the Boyer-Moore-Horspool 176 algorithm take their parameters by value and do not use any information other 177 than what is passed in. Therefore, both interfaces provide the strong exception 178 guarantee. 179 </p> 180<h5> 181<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h7"></a> 182 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.notes"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.notes">Notes</a> 183 </h5> 184<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 185<li class="listitem"> 186 When using the object-based interface, the pattern must remain unchanged 187 for during the searches; i.e, from the time the object is constructed 188 until the final call to operator () returns. 189 </li> 190<li class="listitem"> 191 The Boyer-Moore-Horspool algorithm requires random-access iterators for 192 both the pattern and the corpus. 193 </li> 194</ul></div> 195<h5> 196<a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.h8"></a> 197 <span class="phrase"><a name="the_boost_algorithm_library.Searching.BoyerMooreHorspool.customization_points"></a></span><a class="link" href="BoyerMooreHorspool.html#the_boost_algorithm_library.Searching.BoyerMooreHorspool.customization_points">Customization 198 points</a> 199 </h5> 200<p> 201 The Boyer-Moore-Horspool object takes a traits template parameter which enables 202 the caller to customize how the precomputed table is stored. This table, 203 called the skip table, contains (logically) one entry for every possible 204 value that the pattern can contain. When searching 8-bit character data, 205 this table contains 256 elements. The traits class defines the table to be 206 used. 207 </p> 208<p> 209 The default traits class uses a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">array</span></code> 210 for small 'alphabets' and a <code class="computeroutput"><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_map</span></code> 211 for larger ones. The array-based skip table gives excellent performance, 212 but could be prohibitively large when the 'alphabet' of elements to be searched 213 grows. The unordered_map based version only grows as the number of unique 214 elements in the pattern, but makes many more heap allocations, and gives 215 slower lookup performance. 216 </p> 217<p> 218 To use a different skip table, you should define your own skip table object 219 and your own traits class, and use them to instantiate the Boyer-Moore-Horspool 220 object. The interface to these objects is described TBD. 221 </p> 222</div> 223<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 224<td align="left"></td> 225<td align="right"><div class="copyright-footer">Copyright © 2010-2012 Marshall Clow<p> 226 Distributed under the Boost Software License, Version 1.0. (See accompanying 227 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 228 </p> 229</div></td> 230</tr></table> 231<hr> 232<div class="spirit-nav"> 233<a accesskey="p" href="../../algorithm/Searching.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../algorithm/Searching.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="KnuthMorrisPratt.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 234</div> 235</body> 236</html> 237
