String searching algorithm
Encyclopedia
String searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings
(also called pattern
s) are found within a larger string or text.
Let Σ be an alphabet (finite set). Formally, both the pattern and searched text are vectors of elements of Σ. The Σ may be a usual human alphabet (for example, the letters A through Z in the Latin alphabet). Other applications may use binary alphabet (Σ = {0,1}) or DNA alphabet (Σ = {A,C,G,T}) in bioinformatics
.
In practice, how the string is encoded can affect the feasible string search algorithms. In particular if a variable width encoding is in use then it is slow (time proportional to N) to find the Nth character. This will significantly slow down many of the more advanced search algorithms. A possible solution is to search for the sequence of code units instead, but doing so may produce false matches unless the encoding is specifically designed to avoid it.
s can be classified by the number of patterns each uses.
1Asymptotic times are expressed using O, Ω, and Θ notation
The Boyer–Moore string search algorithm has been the standard benchmark for the practical string search literature.
or regular expression
.
(n + m) steps, where n is the length of the haystack and m is the length of the needle; but in the worst case, searching for a string like "aaaab" in a string like "aaaaaaaaab", it takes O
(nm) steps.
In this approach, we avoid backtracking by constructing a deterministic finite automaton (DFA) that recognizes strings containing the desired search string. These are expensive to construct—they are usually created using the powerset construction
—but very quick to use. For example, the DFA shown to the right recognizes the word "MOMMY". This approach is frequently generalized in practice to search for arbitrary regular expression
s.
computes a DFA that recognizes inputs with the string to search for as a suffix, Boyer–Moore
starts searching from the end of the needle, so it can usually jump ahead a whole needle-length at each step. Baeza–Yates keeps track of whether the previous j characters were a prefix of the search string, and is therefore adaptable to fuzzy string searching. The bitap algorithm
is an application of Baeza-Yates' approach.
or suffix array
, the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in
time, and all 
occurrences of a pattern can be found in 
time (if the alphabet size is viewed as a constant).
, are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called "fuzzy" searches
.
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
(also called pattern
Pattern
A pattern, from the French patron, is a type of theme of recurring events or objects, sometimes referred to as elements of a set of objects.These elements repeat in a predictable manner...
s) are found within a larger string or text.
Let Σ be an alphabet (finite set). Formally, both the pattern and searched text are vectors of elements of Σ. The Σ may be a usual human alphabet (for example, the letters A through Z in the Latin alphabet). Other applications may use binary alphabet (Σ = {0,1}) or DNA alphabet (Σ = {A,C,G,T}) in bioinformatics
Bioinformatics
Bioinformatics is the application of computer science and information technology to the field of biology and medicine. Bioinformatics deals with algorithms, databases and information systems, web technologies, artificial intelligence and soft computing, information and computation theory, software...
.
In practice, how the string is encoded can affect the feasible string search algorithms. In particular if a variable width encoding is in use then it is slow (time proportional to N) to find the Nth character. This will significantly slow down many of the more advanced search algorithms. A possible solution is to search for the sequence of code units instead, but doing so may produce false matches unless the encoding is specifically designed to avoid it.
Basic classification
The various algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s can be classified by the number of patterns each uses.
Single pattern algorithms
Let m be the length of the pattern and let n be the length of the searchable text.| Algorithm | Preprocessing time | Matching time1 |
|---|---|---|
| Naïve string search algorithm | 0 (no preprocessing) | Θ((n-m+1) m) |
| Rabin–Karp string search algorithm | Θ(m) | average Θ(n+m), worst Θ((n-m+1) m) |
| Finite-state automaton based search | Θ(m |Σ|) | Θ(n) |
| Knuth–Morris–Pratt algorithm Knuth–Morris–Pratt algorithm The Knuth–Morris–Pratt string searching algorithm searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing... |
Θ(m) | Θ(n) |
| Boyer–Moore string search algorithm Boyer–Moore string search algorithm The Boyer–Moore string search algorithm is a particularly efficient string searching algorithm, and it has been the standard benchmark for the practical string search literature. It was developed by Bob Boyer and J Strother Moore in 1977... |
Θ(m + |Σ|) | Ω(n/m), O(n) |
| Bitap algorithm Bitap algorithm The bitap algorithm is an approximate string matching algorithm... (shift-or, shift-and, Baeza–Yates–Gonnet) |
Θ(m + |Σ|) | O(mn) |
1Asymptotic times are expressed using O, Ω, and Θ notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
The Boyer–Moore string search algorithm has been the standard benchmark for the practical string search literature.
Algorithms using finite set of patterns
- Aho–Corasick string matching algorithmAho–Corasick string matching algorithmThe Aho–Corasick string matching algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings within an input text. It matches all patterns simultaneously...
- Commentz–Walter algorithm
- Rabin–Karp string search algorithm
Algorithms using infinite number of patterns
Naturally, the patterns can not be enumerated in this case. They are represented usually by a regular grammarRegular grammar
In theoretical computer science, a regular grammar is a formal grammar that describes a regular language.- Strictly regular grammars :A right regular grammar is a formal grammar such that all the production rules in P are of one of the following forms:# B → a - where B is a non-terminal in N and...
or regular expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
.
Other classification
Other classification approaches are possible. One of the most common uses preprocessing as main criteria.| Text not preprocessed | Text preprocessed | |
|---|---|---|
| Patterns not preprocessed | Elementary algorithms | Index methods |
| Patterns preprocessed | Constructed search engines | Signature methods |
Naïve string search
The simplest and least efficient way to see where one string occurs inside another is to check each place it could be, one by one, to see if it's there. So first we see if there's a copy of the needle in the first character of the haystack; if not, we look to see if there's a copy of the needle starting at the second character of the haystack; if not, we look starting at the third character, and so forth. In the normal case, we only have to look at one or two characters for each wrong position to see that it is a wrong position, so in the average case, this takes OBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n + m) steps, where n is the length of the haystack and m is the length of the needle; but in the worst case, searching for a string like "aaaab" in a string like "aaaaaaaaab", it takes O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(nm) steps.
Finite state automaton based search
Powerset construction
In the theory of computation and Automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton into a deterministic finite automaton which recognizes the same formal language...
—but very quick to use. For example, the DFA shown to the right recognizes the word "MOMMY". This approach is frequently generalized in practice to search for arbitrary regular expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
s.
Stubs
Knuth–Morris–PrattKnuth–Morris–Pratt algorithm
The Knuth–Morris–Pratt string searching algorithm searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing...
computes a DFA that recognizes inputs with the string to search for as a suffix, Boyer–Moore
Boyer–Moore string search algorithm
The Boyer–Moore string search algorithm is a particularly efficient string searching algorithm, and it has been the standard benchmark for the practical string search literature. It was developed by Bob Boyer and J Strother Moore in 1977...
starts searching from the end of the needle, so it can usually jump ahead a whole needle-length at each step. Baeza–Yates keeps track of whether the previous j characters were a prefix of the search string, and is therefore adaptable to fuzzy string searching. The bitap algorithm
Bitap algorithm
The bitap algorithm is an approximate string matching algorithm...
is an application of Baeza-Yates' approach.
Index methods
Faster search algorithms are based on preprocessing of the text. After building a substring index, for example a suffix treeSuffix tree
In computer science, a suffix tree is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.The suffix tree for a string S is a tree whose edges are labeled with strings, such that each suffix...
or suffix array
Suffix array
In computer science, a suffix array is an array of integers giving the starting positions of suffixes of a string in lexicographical order.-Details:Consider the string...
, the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in
time, and all occurrences of a pattern can be found in time (if the alphabet size is viewed as a constant).Other variants
Some search methods, for instance trigram searchTrigram search
Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known. It finds objects which match the maximum number of three-character strings in the entered search terms, i.e. near matches. A threshold can be specified as a cutoff point,...
, are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called "fuzzy" searches
Approximate string matching
In computing, approximate string matching is the technique of finding strings that match a pattern approximately...
.
External links
- Huge (maintained) list of pattern matching links
- StringSearch – high-performance pattern matching algorithms in Java – Implementations of many String-Matching-Algorithms in Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
- Exact String Matching Algorithms — Animation in Java, Detailed description and C implementation of many algorithms.
- Boyer-Moore-Raita-Thomas