Editing Boyer–Moore string-search algorithm

{{Short description|String searching algorithm}}
{{For|the majority vote algorithm|Boyer–Moore majority vote algorithm}}{{For|the Boyer–Moore theorem prover|Nqthm}}
{{Infobox algorithm
|name=Boyer–Moore string search
|class=[[String-searching algorithm|String search]]
|data=[[String (computer science)|String]]
|time=Θ(m) preprocessing + O(mn) matching<ref group="note">''m'' is the length of the pattern string, which we are searching for in the text, which is of length ''n''. This runtime is for finding all occurrences of the pattern, without the Galil rule.</ref>
|best-time=Θ(m) preprocessing + Ω(n/m) matching
|space=Θ(k+m)<ref group="note">''k'' is the size of the alphabet. This space is for the original delta1 bad-character table in the C and Java implementations and the good-suffix table.</ref>
}}
In [[computer science]], the '''Boyer–Moore string-search algorithm''' is an efficient [[string-searching algorithm]] that is the standard benchmark for practical string-search literature.<ref>{{cite journal |last1=Hume |first1=Andrew |last2=Sunday |first2=Daniel |s2cid=5902579 |date=November 1991 |title=Fast String Searching |journal=Software: Practice and Experience |volume=21 |issue=11 |pages=1221–1248 |doi=10.1002/spe.4380211105}}</ref> It was developed by [[Robert S. Boyer]] and [[J Strother Moore]] in 1977.<ref name="original">
{{cite journal
 | last1 = Boyer | first1 = Robert S.
 | author1-link = Robert S. Boyer
 | last2 = Moore | first2 = J Strother
 | author2-link = J Strother Moore
 | title = A Fast String Searching Algorithm.
 | journal = Comm. ACM
 | volume = 20
 | issue = 10
 | pages = 762–772
 | publisher = Association for Computing Machinery
 | location = New York
 | date = October 1977
 | issn = 0001-0782
 | doi = 10.1145/359842.359859 | s2cid = 15892987
 | doi-access = free
 }}
</ref> The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow-on paper; this paper contained errors which were later corrected by [[Wojciech Rytter]] in 1980.<ref name="Knuth_Morris_Pratt">{{cite journal |last1=Knuth |first1=Donald E. |author1-link=Donald Knuth |last2=Morris |first2=James H. Jr. |author2-link=James H. Morris |last3=Pratt |first3=Vaughan R. |author3-link=Vaughan Pratt |title=Fast pattern matching in strings |journal=SIAM Journal on Computing |issn=0097-5397 |volume=6 |issue=2 |pages=323–350 |year=1977 |url=http://citeseer.ist.psu.edu/context/23820/0 |doi=10.1137/0206024 |citeseerx=10.1.1.93.8147}}</ref><ref name="Rytter1980">{{cite journal|last1=Rytter|first1=Wojciech|title=A Correct Preprocessing Algorithm for Boyer–Moore String-Searching|journal=SIAM Journal on Computing|volume=9|issue=3|year=1980|pages=509–512|issn=0097-5397|doi=10.1137/0209037}}</ref>

The algorithm [[preprocessor|preprocesses]] the [[string (computer science)|string]] being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.

==Definitions==
{{float begin}}
| A||N||P||A||N||M||A||N||-
|-
| P||A||N||-||-||-||-||-||-
|-
| -||P||A||N||-||-||-||-||-
|-
| -||-||P||A||N||-||-||-||-
|-
| -||-||-||P||A||N||-||-||-
|-
| -||-||-||-||P||A||N||-||-
|-
| -||-||-||-||-||P||A||N||-
{{float end|caption=Alignments of pattern '''PAN''' to text '''ANPANMAN''',<br />from '''k=3''' to '''k=8'''. A match occurs at '''k=5'''.}}
* '''''T''''' denotes the input text to be searched. Its length is '''n'''.
* '''''P''''' denotes the string to be searched for, called the ''pattern''. Its length is '''m'''.
* '''''S''[''i'']''' denotes the character at index ''i'' of string ''S'', counting from 1.
* '''''S''[''i''..''j'']''' denotes the [[substring]] of string ''S'' starting at index ''i'' and ending at ''j'', inclusive.
* A ''prefix'' of ''S'' is a substring ''S''[1..''i''] for some ''i'' in range [1, ''l''], where ''l'' is the length of ''S''.
* A ''suffix'' of ''S'' is a substring ''S''[''i''..''l''] for some ''i'' in range [1, ''l''], where ''l'' is the length of ''S''.
* An ''alignment'' of ''P'' to ''T'' is an index ''k'' in ''T'' such that the last character of ''P'' is aligned with index ''k'' of ''T''.
* A ''match'' or ''occurrence'' of ''P'' occurs at an alignment ''k'' if ''P'' is equivalent to ''T''[(''k''-''m''+1)..''k''].

==Description==
The Boyer–Moore algorithm searches for occurrences of {{mvar|P}} in {{mvar|T}} by performing explicit character comparisons at different alignments. Instead of a [[brute-force search]] of all alignments (of which there are {{tmath|n - m + 1}}), Boyer–Moore uses information gained by preprocessing {{mvar|P}} to skip as many alignments as possible.

Previous to the introduction of this algorithm, the usual way to search within text was to examine each character of the text for the first character of the pattern. Once that was found the subsequent characters of the text would be compared to the characters of the pattern. If no match occurred then the text would again be checked character by character in an effort to find a match. Thus almost every character in the text needs to be examined.

The key insight in this algorithm is that if the end of the pattern is compared to the text, then jumps along the text can be made rather than checking every character of the text. The reason that this works is that in lining up the pattern against the text, the last character of the pattern is compared to the character in the text. If the characters do not match, there is no need to continue searching backwards along the text. If the character in the text does not match any of the characters in the pattern, then the next character in the text to check is located {{mvar|m}} characters farther along the text, where {{mvar|m}} is the length of the pattern. If the character in the text ''is'' in the pattern, then a partial shift of the pattern along the text is done to line up along the matching character and the process is repeated. Jumping along the text to make comparisons rather than checking every character in the text decreases the number of comparisons that have to be made, which is the key to the efficiency of the algorithm.

More formally, the algorithm begins at alignment {{tmath|1= k = m}}, so the start of {{mvar|P}} is aligned with the start of {{mvar|T}}. Characters in {{mvar|P}} and {{mvar|T}} are then compared starting at index {{mvar|m}} in {{mvar|P}} and {{mvar|k}} in {{mvar|T}}, moving backward. The strings are matched from the end of {{mvar|P}} to the start of {{mvar|P}}. The comparisons continue until either the beginning of {{mvar|P}} is reached (which means there is a match) or a mismatch occurs upon which the alignment is shifted forward (to the right) according to the maximum value permitted by a number of rules. The comparisons are performed again at the new alignment, and the process repeats until the alignment is shifted past the end of {{mvar|T}}, which means no further matches will be found.

The shift rules are implemented as constant-time table lookups, using tables generated during the preprocessing of {{mvar|P}}.

==Shift rules==
A shift is calculated by applying two rules: the bad-character rule and the good-suffix rule. The actual shifting offset is the maximum of the shifts calculated by these rules.

===The bad-character rule===

====Description====
{{float begin|side=right|width=340px}}
| -||-||-||-||X||-||-||K||-||-||-
|-
| A||N||P||A||<span style="color:#FF0000">N</span>||M||A||N||A||M||-
|-
| -||N||<span style="color:#0000FF">N</span>||A||A||M||A||N||-||-||-
|-
| -||-||-||N||<span style="color:#0000FF">N</span>||A||A||M||A||N||-
{{float end|Demonstration of bad-character rule with pattern '''P''' {{=}} '''NNAAMAN'''. There is a mismatch between '''N''' (in the input text) and '''A''' (in the pattern) in the column marked with an '''X'''. The pattern is shifted right (in this case by 2) so that the next occurrence of the character '''N''' (in the pattern '''P''') to the left of the current character (which is the middle '''A''') is found.}}

The bad-character rule considers the character in {{mvar|T}} at which the comparison process failed (assuming such a failure occurred). The next occurrence of that character to the left in {{mvar|P}} is found, and a shift which brings that occurrence in line with the mismatched occurrence in {{mvar|T}} is proposed. If the mismatched character does not occur to the left in {{mvar|P}}, a shift is proposed that moves the entirety of {{mvar|P}} past the point of mismatch.

====Preprocessing====
Methods vary on the exact form the table for the bad-character rule should take, but a simple constant-time lookup solution is as follows: create a 2D table which is indexed first by the index of the character {{mvar|c}} in the alphabet and second by the index {{mvar|i}} in the pattern. This lookup will return the occurrence of {{mvar|c}} in {{mvar|P}} with the next-highest index {{tmath|j < i}} or -1 if there is no such occurrence. The proposed shift will then be {{tmath|i - j}}, with {{tmath|O(1)}} lookup time and {{tmath|O(km)}} space, assuming a finite alphabet of length {{mvar|k}}.

The C and Java implementations below have a {{tmath|O(k)}} space complexity (make_delta1, makeCharTable). This is the same as the original delta1 and the [[Boyer–Moore–Horspool algorithm#Description|BMH bad-character table]]. This table maps a character at position {{tmath|i}} to shift by {{tmath|\operatorname{len}(p) - 1 - i}}, with the last instance—the least shift amount—taking precedence. All unused characters are set as {{tmath|\operatorname{len}(p)}} as a sentinel value.

===The good-suffix rule===

====Description====
{{float begin|side=right|width=380px}}
| -||-||-||-||X||-||-||K||-||-||-||-||-
|-
| M||A||N||P||A||<span style="color:#0000FF">N</span>||<span style="color:#0000FF">A</span>||<span style="color:#0000FF">M</span>||A||N||A||P||-
|-
| A||<span style="color:#FF0000">N</span>||<span style="color:#FF0000">A</span>||<span style="color:#FF0000">M</span>||P||<span style="color:#0000FF">N</span>||<span style="color:#0000FF">A</span>||<span style="color:#0000FF">M</span>||-||-||-||-||-
|-
| -||-||-||-||A||<span style="color:#FF0000">N</span>||<span style="color:#FF0000">A</span>||<span style="color:#FF0000">M</span>||P||N||A||M||-
{{float end|Demonstration of good-suffix rule with pattern '''P''' {{=}} '''ANAMPNAM'''. Here, '''''t''''' is '''T'''[6..8] and '''''{{prime|t}}''''' is '''P'''[2..4].}}

The good-suffix rule is markedly more complex in both concept and implementation than the bad-character rule. Like the bad-character rule, it also exploits the algorithm's feature of comparisons beginning at the end of the pattern and proceeding towards the pattern's start. It can be described as follows:<ref name = "ASTS">
{{Citation
 | last = Gusfield
 | first = Dan
 | title = Algorithms on Strings, Trees, and Sequences
 | publisher = Cambridge University Press
 | orig-date =1997
 | year = 1999
 | edition = 1
 | chapter = Chapter 2 - Exact Matching: Classical Comparison-Based Methods
 | pages = 19–21
 | isbn = 0-521-58519-8
}}
</ref>

<blockquote>
Suppose for a given alignment of '''''P''''' and '''''T''''', a substring '''''t''''' of '''''T''''' matches a suffix of '''''P''''' and suppose '''''t''''' is the largest such substring for the given alignment.
# Then find, if it exists, the right-most copy '''''{{prime|t}}''''' of '''''t''''' in '''''P''''' such that '''''{{prime|t}}''''' is not a suffix of '''''P''''' and the character to the left of '''''{{prime|t}}''''' in '''''P''''' differs from the character to the left of '''''t''''' in '''''P'''''. Shift '''''P''''' to the right so that substring '''''{{prime|t}}''''' in '''''P''''' aligns with substring '''''t''''' in '''''T'''''.
# If '''''{{prime|t}}''''' does not exist, then shift the left end of '''''P''''' to the right by the least amount (past the left end of '''''t''''' in '''''T''''') so that a prefix of the shifted pattern matches a suffix of '''''t''''' in '''''T'''''. This includes cases where '''''t''''' is an exact match of '''''P'''''.
# If no such shift is possible, then shift '''''P''''' by '''m''' (length of P) places to the right.
</blockquote>

====Preprocessing====
The good-suffix rule requires two tables: one for use in the general case (where a copy '''''{{prime|t}}''''' is found), and another for use when the general case returns no meaningful result. These tables will be designated {{mvar|L}} and {{mvar|H}} respectively. Their definitions are as follows:<ref name = "ASTS" />

<blockquote>
For each {{mvar|i}}, {{tmath|L[i]}} is the largest position less than {{mvar|m}} such that string {{tmath|P[i..m]}} matches a suffix of {{tmath|P[1..L[i]]}} and such that the character preceding that suffix is not equal to {{tmath|P[i-1]}}. {{tmath|L[i]}} is defined to be zero if there is no position satisfying the condition.
</blockquote>

<blockquote>
Let {{tmath|H[i]}} denote the length of the largest suffix of {{tmath|P[i..m]}} that is also a prefix of {{mvar|P}}, if one exists. If none exists, let {{tmath|H[i]}} be zero.
</blockquote>

Both of these tables are constructible in {{tmath|O(m)}} time and use {{tmath|O(m)}} space. The alignment shift for index {{mvar|i}} in {{mvar|P}} is given by {{tmath|m - L[i]}} or {{tmath|m - H[i]}}. {{mvar|H}} should only be used if {{tmath|L[i]}} is zero or a match has been found.


-----------------------------------------------
===Shift Example using pattern ANPANMAN===

 Index| Mismatch | Shift   
  0   |         N|   1    
  1   |        AN|   8    
  2   |       MAN|   3    
  3   |      NMAN|   6   
  4   |     ANMAN|   6   
  5   |    PANMAN|   6  
  6   |   NPANMAN|   6  
  7   |  ANPANMAN|   6  

Explanation:

Index 0, no characters matched, the character read was not an N. The good-suffix length is zero. Since there are plenty of letters in the pattern that are also not N, we have minimal information here - shifting by 1 is the least interesting result.

Index 1, we matched the N, and it was preceded by something other than A. Now look at the pattern starting from the end, where do we have N preceded by something other than A? There are two other N's, but both are preceded by A. That means no part of the good suffix can be useful to us -- shift by the full pattern length 8.

Index 2: We matched the AN, and it was preceded by not M. In the middle of the pattern there is a AN preceded by P, so it becomes the shift candidate. Shifting that AN to the right to line up with our match is a shift of 3.

Index 3 & up: the matched suffixes do not match anything else in the pattern, but the trailing suffix AN matches the start of the pattern, so the shifts here are all 6.<ref>{{cite web |title=Constructing a Good Suffix Table - Understanding an example |url=https://stackoverflow.com/questions/27428605/constructing-a-good-suffix-table-understanding-an-example |website=Stack Overflow |access-date=30 July 2024 |language=en |date=11 December 2014}}{{Creative Commons text attribution notice|cc=bysa3|from this source=yes}}</ref>

==The Galil rule==
A simple but important optimization of Boyer–Moore was put forth by [[Zvi Galil]] in 1979.<ref name="galil">
{{cite journal
 | last1 = Galil | first1 = Z.
 | author1-link = Zvi Galil
 | title = On improving the worst case running time of the Boyer–Moore string matching algorithm
 | journal = Comm. ACM
 | volume = 22
 | issue = 9
 | pages = 505–508
 | publisher = Association for Computing Machinery
 | location = New York
 | date = September 1979
 | issn = 0001-0782
 | doi = 10.1145/359146.359148 | s2cid = 1333465
 | doi-access = free
 }}
</ref>
As opposed to shifting, the Galil rule deals with speeding up the actual comparisons done at each alignment by skipping sections that are known to match. Suppose that at an alignment {{math|''k''<sub>1</sub>}}, {{math|'''''P'''''}} is compared with {{math|'''''T'''''}} down to character {{math|'''''c'''''}} of {{math|'''''T'''''}}. Then if {{math|'''''P'''''}} is shifted to {{math|''k''<sub>2</sub>}} such that its left end is between {{math|'''''c'''''}} and {{math|''k''<sub>1</sub>}}, in the next comparison phase a prefix of {{math|'''''P'''''}} must match the substring {{math|'''''T'''''[(''k''<sub>2</sub> - ''n'')..''k''<sub>1</sub>]}}. Thus if the comparisons get down to position {{math|''k''<sub>1</sub>}} of {{math|'''''T'''''}}, an occurrence of {{math|'''''P'''''}} can be recorded without explicitly comparing past {{math|''k''<sub>1</sub>}}. In addition to increasing the efficiency of Boyer–Moore, the Galil rule is required for proving linear-time execution in the worst case.

The Galil rule, in its original version, is only effective for versions that output multiple matches. It updates the substring range only on {{math|1='''''c''''' = 0}}, i.e. a full match. A generalized version for dealing with submatches was reported in 1985 as the [[Apostolico–Giancarlo algorithm]].<ref>{{cite journal |last1=Apostolico |first1=Alberto |last2=Giancarlo |first2=Raffaele |title=The Boyer–Moore–Galil String Searching Strategies Revisited |journal=SIAM Journal on Computing |volume=15 |pages=98–105 |language=en |doi=10.1137/0215007 |date=February 1986|url=https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech |url-access=subscription }}</ref>

==Performance==
The Boyer–Moore algorithm as presented in the original paper has worst-case running time of {{tmath|O(n+m)}} only if the pattern does ''not'' appear in the text. This was first proved by [[Donald Knuth|Knuth]], [[James H. Morris|Morris]], and [[Vaughan Pratt|Pratt]] in 1977,<ref name="Knuth_Morris_Pratt" /> followed by [[Leonidas J. Guibas|Guibas]] and [[Andrew Odlyzko|Odlyzko]] in 1980<ref name="go">
{{cite journal
 | last1 = Guibas | first1 = Leonidas
 | author1-link = Leonidas J. Guibas
 | last2 = Odlyzko | first2 = Andrew
 | author2-link = Andrew Odlyzko
 | title = A new proof of the linearity of the Boyer–Moore string searching algorithm
 | journal = Proceedings of the 18th Annual Symposium on Foundations of Computer Science
 | series = SFCS '77
 | pages = 189–195
 | publisher = IEEE Computer Society
 | location = Washington, District of Columbia
 | year = 1977
 | url = http://dl.acm.org/citation.cfm?id=1382431.1382552
 | doi = 10.1109/SFCS.1977.3 | s2cid = 6470193
 | url-access = subscription
 }}
</ref> with an upper bound of {{math|5''n''}} comparisons in the worst case. [[Richard J. Cole|Richard Cole]] gave a proof with an upper bound of {{math|3''n''}} comparisons in the worst case in 1991.<ref name="cole">
{{cite journal
 | last1 = Cole | first1 = Richard
 | title = Tight bounds on the complexity of the Boyer–Moore string matching algorithm
 | journal = Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms
 | series = Soda '91
 | pages = 224–233
 | publisher = Society for Industrial and Applied Mathematics
 | location = Philadelphia, Pennsylvania
 | date = September 1991
 | url = http://dl.acm.org/citation.cfm?id=127830
 | isbn = 0-89791-376-0 }}
</ref>

When the pattern ''does'' occur in the text, running time of the original algorithm is {{tmath|O(nm)}} in the worst case. This is easy to see when both pattern and text consist solely of the same repeated character. However, inclusion of the [[Galil rule]] results in linear runtime across all cases.<ref name="galil" /><ref name="cole" />

==Implementations==
Various implementations exist in different programming languages. In [[C++]] it is part of the Standard Library since C++17 and [[Boost (C++ libraries)|Boost]] provides the [http://www.boost.org/doc/libs/1_58_0/libs/algorithm/doc/html/algorithm/Searching.html#the_boost_algorithm_library.Searching.BoyerMoore generic Boyer–Moore search] implementation under the ''Algorithm'' library. In [[Go (programming language)]] there is an implementation in [https://golang.org/src/strings/search.go search.go]. [[D (programming language)]] uses a [http://dlang.org/phobos/std_algorithm_searching.html#boyerMooreFinder BoyerMooreFinder] for predicate based matching within ranges as a part of the Phobos Runtime Library.

The Boyer–Moore algorithm is also used in [[GNU]]'s [[grep]].<ref>{{cite web| url=https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html |title=why GNU grep is fast |website=FreeBSD-current mailing list archive |date=21 August 2010 |first=Mike |last=Haertel}}</ref>

==Variants==
The [[Boyer–Moore–Horspool algorithm]] is a simplification of the Boyer–Moore algorithm using only the bad-character rule.

The [[Apostolico–Giancarlo algorithm]] speeds up the process of checking whether a match has occurred at the given alignment by skipping explicit character comparisons. This uses information gleaned during the pre-processing of the pattern in conjunction with suffix match lengths recorded at each match attempt. Storing suffix match lengths requires an additional table equal in size to the text being searched.

The [[Raita algorithm]] improves the performance of Boyer–Moore–Horspool algorithm. The searching pattern of particular sub-string in a given string is different from Boyer–Moore–Horspool algorithm.

==Notes==
{{reflist|group=note}}

==References==
{{reflist}}

==External links==
{{Commons category}}
*[http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf Original paper on the Boyer-Moore algorithm]
*[http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html An example of the Boyer-Moore algorithm] from the homepage of [[J Strother Moore]], co-inventor of the algorithm
*[http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps Richard Cole's 1991 paper proving runtime linearity]

{{Strings}}

{{DEFAULTSORT:Boyer-Moore String Search Algorithm}}
[[Category:String matching algorithms]]
[[Category:Articles with example C code]]
[[Category:Articles with example Python (programming language) code]]
[[Category:Articles with example Java code]]
[[Category:Computer-related introductions in 1977]]