String-to-string correction problem - Revision history

666-Bandera Mouse at 08:42, 16 July 2024

2024-07-16T08:42:42Z

← Previous revision		Revision as of 08:42, 16 July 2024
Line 18:		Line 18:

	[[Category:Problems on strings]]		[[Category:Problems on strings]]
			[[Category:NP-complete problems]]

OAbot: Open access bot: doi updated in citation with #oabot.

2023-08-14T23:30:36Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 23:30, 14 August 2023
Line 1:		Line 1:
	In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first1=Robert A. \|last1=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811\|s2cid=13381535 }}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|s2cid=18892193 \|doi-access=free }}</ref>		In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first1=Robert A. \|last1=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811\|s2cid=13381535 \|doi-access=free }}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|s2cid=18892193 \|doi-access=free }}</ref>

	If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.		If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.

Citation bot: Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1977/2306

2023-08-09T06:14:42Z

Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1977/2306

← Previous revision		Revision as of 06:14, 9 August 2023
Line 10:		Line 10:
	The extended variant of the problem includes a new type of edit operation: swapping any two adjacent symbols, with a cost of W<sub>S</sub>.		The extended variant of the problem includes a new type of edit operation: swapping any two adjacent symbols, with a cost of W<sub>S</sub>.

	This version can be solved in polynomial time under certain restrictions on edit operation costs.<ref name="lowrancewagner" /><ref name="wagner">{{cite ~~journal~~ \|last1=Wagner \|first1=Robert A. \|title=On ~~the~~ ~~complexity~~ of ~~the~~ ~~Extended~~ ~~String-to-String~~ ~~Correction~~ ~~Problem~~ ~~\|journal=~~STOC '75: ~~Proceedings of~~ the ~~Seventh~~ ~~Annual~~ ~~ACM~~ ~~Symposium~~ on ~~Theory~~ ~~of Computing~~ \|date=May 1975 \|pages=218–223 \|doi=10.1145/800116.803771 \|isbn=9781450374194 \|s2cid=18705107 \|url=https://dl.acm.org/doi/10.1145/800116.803771}}</ref>		This version can be solved in polynomial time under certain restrictions on edit operation costs.<ref name="lowrancewagner" /><ref name="wagner">{{cite book \|last1=Wagner \|first1=Robert A. \|title=Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75 \|chapter=On the complexity of the Extended String-to-String Correction Problem \|date=May 1975 \|pages=218–223 \|doi=10.1145/800116.803771 \|isbn=9781450374194 \|s2cid=18705107 \|chapter-url=https://dl.acm.org/doi/10.1145/800116.803771}}</ref>

	Robert A. Wagner (1975) showed that the general problem is [[NP-complete]]. In particular, he proved that when W<sub>I</sub> < W<sub>C</sub> = W<sub>D</sub> = ∞ and 0 < W<sub>S</sub> < ∞ (or equivalently, changing and deletion are not permitted), the problem is NP-complete.<ref name="wagner" />		Robert A. Wagner (1975) showed that the general problem is [[NP-complete]]. In particular, he proved that when W<sub>I</sub> < W<sub>C</sub> = W<sub>D</sub> = ∞ and 0 < W<sub>S</sub> < ∞ (or equivalently, changing and deletion are not permitted), the problem is NP-complete.<ref name="wagner" />

Citation bot: Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 3490/3500

2023-02-12T08:28:09Z

Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 3490/3500

← Previous revision		Revision as of 08:28, 12 February 2023
Line 1:		Line 1:
	In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first1=Robert A. \|last1=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811\|s2cid=13381535 }}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|s2cid=18892193 ~~\|url=https://dl.acm.org/doi/10.1145/321879.321880~~\|doi-access=free }}</ref>		In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first1=Robert A. \|last1=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811\|s2cid=13381535 }}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|s2cid=18892193 \|doi-access=free }}</ref>

	If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.		If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-30T07:25:26Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 07:25, 30 January 2023
Line 1:		Line 1:
	In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first1=Robert A. \|last1=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811\|s2cid=13381535 }}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|s2cid=18892193 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>		In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first1=Robert A. \|last1=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811\|s2cid=13381535 }}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|s2cid=18892193 \|url=https://dl.acm.org/doi/10.1145/321879.321880\|doi-access=free }}</ref>

	If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.		If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.

	Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|s2cid=14034845 \|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.		Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|s2cid=14034845 \|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech \|doi-access=free }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.
	Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).		Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).

Citation bot: Alter: journal. Add: isbn, s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2022-07-26T06:39:47Z

Alter: journal. Add: isbn, s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 06:39, 26 July 2022
Line 1:		Line 1:
	In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|~~first~~=Robert A. \|~~last~~=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>		In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first1=Robert A. \|last1=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811\|s2cid=13381535 }}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|s2cid=18892193 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>

	If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.		If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.

	Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.		Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|s2cid=14034845 \|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.
	Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).		Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).

Line 10:		Line 10:
	The extended variant of the problem includes a new type of edit operation: swapping any two adjacent symbols, with a cost of W<sub>S</sub>.		The extended variant of the problem includes a new type of edit operation: swapping any two adjacent symbols, with a cost of W<sub>S</sub>.

	This version can be solved in polynomial time under certain restrictions on edit operation costs.<ref name="lowrancewagner" /><ref name="wagner">{{cite journal \|last1=Wagner \|first1=Robert A. \|title=On the complexity of the Extended String-to-String Correction Problem \|journal=STOC '75: Proceedings of the ~~seventh~~ ~~annual~~ ACM ~~symposium~~ on Theory of ~~computing~~ \|date=May 1975 \|pages=218–223 \|doi=10.1145/800116.803771 \|url=https://dl.acm.org/doi/10.1145/800116.803771}}</ref>		This version can be solved in polynomial time under certain restrictions on edit operation costs.<ref name="lowrancewagner" /><ref name="wagner">{{cite journal \|last1=Wagner \|first1=Robert A. \|title=On the complexity of the Extended String-to-String Correction Problem \|journal=STOC '75: Proceedings of the Seventh Annual ACM Symposium on Theory of Computing \|date=May 1975 \|pages=218–223 \|doi=10.1145/800116.803771 \|isbn=9781450374194 \|s2cid=18705107 \|url=https://dl.acm.org/doi/10.1145/800116.803771}}</ref>

	Robert A. Wagner (1975) showed that the general problem is [[NP-complete]]. In particular, he proved that when W<sub>I</sub> < W<sub>C</sub> = W<sub>D</sub> = ∞ and 0 < W<sub>S</sub> < ∞ (or equivalently, changing and deletion are not permitted), the problem is NP-complete.<ref name="wagner" />		Robert A. Wagner (1975) showed that the general problem is [[NP-complete]]. In particular, he proved that when W<sub>I</sub> < W<sub>C</sub> = W<sub>D</sub> = ∞ and 0 < W<sub>S</sub> < ∞ (or equivalently, changing and deletion are not permitted), the problem is NP-complete.<ref name="wagner" />

LightbulbMEOW: Alternate phrasing

2022-04-01T04:48:59Z

Alternate phrasing

← Previous revision		Revision as of 04:48, 1 April 2022
Line 1:		Line 1:
	In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>		In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>

	If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of ~~the~~ two strings.		If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of two strings.

	Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.		Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.
Line 12:		Line 12:
	This version can be solved in polynomial time under certain restrictions on edit operation costs.<ref name="lowrancewagner" /><ref name="wagner">{{cite journal \|last1=Wagner \|first1=Robert A. \|title=On the complexity of the Extended String-to-String Correction Problem \|journal=STOC '75: Proceedings of the seventh annual ACM symposium on Theory of computing \|date=May 1975 \|pages=218–223 \|doi=10.1145/800116.803771 \|url=https://dl.acm.org/doi/10.1145/800116.803771}}</ref>		This version can be solved in polynomial time under certain restrictions on edit operation costs.<ref name="lowrancewagner" /><ref name="wagner">{{cite journal \|last1=Wagner \|first1=Robert A. \|title=On the complexity of the Extended String-to-String Correction Problem \|journal=STOC '75: Proceedings of the seventh annual ACM symposium on Theory of computing \|date=May 1975 \|pages=218–223 \|doi=10.1145/800116.803771 \|url=https://dl.acm.org/doi/10.1145/800116.803771}}</ref>

	Robert A. Wagner (1975) showed if W<sub>I</sub> < W<sub>C</sub> = W<sub>D</sub> = ∞ and 0 < W<sub>S</sub> < ∞, ~~then~~ the problem is [[NP-complete]].<ref name="wagner" />		Robert A. Wagner (1975) showed that the general problem is [[NP-complete]]. In particular, he proved that when W<sub>I</sub> < W<sub>C</sub> = W<sub>D</sub> = ∞ and 0 < W<sub>S</sub> < ∞ (or equivalently, changing and deletion are not permitted), the problem is NP-complete.<ref name="wagner" />

	== References ==		== References ==

LightbulbMEOW: New section: Extension

2022-04-01T04:36:23Z

New section: Extension

← Previous revision		Revision as of 04:36, 1 April 2022
Line 1:		Line 1:
	In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>		In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a new symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>

	If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of the two strings.		If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of the two strings.
Line 5:		Line 5:
	Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.		Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.
	Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).		Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).

			== Extension ==

			The extended variant of the problem includes a new type of edit operation: swapping any two adjacent symbols, with a cost of W<sub>S</sub>.

			This version can be solved in polynomial time under certain restrictions on edit operation costs.<ref name="lowrancewagner" /><ref name="wagner">{{cite journal \|last1=Wagner \|first1=Robert A. \|title=On the complexity of the Extended String-to-String Correction Problem \|journal=STOC '75: Proceedings of the seventh annual ACM symposium on Theory of computing \|date=May 1975 \|pages=218–223 \|doi=10.1145/800116.803771 \|url=https://dl.acm.org/doi/10.1145/800116.803771}}</ref>

			Robert A. Wagner (1975) showed if W<sub>I</sub> < W<sub>C</sub> = W<sub>D</sub> = ∞ and 0 < W<sub>S</sub> < ∞, then the problem is [[NP-complete]].<ref name="wagner" />

	== References ==		== References ==

LightbulbMEOW: Add inline citations, and correct the definition of the problem

2022-04-01T03:47:45Z

Add inline citations, and correct the definition of the problem

← Previous revision		Revision as of 03:47, 1 April 2022
Line 1:		Line 1:
			In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum cost sequence of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). Each type of edit operation has its own cost value.<ref name="wagnerfischer">{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}</ref> A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another (cost W<sub>C</sub>), deleting a symbol (cost W<sub>D</sub>), or inserting a symbol (cost W<sub>I</sub>).<ref name="lowrancewagner">{{cite journal \|last1=Lowrance \|first1=Roy \|last2=Wagner \|first2=Robert A. \|title=An Extension of the String-to-String Correction Problem \|journal=Journal of the ACM \|date=April 1975 \|volume=22 \|issue=2 \|pages=177–183 \|doi=10.1145/321879.321880 \|url=https://dl.acm.org/doi/10.1145/321879.321880}}</ref>
	{{No footnotes\|date=July 2010}}
	In [[computer science]], the '''string-to-string correction problem''' refers to determining the minimum number of edit operations necessary to change one [[String (computer science)\|string]] into another (i.e., computing the shortest [[edit distance]]). A single edit operation may be changing a single [[Character (computing)\|symbol]] of the string into another, deleting, or inserting a symbol. The length of the edit sequence provides a measure of the [[Hamming distance\|distance]] between the two strings.

			If all edit operations have the same unit costs (W<sub>C</sub> = W<sub>D</sub> = W<sub>I</sub> = 1) the problem is the same as computing the [[Levenshtein distance]] of the two strings.
⚫	Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required. Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.
⚫	Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).

		⚫	Several [[algorithm]]s exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required.<ref>[[Edit distance#Computation]]</ref><ref>{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}</ref> Such algorithms are particularly useful for [[Delta encoding\|delta]] creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between.
	== See also ==
		⚫	Notably, such difference algorithms are used in [[molecular biology]] to provide some measure of kinship between different kinds of organisms based on the similarities of their [[macromolecule]]s (such as [[protein]]s or [[DNA]]).
	* [[Delta encoding]]
	* [[Levenshtein distance]]
	* [[Edit distance]]

	== References ==		== References ==
	{{~~refbegin~~}}		{{reflist}}
	*{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}
	*{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}
	{{refend}}

	[[Category:Problems on strings]]		[[Category:Problems on strings]]

QueerEcofeminist: Added free to read link in citations with OAbot #oabot

2018-09-02T06:30:10Z

Added free to read link in citations with OAbot #oabot

← Previous revision		Revision as of 06:30, 2 September 2018
Line 13:		Line 13:
	{{refbegin}}		{{refbegin}}
	*{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}		*{{cite journal \|first=Robert A. \|last=Wagner \|first2=Michael J. \|last2=Fischer \|author2-link=Michael J. Fischer \|title=The String-to-String Correction Problem \|journal=Journal of the ACM \|volume=21 \|issue=1 \|year=1974 \|pages=168–173 \|doi= 10.1145/321796.321811}}
	*{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404}}		*{{cite journal \|first=Walter F. \|last=Tichy \|title=The string-to-string correction problem with block moves \|journal=ACM Transactions on Computer Systems \|volume=2 \|issue=4 \|year=1984 \|pages=309–321 \|doi= 10.1145/357401.357404\|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech }}
	{{refend}}		{{refend}}