Talk:String-searching algorithm - Revision history

Cewbot: Maintain {{WPBS}} and vital articles: 1 WikiProject template. Merge {{VA}} into {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{WikiProject Computer science}}.

2024-01-07T01:00:52Z

Maintain {{WPBS}} and vital articles: 1 WikiProject template. Merge {{VA}} into {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{WikiProject Computer science}}.

← Previous revision		Revision as of 01:00, 7 January 2024
Line 1:		Line 1:
			{{WikiProject banner shell\|class=Start\|vital=yes\|1=
	{{Vital article\|topic=Mathematics\|level=5\|class=Start}}
	{{WikiProject Computer science\|importance=high~~\|class=start~~}}		{{WikiProject Computer science\|importance=high}}
			}}

	==Untitled==		==Untitled==

67.198.37.16: remove wikiproject maths banner

2023-11-17T01:44:46Z

remove wikiproject maths banner

← Previous revision		Revision as of 01:44, 17 November 2023
Line 1:		Line 1:
	{{Vital article\|topic=Mathematics\|level=5\|class=Start}}		{{Vital article\|topic=Mathematics\|level=5\|class=Start}}
	{{WikiProject Mathematics\|class=
	}}
	{{WikiProject Computer science\|importance=high\|class=start}}		{{WikiProject Computer science\|importance=high\|class=start}}

181.94.242.100 at 06:24, 13 April 2023

2023-04-13T06:24:25Z

← Previous revision		Revision as of 06:24, 13 April 2023
Line 9:		Line 9:
	These descriptions are insufficient!		These descriptions are insufficient!

	<i>~~Could~~ somebody expand this entry ?</i>		<i>Couldm somebody expand this entry ?</i>

	The "Finite Automata" link is entirely unhelpful, redirection to a page about finite state machines that has no information on string searching. --[[User:Furrykef\|Furrykef]] 05:53, 29 Jun 2004 (UTC)		The "Finite Automata" link is entirely unhelpful, redirection to a page about finite state machines that has no information on string searching. --[[User:Furrykef\|Furrykef]] 05:53, 29 Jun 2004 (UTC)

Smasongarrison: Category:Wikipedia vital articles in Mathematics, Added {{WikiProject Mathematics}}

2023-02-16T03:18:37Z

Category:Wikipedia vital articles in Mathematics, Added {{WikiProject Mathematics}}

← Previous revision		Revision as of 03:18, 16 February 2023
Line 1:		Line 1:
	{{Vital article\|topic=Mathematics\|level=5\|class=Start}}		{{Vital article\|topic=Mathematics\|level=5\|class=Start}}
			{{WikiProject Mathematics\|class=
			}}
	{{WikiProject Computer science\|importance=high\|class=start}}		{{WikiProject Computer science\|importance=high\|class=start}}

SSTbot: Added {{vital article}}

2018-08-01T13:15:00Z

Added {{vital article}}

← Previous revision		Revision as of 13:15, 1 August 2018
Line 1:		Line 1:
			{{Vital article\|topic=Mathematics\|level=5\|class=Start}}
	{{WikiProject Computer science\|importance=high\|class=start}}		{{WikiProject Computer science\|importance=high\|class=start}}

			==Untitled==
	''Moved from article''		''Moved from article''

LordOfPens: LordOfPens moved page Talk:String searching algorithm to Talk:String-searching algorithm: Missing hyphen in compound modifier

2018-06-12T17:15:48Z

LordOfPens moved page Talk:String searching algorithm to Talk:String-searching algorithm: Missing hyphen in compound modifier

← Previous revision	Revision as of 17:15, 12 June 2018
(No difference)

SineBot: Signing comment by Sderose - "/* Two-way string search algorithm */"

2017-08-31T20:29:05Z

Signing comment by Sderose - "Two-way string search algorithm: "

← Previous revision		Revision as of 20:29, 31 August 2017
Line 57:		Line 57:
	*In strings, the length is highly variable, and the length in and of itself is of little importance; in linear algebra the length of a vector is an extremely important intrinsic property. This again shows they are quite different concepts, and one cannot trivially be a "formal" model for another.		*In strings, the length is highly variable, and the length in and of itself is of little importance; in linear algebra the length of a vector is an extremely important intrinsic property. This again shows they are quite different concepts, and one cannot trivially be a "formal" model for another.

	*Saying "Formally" suggested the introduction of a mathematical model which covers the important properties of a certain thing. No such model is in evidence. The mathematical properties of vector spaces are not even a basically correct model of strings, and do not approach being adequate, much less conceptually helpful.		*Saying "Formally" suggested the introduction of a mathematical model which covers the important properties of a certain thing. No such model is in evidence. The mathematical properties of vector spaces are not even a basically correct model of strings, and do not approach being adequate, much less conceptually helpful. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Sderose\|Sderose]] ([[User talk:Sderose#top\|talk]] • [[Special:Contributions/Sderose\|contribs]]) 20:28, 31 August 2017 (UTC)</small> <!--Autosigned by SineBot-->

Sderose: /* Two-way string search algorithm */

2017-08-31T20:28:03Z

Two-way string search algorithm

← Previous revision		Revision as of 20:28, 31 August 2017
Line 41:		Line 41:

	This page seems to forget to mention the existence of the [http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf two-way string-matching] algorithm, which provides a worst-case running time of O(n+m). This is the algorithm used by glibc's strstr() function, for example. [[User:EdSchouten\|EdSchouten]] ([[User talk:EdSchouten\|talk]]) 10:18, 20 June 2016 (UTC)		This page seems to forget to mention the existence of the [http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf two-way string-matching] algorithm, which provides a worst-case running time of O(n+m). This is the algorithm used by glibc's strstr() function, for example. [[User:EdSchouten\|EdSchouten]] ([[User talk:EdSchouten\|talk]]) 10:18, 20 June 2016 (UTC)

			== Reference to "vector_space" ==

			Have just corrected where intro said strings are "formally" "vectors", and linked to [[vector_space]]. Perhaps someone merely accidentally linked to the wrong sense of "vector"; but it's incorrect as well as unhelpful. It was never mentioned again in the article, never had a connection described, and was unsourced). I changed it to [[Array_data_structure\|array]], which is not without problems, but at least a common basic analogy, and I removed the "formal", because it the analogy does not approach formality (nor does it need to).

			*Character strings are sequences of characters, not numeric quantities. There is no intrinsic relationship between "A" and 1 (or 65), or between control characters, ligatures, diacritics, etc., etc. Character strings (not to mention DNA base-pair sequences) existed millennia before ASCII.

			Even a coded* character string in a particular coded character set, is a sequence of integers draw from an extremely small set (even for Unicode), whereas even the infinite set of integers do not constitute a [Field_(mathematics)\|field], which is required to define a vector space. Characters do not support addition, subtraction, multiplication, and division:
			**What is "C" + 1? Not "D" if it's EBCDIC; and the integer 1 is not a character anyway, so we could only refer to "C" + "1", which may be a totally different thing)
			*What is "C" "#"?
			**What is "Z"/" "?

			*Strings do not behave like a space (or lattice) of numbers. One does not typically do linear algebra on strings. The dot product of two strings is an unusual notion (dot products are important in information theory, on arrays of words; but not for "string searching" per se). Affine transforms would be very strange way to do case-folding or space-normalizaiton (both highly important in string searching), if possible at all.

			*In strings, the length is highly variable, and the length in and of itself is of little importance; in linear algebra the length of a vector is an extremely important intrinsic property. This again shows they are quite different concepts, and one cannot trivially be a "formal" model for another.

			*Saying "Formally" suggested the introduction of a mathematical model which covers the important properties of a certain thing. No such model is in evidence. The mathematical properties of vector spaces are not even a basically correct model of strings, and do not approach being adequate, much less conceptually helpful.

EdSchouten: /* Two-way string search algorithm */

2016-06-20T10:18:34Z

Two-way string search algorithm

← Previous revision		Revision as of 10:18, 20 June 2016
Line 40:		Line 40:
	== Two-way string search algorithm ==		== Two-way string search algorithm ==

	This page seems to forget to mention the existence of the [http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf\|two-way string-matching] algorithm, which provides a worst-case running time of O(n+m). This is the algorithm used by glibc's strstr() function, for example. [[User:EdSchouten\|EdSchouten]] ([[User talk:EdSchouten\|talk]]) 10:18, 20 June 2016 (UTC)		This page seems to forget to mention the existence of the [http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf two-way string-matching] algorithm, which provides a worst-case running time of O(n+m). This is the algorithm used by glibc's strstr() function, for example. [[User:EdSchouten\|EdSchouten]] ([[User talk:EdSchouten\|talk]]) 10:18, 20 June 2016 (UTC)

EdSchouten: /* Two-way string search algorithm */ new section

2016-06-20T10:18:10Z

Two-way string search algorithm: new section

← Previous revision		Revision as of 10:18, 20 June 2016
Line 37:		Line 37:

	Alpha Skip Search was published at Combinatorial Pattern Matching 1998. The method appears to be optimal on average, for all alphabet sizes, and large M,N. Keys are sequences of logM letters. Preprocess the pattern into a lookup table with M-logM+1 keys of size logM (log base is alphabet size), encoding the key position in the pattern. Then skip through the text by length M-logM+1, building a logM sized key, and try to match the key in the lookup table. If a match is found, then try naively to match the pattern at the implied start position in the text. The expected run time of the algorithm is O((N/M + M)logM) for all alphabet sizes, including 2! Daniel Pehoushek [[Special:Contributions/24.33.70.144\|24.33.70.144]] ([[User talk:24.33.70.144\|talk]]) 18:45, 24 August 2014 (UTC)		Alpha Skip Search was published at Combinatorial Pattern Matching 1998. The method appears to be optimal on average, for all alphabet sizes, and large M,N. Keys are sequences of logM letters. Preprocess the pattern into a lookup table with M-logM+1 keys of size logM (log base is alphabet size), encoding the key position in the pattern. Then skip through the text by length M-logM+1, building a logM sized key, and try to match the key in the lookup table. If a match is found, then try naively to match the pattern at the implied start position in the text. The expected run time of the algorithm is O((N/M + M)logM) for all alphabet sizes, including 2! Daniel Pehoushek [[Special:Contributions/24.33.70.144\|24.33.70.144]] ([[User talk:24.33.70.144\|talk]]) 18:45, 24 August 2014 (UTC)

			== Two-way string search algorithm ==

			This page seems to forget to mention the existence of the [http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf\|two-way string-matching] algorithm, which provides a worst-case running time of O(n+m). This is the algorithm used by glibc's strstr() function, for example. [[User:EdSchouten\|EdSchouten]] ([[User talk:EdSchouten\|talk]]) 10:18, 20 June 2016 (UTC)