String-searching algorithm - Revision history

OatPowered: /* Classification by the use of preprocessing programs */ Fix VLDB cite, update URL, add all authors and wikilink

2025-04-23T20:41:37Z

Classification by the use of preprocessing programs: Fix VLDB cite, update URL, add all authors and wikilink

← Previous revision		Revision as of 20:41, 23 April 2025
Line 159:		Line 159:
	! Patterns preprocessed		! Patterns preprocessed
	\| Constructed search engines		\| Constructed search engines
	\| Signature methods :<ref>{{citation\|~~surname1~~=~~Riad~~ ~~Mokadem~~\|~~surname2~~=Witold ~~Litwin~~ ~~http~~://www.~~cse~~.~~scu.edu~~/~~~tschwarz~~/~~Papers~~/~~vldb07_final~~.pdf\|title=Fast ~~nGramBased~~ String Search Over Data Encoded Using Algebraic Signatures \|year=2007 \|publisher=~~33rd~~ International Conference on Very Large Data Bases ~~(VLDB)~~}}</ref>		\| Signature methods<ref>{{citation \|last1=Litwin \|first1=Witold \|last2=Mokadem \|first2=Riad \|last3=Rigaux \|first3=Philippe \|last4=Schwarz \|first4=Thomas \|url=https://www.vldb.org/conf/2007/papers/research/p207-litwin.pdf \|title=Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures \|year=2007 \|publisher=[[International Conference on Very Large Data Bases]]}}</ref>

	\|}		\|}

HMSLavender: Reverted edits by 220.244.208.194 (talk) (AV)

2025-04-23T04:47:55Z

Reverted edits by 220.244.208.194 (talk) (AV)

← Previous revision		Revision as of 04:47, 23 April 2025
Line 38:		Line 38:
	This article mainly discusses algorithms for the simpler kinds of string searching.		This article mainly discusses algorithms for the simpler kinds of string searching.

			A similar problem introduced in the field of bioinformatics and genomics is the maximal exact matching (MEM).<ref>{{Cite journal\|last1=Kurtz\|first1=Stefan\|last2=Phillippy\|first2=Adam\|last3=Delcher\|first3=Arthur L\|last4=Smoot\|first4=Michael\|last5=Shumway\|first5=Martin\|last6=Antonescu\|first6=Corina\|last7=Salzberg\|first7=Steven L\|date=2004\|title=Versatile and open software for comparing large genomes \|journal=Genome Biology \|volume=5\|issue=2\|pages=R12\|doi=10.1186/gb-2004-5-2-r12\|issn=1465-6906 \|pmc= 395750\|pmid=14759262 \|doi-access=free }}</ref> Given two strings, MEMs are common substrings that cannot be extended left or right without causing a mismatch.<ref>{{Cite journal\|last1=Khan\|first1=Zia\|last2=Bloom\|first2=Joshua S.\|last3=Kruglyak\|first3=Leonid\|last4=Singh\|first4=Mona\|date=2009-07-01\|title=A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays\|url= \|journal=Bioinformatics \|volume=25\|issue=13\|pages=1609–1616\|doi=10.1093/bioinformatics/btp275 \|pmc=2732316\|pmid=19389736}}</ref>
	A similar problem introduced in the field of bioinformatics and genomics is the maximal exact matching (MEM).<ref>{{Cite journal\|last1=Kurtz\|first1=S}}</ref>

	== Examples of search algorithms ==		== Examples of search algorithms ==
Line 44:		Line 44:
	A simple and inefficient way to see where one string occurs inside another is to check at each index, one by one. First, we see if there is a copy of the needle starting at 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, 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 [[Big O notation\|O]](''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 [[Big O notation\|O]](''nm'')		A simple and inefficient way to see where one string occurs inside another is to check at each index, one by one. First, we see if there is a copy of the needle starting at 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, 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 [[Big O notation\|O]](''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 [[Big O notation\|O]](''nm'')

			=== Finite-state-automaton-based search ===
	=== Finite-state-automatoprefix of the search string, and is therefore adaptable to [[fuzzy string searching]]. The [[bitap algorithm]] is an application of Baeza–Yates' approach.
			[[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 expression]]s.

			===Stubs===
⚫	=== Index methods
			[[Knuth–Morris–Pratt algorithm\|Knuth–Morris–Pratt]] computes a [[deterministic finite automaton\|DFA]] that recognizes inputs with the string to search for as a suffix, [[Boyer–Moore string-search algorithm\|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.
⚫	Faster search algorithms preprocess the text. After building a [[substring index]], for example a [[suffix tree]] or [[suffix array]], the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in <math>\Theta(n)</math> time, and all <math>z</~~mat~~] from the root of the suffix tree.

		⚫	=== Index methods ===
		⚫	Faster search algorithms preprocess the text. After building a [[substring index]], for example a [[suffix tree]] or [[suffix array]], the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in <math>\Theta(n)</math> time, and all <math>z</math> occurrences of a pattern can be found in <math>O(m)</math> time under the assumption that the alphabet has a constant size and all inner nodes in the suffix tree know what leaves are underneath them. The latter can be accomplished by running a [[Depth-first search\|DFS algorithm]] from the root of the suffix tree.

	=== Other variants ===		=== Other variants ===
Line 82:		Line 87:
	! [[Boyer–Moore string-search algorithm\|Boyer–Moore]]		! [[Boyer–Moore string-search algorithm\|Boyer–Moore]]
	\| Θ(m + k)		\| Θ(m + k)
			\| Ω(n/m) at best,<br/> O(mn) at worst
⚫	\| Ω(~~n/m~~) at be=https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|publisher=Springer Berlin Heidelberg \|series=Lecture Notes in Computer Science \|isbn=978-3-540-64739-3 \|access-date=2019-11-22 \|archive-date=2019-01-05 \|archive-url=https://web.archive.org/web/20190105101910/https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|url-status=live }}</ref>{{ref\|fuzzy+regexp}}
			\| Θ(k)
			\|-
			! [[Two-way string-matching algorithm\|Two-way algorithm]]<ref>{{cite journal \|last1=Crochemore \|first1=Maxime \|last2=Perrin \|first2=Dominique \|title=Two-way string-matching \|journal=Journal of the ACM \|date=1 July 1991 \|volume=38 \|issue=3 \|pages=650–674 \|doi=10.1145/116825.116845 \|s2cid=15055316 \|url=http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf \|access-date=5 April 2019 \|archive-date=24 November 2021 \|archive-url=https://web.archive.org/web/20211124025145/http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf \|url-status=live }}</ref>{{ref\|libc}}
			\| Θ(m)
			\| O(n)
			\| O(log(m))
			\|-
		⚫	! Backward Non-Deterministic [[Suffix automaton\|DAWG]] Matching (BNDM)<ref>{{cite book \|last1=Navarro \|first1=Gonzalo \|last2=Raffinot \|first2=Mathieu \|title=Combinatorial Pattern Matching \|chapter=A bit-parallel approach to suffix automata: Fast extended string matching \|date=1998 \|volume=1448 \|pages=14–33 \|doi=10.1007/bfb0030778 \|chapter-url=https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|publisher=Springer Berlin Heidelberg \|series=Lecture Notes in Computer Science \|isbn=978-3-540-64739-3 \|access-date=2019-11-22 \|archive-date=2019-01-05 \|archive-url=https://web.archive.org/web/20190105101910/https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|url-status=live }}</ref>{{ref\|fuzzy+regexp}}
	\| O(m)		\| O(m)
	\| Ω(n/m) at best,<br/> O(mn) at worst		\| Ω(n/m) at best,<br/> O(mn) at worst
Line 97:		Line 110:

	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 }}</ref>		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 }}</ref>

	'=0-86\3U46M7IUNRBT2H5J75213RVT
	==== Algorithms using a finite set of patterns ====		==== Algorithms using a finite set of patterns ====
	In the following compilation, ''M'' is the length of the longest pattern, ''m'' their total length, ''n'' the length of the searchable text, ''o'' the number of occurrences.		In the following compilation, ''M'' is the length of the longest pattern, ''m'' their total length, ''n'' the length of the searchable text, ''o'' the number of occurrences.
Line 115:		Line 128:
	\| Θ(m)		\| Θ(m)
	\|-		\|-
	! [[Commentz		! [[Commentz-Walter algorithm\|Commentz-Walter]]
	r algorithm\|Commentz-Walter]]
	\| [[Boyer–Moore string-search algorithm\|Boyer-Moore]]		\| [[Boyer–Moore string-search algorithm\|Boyer-Moore]]
	\| Θ(m)		\| Θ(m)
Line 135:		Line 147:
	Other classification approaches are possible. One of the most common uses preprocessing as main criteria.		Other classification approaches are possible. One of the most common uses preprocessing as main criteria.

	{\| class="wikitable"~~frctuvyifxrzyfhvugofdtfyi~~		{\| class="wikitable"
	\|+Classes of string searching algorithms<ref>Melichar, Borivoj, Jan Holub, and J. Polcar. Text Searching Algorithms. Volume I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ {{Webarchive\|url=https://web.archive.org/web/20160304074815/http://stringology.org/athens/TextSearchingAlgorithms/ \|date=2016-03-04 }}.</ref>		\|+Classes of string searching algorithms<ref>Melichar, Borivoj, Jan Holub, and J. Polcar. Text Searching Algorithms. Volume I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ {{Webarchive\|url=https://web.archive.org/web/20160304074815/http://stringology.org/athens/TextSearchingAlgorithms/ \|date=2016-03-04 }}.</ref>
	!		!

220.244.208.194: wvhdioooo

2025-04-23T04:47:14Z

wvhdioooo

← Previous revision		Revision as of 04:47, 23 April 2025
Line 38:		Line 38:
	This article mainly discusses algorithms for the simpler kinds of string searching.		This article mainly discusses algorithms for the simpler kinds of string searching.

			A similar problem introduced in the field of bioinformatics and genomics is the maximal exact matching (MEM).<ref>{{Cite journal\|last1=Kurtz\|first1=S}}</ref>
	A similar problem introduced in the field of bioinformatics and genomics is the maximal exact matching (MEM).<ref>{{Cite journal\|last1=Kurtz\|first1=Stefan\|last2=Phillippy\|first2=Adam\|last3=Delcher\|first3=Arthur L\|last4=Smoot\|first4=Michael\|last5=Shumway\|first5=Martin\|last6=Antonescu\|first6=Corina\|last7=Salzberg\|first7=Steven L\|date=2004\|title=Versatile and open software for comparing large genomes \|journal=Genome Biology \|volume=5\|issue=2\|pages=R12\|doi=10.1186/gb-2004-5-2-r12\|issn=1465-6906 \|pmc= 395750\|pmid=14759262 \|doi-access=free }}</ref> Given two strings, MEMs are common substrings that cannot be extended left or right without causing a mismatch.<ref>{{Cite journal\|last1=Khan\|first1=Zia\|last2=Bloom\|first2=Joshua S.\|last3=Kruglyak\|first3=Leonid\|last4=Singh\|first4=Mona\|date=2009-07-01\|title=A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays\|url= \|journal=Bioinformatics \|volume=25\|issue=13\|pages=1609–1616\|doi=10.1093/bioinformatics/btp275 \|pmc=2732316\|pmid=19389736}}</ref>

	== Examples of search algorithms ==		== Examples of search algorithms ==
Line 44:		Line 44:
	A simple and inefficient way to see where one string occurs inside another is to check at each index, one by one. First, we see if there is a copy of the needle starting at 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, 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 [[Big O notation\|O]](''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 [[Big O notation\|O]](''nm'')		A simple and inefficient way to see where one string occurs inside another is to check at each index, one by one. First, we see if there is a copy of the needle starting at 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, 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 [[Big O notation\|O]](''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 [[Big O notation\|O]](''nm'')

			=== Finite-state-automatoprefix of the search string, and is therefore adaptable to [[fuzzy string searching]]. The [[bitap algorithm]] is an application of Baeza–Yates' approach.
	=== 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 expression]]s.

		⚫	=== Index methods
	===Stubs===
		⚫	Faster search algorithms preprocess the text. After building a [[substring index]], for example a [[suffix tree]] or [[suffix array]], the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in <math>\Theta(n)</math> time, and all <math>z</mat] from the root of the suffix tree.
	[[Knuth–Morris–Pratt algorithm\|Knuth–Morris–Pratt]] computes a [[deterministic finite automaton\|DFA]] that recognizes inputs with the string to search for as a suffix, [[Boyer–Moore string-search algorithm\|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.

⚫	=== Index methods ~~===~~
⚫	Faster search algorithms preprocess the text. After building a [[substring index]], for example a [[suffix tree]] or [[suffix array]], the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in <math>\Theta(n)</math> time, and all <math>z</math> occurrences of a pattern can be found in <math>O(m)</math> time under the assumption that the alphabet has a constant size and all inner nodes in the suffix tree know what leaves are underneath them. The latter can be accomplished by running a [[Depth-first search\|DFS algorithm]] from the root of the suffix tree.

	=== Other variants ===		=== Other variants ===
Line 87:		Line 82:
	! [[Boyer–Moore string-search algorithm\|Boyer–Moore]]		! [[Boyer–Moore string-search algorithm\|Boyer–Moore]]
	\| Θ(m + k)		\| Θ(m + k)
		⚫	\| Ω(n/m) at be=https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|publisher=Springer Berlin Heidelberg \|series=Lecture Notes in Computer Science \|isbn=978-3-540-64739-3 \|access-date=2019-11-22 \|archive-date=2019-01-05 \|archive-url=https://web.archive.org/web/20190105101910/https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|url-status=live }}</ref>{{ref\|fuzzy+regexp}}
	\| Ω(n/m) at best,<br/> O(mn) at worst
	\| Θ(k)
	\|-
	! [[Two-way string-matching algorithm\|Two-way algorithm]]<ref>{{cite journal \|last1=Crochemore \|first1=Maxime \|last2=Perrin \|first2=Dominique \|title=Two-way string-matching \|journal=Journal of the ACM \|date=1 July 1991 \|volume=38 \|issue=3 \|pages=650–674 \|doi=10.1145/116825.116845 \|s2cid=15055316 \|url=http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf \|access-date=5 April 2019 \|archive-date=24 November 2021 \|archive-url=https://web.archive.org/web/20211124025145/http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf \|url-status=live }}</ref>{{ref\|libc}}
	\| Θ(m)
	\| O(n)
	\| O(log(m))
	\|-
⚫	~~! Backward Non-Deterministic [[Suffix automaton~~\|~~DAWG]] Matching~~ (~~BNDM~~)~~<ref>{{cite~~ ~~book~~ \|last1=Navarro \|first1=Gonzalo \|last2=Raffinot \|first2=Mathieu \|title=Combinatorial Pattern Matching \|chapter=A bit-parallel approach to suffix automata: Fast extended string matching \|date=1998 \|volume=1448 \|pages=14–33 \|doi=10.1007/bfb0030778 \|chapter-url=https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|publisher=Springer Berlin Heidelberg \|series=Lecture Notes in Computer Science \|isbn=978-3-540-64739-3 \|access-date=2019-11-22 \|archive-date=2019-01-05 \|archive-url=https://web.archive.org/web/20190105101910/https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf \|url-status=live }}</ref>{{ref\|fuzzy+regexp}}
	\| O(m)		\| O(m)
	\| Ω(n/m) at best,<br/> O(mn) at worst		\| Ω(n/m) at best,<br/> O(mn) at worst
Line 110:		Line 97:

	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 }}</ref>		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 }}</ref>
			'=0-86\3U46M7IUNRBT2H5J75213RVT

	==== Algorithms using a finite set of patterns ====		==== Algorithms using a finite set of patterns ====
	In the following compilation, ''M'' is the length of the longest pattern, ''m'' their total length, ''n'' the length of the searchable text, ''o'' the number of occurrences.		In the following compilation, ''M'' is the length of the longest pattern, ''m'' their total length, ''n'' the length of the searchable text, ''o'' the number of occurrences.
Line 128:		Line 115:
	\| Θ(m)		\| Θ(m)
	\|-		\|-
	! [[Commentz~~-Walter~~ algorithm\|Commentz-Walter]]		! [[Commentz
			r algorithm\|Commentz-Walter]]
	\| [[Boyer–Moore string-search algorithm\|Boyer-Moore]]		\| [[Boyer–Moore string-search algorithm\|Boyer-Moore]]
	\| Θ(m)		\| Θ(m)
Line 147:		Line 135:
	Other classification approaches are possible. One of the most common uses preprocessing as main criteria.		Other classification approaches are possible. One of the most common uses preprocessing as main criteria.

	{\| class="wikitable"		{\| class="wikitable"frctuvyifxrzyfhvugofdtfyi
	\|+Classes of string searching algorithms<ref>Melichar, Borivoj, Jan Holub, and J. Polcar. Text Searching Algorithms. Volume I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ {{Webarchive\|url=https://web.archive.org/web/20160304074815/http://stringology.org/athens/TextSearchingAlgorithms/ \|date=2016-03-04 }}.</ref>		\|+Classes of string searching algorithms<ref>Melichar, Borivoj, Jan Holub, and J. Polcar. Text Searching Algorithms. Volume I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ {{Webarchive\|url=https://web.archive.org/web/20160304074815/http://stringology.org/athens/TextSearchingAlgorithms/ \|date=2016-03-04 }}.</ref>
	!		!

MrOllie: Reverted 1 edit by Jerzy.Respondek (talk): Rv citespam

2025-03-18T21:29:49Z

Reverted 1 edit by Jerzy.Respondek (talk): Rv citespam

← Previous revision		Revision as of 21:29, 18 March 2025
Line 55:		Line 55:

	=== Other variants ===		=== Other variants ===
	Some search methods, for instance [[trigram search]], are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called [[Approximate string matching\|"fuzzy" searches]]. Also fast matrix multiplication algorithms can be used <ref>{{cite book\|title=Fast Matrix Multiplication with Applications, Ch. 9 \| last = Respondek \| first = J.S. \| publisher=Springer Cham\| series=Studies in Big Data \|volume=166\| date=2025 \|isbn=978-3-031-76929-0 \|url=https://link.springer.com/chapter/10.1007/978-3-031-76930-6_9}}</ref>.		Some search methods, for instance [[trigram search]], are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called [[Approximate string matching\|"fuzzy" searches]].

	== Classification of search algorithms ==		== Classification of search algorithms ==

Jerzy.Respondek at 21:28, 18 March 2025

2025-03-18T21:28:22Z

← Previous revision		Revision as of 21:28, 18 March 2025
Line 55:		Line 55:

	=== Other variants ===		=== Other variants ===
	Some search methods, for instance [[trigram search]], are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called [[Approximate string matching\|"fuzzy" searches]].		Some search methods, for instance [[trigram search]], are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called [[Approximate string matching\|"fuzzy" searches]]. Also fast matrix multiplication algorithms can be used <ref>{{cite book\|title=Fast Matrix Multiplication with Applications, Ch. 9 \| last = Respondek \| first = J.S. \| publisher=Springer Cham\| series=Studies in Big Data \|volume=166\| date=2025 \|isbn=978-3-031-76929-0 \|url=https://link.springer.com/chapter/10.1007/978-3-031-76930-6_9}}</ref>.

	== Classification of search algorithms ==		== Classification of search algorithms ==

Stevebroshar: the target need not be larger (although probably won't find if it's smaller); singular reads better than plural

2024-12-20T13:58:15Z

the target need not be larger (although probably won't find if it's smaller); singular reads better than plural

← Previous revision		Revision as of 13:58, 20 December 2024
Line 1:		Line 1:
	{{short description\|~~Searches~~ for patterns ~~within~~ ~~strings~~}}		{{short description\|Searching for patterns in text}}
	~~In [[computer science]],~~ '''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~~ [[string (computer science)\|~~strings~~]] ~~(also~~ ~~called~~ ~~patterns)~~ ~~are~~ ~~found~~ ~~within a larger string or text~~.		A '''string-searching algorithm''', sometimes called '''string-matching algorithm''', is an [[algorithm]] that searches a body of [[string (computer science)\|text]] for portions that match by pattern.

	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]].		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]].

ClueBot NG: Reverting possible vandalism by 113.161.109.242 to version by 2A0D:6FC2:5E30:9A00:71BB:FAF7:C2A:B6B2. Report False Positive? Thanks, ClueBot NG. (4360169) (Bot)

2024-11-25T04:23:46Z

Reverting possible vandalism by 113.161.109.242 to version by 2A0D:6FC2:5E30:9A00:71BB:FAF7:C2A:B6B2. Report False Positive? Thanks, ClueBot NG. (4360169) (Bot)

← Previous revision		Revision as of 04:23, 25 November 2024
Line 2:		Line 2:
	In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.		In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.

	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]]. ~~Hello~~		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]].

	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}}		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}}

113.161.109.242: aaa

2024-11-25T04:23:28Z

aaa

← Previous revision		Revision as of 04:23, 25 November 2024
Line 2:		Line 2:
	In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.		In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.

	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]].		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]]. Hello

	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}}		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}}

2A0D:6FC2:5E30:9A00:71BB:FAF7:C2A:B6B2: /* Single-pattern algorithms */

2024-09-20T09:32:31Z

Single-pattern algorithms

← Previous revision		Revision as of 09:32, 20 September 2024
Line 72:		Line 72:
	! Naïve algorithm		! Naïve algorithm
	\| none		\| none
	\| Θ(n+m) in average,<br/> Θ(mn)		\| Θ(n+m) in average,<br/> O(mn)
	\| none		\| none
	\|-		\|-

ReiniUrban: /* Classification by matching strategies */Add Vectorized (eg. the current best EPSM) as other strategy

2024-04-07T14:01:20Z

Classification by matching strategies: Add Vectorized (eg. the current best EPSM) as other strategy

← Previous revision		Revision as of 14:01, 7 April 2024
Line 168:		Line 168:
	* Match the suffix first (Boyer–Moore and variants, Commentz-Walter)		* Match the suffix first (Boyer–Moore and variants, Commentz-Walter)
	* Match the best factor first (BNDM, BOM, Set-BOM)		* Match the best factor first (BNDM, BOM, Set-BOM)
	* Other strategy (Naïve, Rabin–Karp)		* Other strategy (Naïve, Rabin–Karp, Vectorized)

	==See also==		==See also==

← Previous revision		Revision as of 13:58, 20 December 2024
Line 1:		Line 1:
	{{short description\|~~Searches~~ for patterns ~~within~~ ~~strings~~}}		{{short description\|Searching for patterns in text}}
	~~In [[computer science]],~~ '''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~~ [[string (computer science)\|~~strings~~]] ~~(also~~ ~~called~~ ~~patterns)~~ ~~are~~ ~~found~~ ~~within a larger string or text~~.		A '''string-searching algorithm''', sometimes called '''string-matching algorithm''', is an [[algorithm]] that searches a body of [[string (computer science)\|text]] for portions that match by pattern.

	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]].		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]].

← Previous revision		Revision as of 04:23, 25 November 2024
Line 2:		Line 2:
	In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.		In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.

	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]]. ~~Hello~~		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]].

	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}}		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}}

← Previous revision		Revision as of 04:23, 25 November 2024
Line 2:		Line 2:
	In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.		In [[computer science]], '''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 [[string (computer science)\|strings]] (also called patterns) are found within a larger string or text.

	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]].		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]]. Hello

	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}}		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}}