Content deleted Content added
Tags: Reverted Visual edit |
ShelfSkewed (talk | contribs) →String searching with don't cares: dab link |
||
| (30 intermediate revisions by 22 users not shown) | |||
Line 1:
{{short description|
A basic example of string searching is when the pattern and the searched text are [[Array data structure|arrays]] of elements of an [[Alphabet (computer science)|alphabet]] ([[finite set]]) Σ. Σ may be a human language alphabet, for example, the letters ''A'' through ''Z'' and other applications may use a ''binary alphabet'' (Σ = {0,1}) or a ''DNA alphabet'' (Σ = {A,C,G,T}) in [[bioinformatics]].
Line 6:
In practice, the method of feasible string-search algorithm may be affected by the string encoding. In particular, if a [[variable-width encoding]] is in use, then it may be slower to find the ''N''th character, perhaps requiring time proportional to ''N''. This may significantly slow some search algorithms. One of many possible solutions 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.{{citation needed|date=August 2017}}
== Overview ==
▲[[The New York Times|The]] most basic case of string searching involves one (often very long) string, sometimes called the ''haystack'', and one (often very short) string, sometimes called the ''needle''. The goal is to find one or more occurrences of the needle within the haystack. For example, one might search for ''to'' within:
Some books are to be tasted, others to be swallowed, and some few to be chewed and digested.
Line 14 ⟶ 13:
One might request the first occurrence of "to", which is the fourth word; or all occurrences, of which there are 3; or the last, which is the fifth word from the end.
Another common example involves "normalization". For many purposes, a search for a phrase such as "to be" should succeed even in places where there is something else intervening between the "to" and the "be":
Line 47 ⟶ 46:
=== Finite-state-automaton-based search ===
[[Image:DFA search mommy.svg|200px|right]]
In this approach, backtracking is avoided by constructing a [[deterministic finite automaton]] (DFA) that recognizes a stored search string. These are expensive to construct—they are usually created using the [[powerset construction]]—but are very quick to use. For example, the [[deterministic finite automaton|DFA]] shown to the right recognizes the word "MOMMY". This approach is frequently generalized in practice to search for arbitrary [[regular
===Stubs===
Line 73 ⟶ 72:
! Naïve algorithm
| none
| Θ(n+m) in average,<br/> O(mn)
| none
|-
! Automaton-based matching
| Θ(km)
| Θ(n)
| Θ(km)
|-
! [[Rabin–Karp algorithm|Rabin–Karp]]
Line 88 ⟶ 92:
! [[Boyer–Moore string-search algorithm|Boyer–Moore]]
| Θ(m + k)
|
| Θ(k)
|-
Line 108 ⟶ 112:
:1.{{note|Asymptotic times}}Asymptotic times are expressed using [[Big O notation|O, Ω, and Θ notation]].
:2.{{note|libc}}Used to implement the ''memmem'' and [[C string handling#Functions|''strstr'']] search functions in the [[glibc]]<ref>{{cite web |title=glibc/string/str-two-way.h |url=https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |access-date=2022-03-22 |archive-date=2020-09-20 |archive-url=https://web.archive.org/web/20200920180414/https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |url-status=live }}</ref> and [[musl]]<ref>{{cite web |title=musl/src/string/memmem.c |url=http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |access-date=23 November 2019 |archive-date=1 October 2020 |archive-url=https://web.archive.org/web/20201001184748/http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |url-status=live }}</ref> [[C standard libraries]].
:3.{{note|fuzzy+regexp}}Can be extended to handle [[approximate string matching]] and (potentially-infinite) sets of patterns represented as [[regular
The '''[[Boyer–Moore string-search algorithm]]''' has been the standard benchmark for the practical string-search literature.<ref name=":0">{{cite journal |last1=Hume |last2=Sunday |year=1991 |title=Fast String Searching |journal=Software: Practice and Experience |volume=21 |issue=11 |pages=1221–1248 |doi=10.1002/spe.4380211105 |s2cid=5902579
==== Algorithms using a finite set of patterns ====
Line 160 ⟶ 164:
! Patterns preprocessed
| Constructed search engines
| Signature methods
|}
Line 169 ⟶ 173:
* Match the suffix first (Boyer–Moore and variants, Commentz-Walter)
* Match the best factor first (BNDM, BOM, Set-BOM)
* Other strategy (Naïve, Rabin–Karp, Vectorized)
===Real-time string matching===
In real-time string matching, one requires the matcher to output a response after reading each character of the text, that indicates
whether this is the last character of a match. The response has to be given within constant time.
The requirement regarding preprocessing vary: O(''m'') preprocessing may be allowed after the pattern is read (but before the reading of
the text), or a stricter requirement may be posed according to which the matcher has to also pause for at most a constant time after reading any character of the pattern (including the last).
For the more lenient version, if one does not mind that the preprocessing time and memory requirement dependend on the size of the alphabet, a real-time solution is provided by
automaton matching.
[[Zvi Galil]] developed a method to turn certain algorithms into real-time algorithms, and applied it to produce a variant of the KMP
matcher that runs in real time under the strict requirement.<ref>{{Cite journal
| last = Galil
| first = Zvi
| title = String matching in real time
| journal = Journal of the ACM
| volume = 28
| issue = 1
| pages = 134–149
| year = 1981
| doi = 10.1145/322234.322244
| pmid =
| url =
}}</ref>
==String searching with don't cares==
In this version of the string searching problem, there is a special symbol, ø (read: don't care), which can match any other symbol (including another ø).
Don't care symbols can appear either in the pattern or in the text. In 2002, an algorithm for this problem that runs in <math>O(n\log m)</math> time has been
given by [[Richard Cole]] and [[Ramesh Hariharan]], improving on a solution from 1973 by [[Michael J. Fischer|Fischer]] and [[Michael S. Paterson|Paterson]]
that has complexity <math>O(n\log m\log k)</math>, where ''k'' is the size of the alphabet.<ref>{{Cite conference
| last1 = Cole
| first1 = Richard
| last2 = Hariharan
| first2 = Ramesh
| title = Verifying candidate matches in sparse and wildcard matching
| book-title = Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
| editor =
| publisher =
| ___location =
| pages = 592–601
| year = 2002
| url =
| doi =
}}</ref> Another algorithm, claimed simpler, has been proposed by [[Peter Clifford (mathematician)|Clifford]] and [[Raphaël Clifford|Clifford]].<ref>{{cite journal |last1=Clifford |first1=Peter |last2=Clifford |first2=Raphaël |title=Simple deterministic wildcard matching |journal=Information Processing Letters |date=January 2007 |volume=101 |issue=2 |pages=53–54 |doi=10.1016/j.ipl.2006.08.002}}</ref>
==See also==
Line 177 ⟶ 224:
*[[Compressed pattern matching]]
*[[Matching wildcards]]
*[[Approximate string matching]]
*[[Full-text search]]
Line 209 ⟶ 257:
*[http://stringsandchars.amygdalum.net/ StringsAndChars] – Implementations of many String-Matching-Algorithms (for single and multiple patterns) in Java
*[http://www-igm.univ-mlv.fr/~lecroq/string/index.html Exact String Matching Algorithms] — Animation in Java, Detailed description and C implementation of many algorithms.
*[http://www.cs.ucr.edu/~stelo/cpm/cpm04/35_Navarro.pdf (PDF) Improved Single and Multiple Approximate String Matching] {{Webarchive|url=https://web.archive.org/web/20170311221134/http://www.cs.ucr.edu/~stelo/cpm/cpm04/35_Navarro.pdf |date=2017-03-11 }}
*[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2647288/ Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features]
*[https://www.codeproject.com/Articles/5282980/Fastest-Fulltext-Vector-Scalar-Exact-Searcher NyoTengu – high-performance pattern matching algorithm in C] – Implementations of Vector and Scalar String-Matching-Algorithms in C
*[https://arxiv.org/html/2502.20338v3 Nathaniel K. Brown, et al.: "KeBaB: k-mer based breaking for finding long MEMs", arXiv:2502.20338v3 (09 Jun 2025).]
{{strings}}
| |||