Talk:Bitap algorithm - Revision history

Qwerfjkl (bot): Implementing WP:PIQA (Task 26)

2024-01-28T02:06:24Z

← Previous revision		Revision as of 02:06, 28 January 2024
Line 1:		Line 1:
			{{WikiProject banner shell\|class=Start\|
	{{WikiProject Computer science		{{WikiProject Computer science
	\|class=start
	\|importance=low		\|importance=low
			}}
	}}		}}

GreenC bot: Add {{reflist-talk}} to #The Myers algorithm is not a modification of bitap (via reftalk bot)

2022-03-03T14:11:56Z

Add {{reflist-talk}} to #The Myers algorithm is not a modification of bitap (via reftalk bot)

← Previous revision		Revision as of 14:11, 3 March 2022
Line 107:		Line 107:

	The bitap algorithm can be thought of as being based on nondeterministic automata<ref>{{cite journal \|last1=Navarro \|first1=Gonzalo \|title=A guided tour to approximate string matching \|journal=ACM Computing Surveys \|date=1 March 2001 \|volume=33 \|issue=1 \|pages=31–88 \|doi=https://doi.org/10.1145/375360.375365}} See section 7.2.1</ref>. The Myers algorithm uses a completely different technique based on the dynamic programming matrix<ref>{{cite journal \|last1=Navarro \|first1=Gonzalo \|title=A guided tour to approximate string matching \|journal=ACM Computing Surveys \|date=1 March 2001 \|volume=33 \|issue=1 \|pages=31–88 \|doi=https://doi.org/10.1145/375360.375365}} See section 7.3.2</ref>. So it is incorrect to say that Myers modified the algorithm for long patterns. I've removed the line that said that the bitap algorithm was modified by Myers in 1998 for long patterns.		The bitap algorithm can be thought of as being based on nondeterministic automata<ref>{{cite journal \|last1=Navarro \|first1=Gonzalo \|title=A guided tour to approximate string matching \|journal=ACM Computing Surveys \|date=1 March 2001 \|volume=33 \|issue=1 \|pages=31–88 \|doi=https://doi.org/10.1145/375360.375365}} See section 7.2.1</ref>. The Myers algorithm uses a completely different technique based on the dynamic programming matrix<ref>{{cite journal \|last1=Navarro \|first1=Gonzalo \|title=A guided tour to approximate string matching \|journal=ACM Computing Surveys \|date=1 March 2001 \|volume=33 \|issue=1 \|pages=31–88 \|doi=https://doi.org/10.1145/375360.375365}} See section 7.3.2</ref>. So it is incorrect to say that Myers modified the algorithm for long patterns. I've removed the line that said that the bitap algorithm was modified by Myers in 1998 for long patterns.

			{{reflist-talk}}

Suapajh: /* The Myers algorithm is not a modification of bitap */ new section

2022-01-02T06:44:20Z

The Myers algorithm is not a modification of bitap: new section

← Previous revision		Revision as of 06:44, 2 January 2022
Line 101:		Line 101:

	Cheers.—[[User:InternetArchiveBot\|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot\|Report bug]])</span> 09:05, 3 November 2016 (UTC)		Cheers.—[[User:InternetArchiveBot\|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot\|Report bug]])</span> 09:05, 3 November 2016 (UTC)

			== The Myers algorithm is not a modification of bitap ==

			Firstly, let me preface this by saying that it is true that both the bitap algorithm and the Myers algorithm are bit parallel approximate string matching algorithms. But the Myers algorithm and bitap are based on completely different techniques.

			The bitap algorithm can be thought of as being based on nondeterministic automata<ref>{{cite journal \|last1=Navarro \|first1=Gonzalo \|title=A guided tour to approximate string matching \|journal=ACM Computing Surveys \|date=1 March 2001 \|volume=33 \|issue=1 \|pages=31–88 \|doi=https://doi.org/10.1145/375360.375365}} See section 7.2.1</ref>. The Myers algorithm uses a completely different technique based on the dynamic programming matrix<ref>{{cite journal \|last1=Navarro \|first1=Gonzalo \|title=A guided tour to approximate string matching \|journal=ACM Computing Surveys \|date=1 March 2001 \|volume=33 \|issue=1 \|pages=31–88 \|doi=https://doi.org/10.1145/375360.375365}} See section 7.3.2</ref>. So it is incorrect to say that Myers modified the algorithm for long patterns. I've removed the line that said that the bitap algorithm was modified by Myers in 1998 for long patterns.

Qzekrom: add rating

2019-02-22T21:46:29Z

add rating

← Previous revision		Revision as of 21:46, 22 February 2019
Line 1:		Line 1:
	{{WikiProject Computer science}}		{{WikiProject Computer science
			\|class=start
			\|importance=low
			}}

	=='It performs best on patterns less than a constant length'==		=='It performs best on patterns less than a constant length'==

InternetArchiveBot: Notification of altered sources needing review #IABot (v1.2.6)

2016-11-03T09:05:19Z

Notification of altered sources needing review #IABot (v1.2.6)

← Previous revision		Revision as of 09:05, 3 November 2016
Line 85:		Line 85:
	# Now you will hate me even more, but... spacing and indentation! At least be consistent. How is one time you are writing x=y and the other time x = y?		# Now you will hate me even more, but... spacing and indentation! At least be consistent. How is one time you are writing x=y and the other time x = y?
	[[Special:Contributions/79.176.215.66\|79.176.215.66]] ([[User talk:79.176.215.66\|talk]]) 13:36, 31 October 2012 (UTC)		[[Special:Contributions/79.176.215.66\|79.176.215.66]] ([[User talk:79.176.215.66\|talk]]) 13:36, 31 October 2012 (UTC)

			== External links modified ==

			Hello fellow Wikipedians,

			I have just modified {{plural:1\|one external link\|1 external links}} on [[Bitap algorithm]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=747604802 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot\|this simple FaQ]] for additional information. I made the following changes:
			*Added archive https://web.archive.org/web/20120122013152/http://www.cod5.ch:80/archive/l/libbitap.html to http://www.cod5.ch/archive/l/libbitap.html

			When you have finished reviewing my changes, please set the ''checked'' parameter below to '''true''' or '''failed''' to let others know (documentation at {{tlx\|Sourcecheck}}).

			{{sourcecheck\|checked=false}}

			Cheers.—[[User:InternetArchiveBot\|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot\|Report bug]])</span> 09:05, 3 November 2016 (UTC)

79.176.215.66: /* Improve code quality */

2012-10-31T13:39:23Z

Improve code quality

← Previous revision		Revision as of 13:39, 31 October 2012
Line 82:		Line 82:
	# Writing a short description of what function is doing (for example: ''Given the string TEXT searches for the PATTERN string inside the TEXT and returns... whoops, there's no consensus on what the function returns, the value appears to be somewhat random in corner cases.'')		# Writing a short description of what function is doing (for example: ''Given the string TEXT searches for the PATTERN string inside the TEXT and returns... whoops, there's no consensus on what the function returns, the value appears to be somewhat random in corner cases.'')
	# Remove the Captain Obvious comments. It is trivial knowledge that malloc allocates memory, only complex or non-intuitive parts require commenting.		# Remove the Captain Obvious comments. It is trivial knowledge that malloc allocates memory, only complex or non-intuitive parts require commenting.
	# Add comments, where it is not trivial. For example, it is not clear why if R(m) is not equal to zero the outer loop should terminate (hint: this is the most important part of the algorithm).		# Add comments, where it is not trivial. For example, it is not clear why if R[m] is not equal to zero the outer loop should terminate (hint: this is the most important part of the algorithm).
	# Now you will hate me even more, but... spacing and indentation! At least be consistent. How is one time you are writing x=y and the other time x = y?		# Now you will hate me even more, but... spacing and indentation! At least be consistent. How is one time you are writing x=y and the other time x = y?
	[[Special:Contributions/79.176.215.66\|79.176.215.66]] ([[User talk:79.176.215.66\|talk]]) 13:36, 31 October 2012 (UTC)		[[Special:Contributions/79.176.215.66\|79.176.215.66]] ([[User talk:79.176.215.66\|talk]]) 13:36, 31 October 2012 (UTC)

79.176.215.66: /* Improve code quality */ new section

2012-10-31T13:36:51Z

Improve code quality: new section

← Previous revision		Revision as of 13:36, 31 October 2012
Line 74:		Line 74:

	http://code.google.com/p/google-diff-match-patch/ <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Maasha\|Maasha]] ([[User talk:Maasha\|talk]] • [[Special:Contributions/Maasha\|contribs]]) 08:21, 30 March 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		http://code.google.com/p/google-diff-match-patch/ <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Maasha\|Maasha]] ([[User talk:Maasha\|talk]] • [[Special:Contributions/Maasha\|contribs]]) 08:21, 30 March 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

			== Improve code quality ==

			While there are comments in the code, they comment on the trivial things and miss the non-trivial things. There's no need to explain that malloc allocates memory, but it would make a lot of sense if the author of the code explained why R[m] has to be non-zero in order to... what? Also, in my humble opinion, the code will benefit a lot from:

			# Giving proper names to the variables (proper means exactly "the whole word that reflects the purpose of the variable". `R' is not a whole word and reflects nothing; moreso, it is a good practice to name all variables using the same convention with regard to their case, thus `R' near `m' are the opposite of good practice).
			# Writing a short description of what function is doing (for example: ''Given the string TEXT searches for the PATTERN string inside the TEXT and returns... whoops, there's no consensus on what the function returns, the value appears to be somewhat random in corner cases.'')
			# Remove the Captain Obvious comments. It is trivial knowledge that malloc allocates memory, only complex or non-intuitive parts require commenting.
			# Add comments, where it is not trivial. For example, it is not clear why if R(m) is not equal to zero the outer loop should terminate (hint: this is the most important part of the algorithm).
			# Now you will hate me even more, but... spacing and indentation! At least be consistent. How is one time you are writing x=y and the other time x = y?
			[[Special:Contributions/79.176.215.66\|79.176.215.66]] ([[User talk:79.176.215.66\|talk]]) 13:36, 31 October 2012 (UTC)

GregorB: +section title

2012-08-28T17:20:28Z

+section title

← Previous revision		Revision as of 17:20, 28 August 2012
Line 1:		Line 1:
	{{WikiProject Computer science}}		{{WikiProject Computer science}}

			=='It performs best on patterns less than a constant length'==
	Someone wrote 'it performs best on patterns less than a constant length'. Such statements should not be made without adequite analysis. It is true that patterns that are 33 characters long may take twice as long as patterns of length 32, but if the algorithm beats the hell out of all its competitors, or it takes 2 nanoseconds instead of 1, then there's no reason not to use it.		Someone wrote 'it performs best on patterns less than a constant length'. Such statements should not be made without adequite analysis. It is true that patterns that are 33 characters long may take twice as long as patterns of length 32, but if the algorithm beats the hell out of all its competitors, or it takes 2 nanoseconds instead of 1, then there's no reason not to use it.

Ruud Koot: {{WikiProject Computer science}}

2011-12-05T01:00:00Z

← Previous revision		Revision as of 01:00, 5 December 2011
Line 1:		Line 1:
			{{WikiProject Computer science}}

	Someone wrote 'it performs best on patterns less than a constant length'. Such statements should not be made without adequite analysis. It is true that patterns that are 33 characters long may take twice as long as patterns of length 32, but if the algorithm beats the hell out of all its competitors, or it takes 2 nanoseconds instead of 1, then there's no reason not to use it.		Someone wrote 'it performs best on patterns less than a constant length'. Such statements should not be made without adequite analysis. It is true that patterns that are 33 characters long may take twice as long as patterns of length 32, but if the algorithm beats the hell out of all its competitors, or it takes 2 nanoseconds instead of 1, then there's no reason not to use it.

SineBot: Signing comment by Maasha - "/* Canonical name */"

2011-03-30T08:22:48Z

Signing comment by Maasha - "Canonical name: "

← Previous revision		Revision as of 08:22, 30 March 2011
Line 70:		Line 70:
	Google exploits the bitap algorithm many places. Free code here:		Google exploits the bitap algorithm many places. Free code here:

			http://code.google.com/p/google-diff-match-patch/ <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Maasha\|Maasha]] ([[User talk:Maasha\|talk]] • [[Special:Contributions/Maasha\|contribs]]) 08:21, 30 March 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
	http://code.google.com/p/google-diff-match-patch/