String-to-string correction problem (original) (raw)
In computer science, the string-to-string correction problem refers to determining the minimum cost sequence of edit operations necessary to change one string into another (i.e., computing the shortest edit distance). Each type of edit operation has its own cost value. A single edit operation may be changing a single symbol of the string into another (cost WC), deleting a symbol (cost WD), or inserting a new symbol (cost WI). If all edit operations have the same unit costs (WC = WD = WI = 1) the problem is the same as computing the Levenshtein distance of two strings.
| Property | Value |
|---|---|
| dbo:abstract | In computer science, the string-to-string correction problem refers to determining the minimum cost sequence of edit operations necessary to change one string into another (i.e., computing the shortest edit distance). Each type of edit operation has its own cost value. A single edit operation may be changing a single symbol of the string into another (cost WC), deleting a symbol (cost WD), or inserting a new symbol (cost WI). If all edit operations have the same unit costs (WC = WD = WI = 1) the problem is the same as computing the Levenshtein distance of two strings. Several algorithms 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 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 macromolecules (such as proteins or DNA). (en) |
| dbo:wikiPageID | 1899780 (xsd:integer) |
| dbo:wikiPageLength | 3561 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1100495856 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Character_(computing) dbr:DNA dbr:Levenshtein_distance dbr:NP-complete dbr:Computer_science dbr:Delta_encoding dbr:Macromolecule dbr:String_(computer_science) dbc:Problems_on_strings dbr:Protein dbr:Edit_distance dbr:Molecular_biology |
| dbp:wikiPageUsesTemplate | dbt:Reflist |
| dcterms:subject | dbc:Problems_on_strings |
| rdf:type | yago:WikicatStringSimilarityMeasures yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Attribute100024264 yago:Choice100161243 yago:Condition113920835 yago:Decision100162632 yago:Difficulty114408086 yago:Event100029378 yago:Maneuver100168237 yago:Measure100174412 yago:Move100165942 yago:Problem114410605 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:State100024720 yago:WikicatProblemsOnStrings |
| rdfs:comment | In computer science, the string-to-string correction problem refers to determining the minimum cost sequence of edit operations necessary to change one string into another (i.e., computing the shortest edit distance). Each type of edit operation has its own cost value. A single edit operation may be changing a single symbol of the string into another (cost WC), deleting a symbol (cost WD), or inserting a new symbol (cost WI). If all edit operations have the same unit costs (WC = WD = WI = 1) the problem is the same as computing the Levenshtein distance of two strings. (en) |
| rdfs:label | String-to-string correction problem (en) |
| owl:sameAs | freebase:String-to-string correction problem wikidata:String-to-string correction problem https://global.dbpedia.org/id/4w5ej yago-res:String-to-string correction problem |
| prov:wasDerivedFrom | wikipedia-en:String-to-string_correction_problem?oldid=1100495856&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:String-to-string_correction_problem |
| is dbo:wikiPageWikiLink of | dbr:Levenshtein_distance dbr:Gosling_Emacs dbr:Delta_encoding dbr:Walter_F._Tichy dbr:List_of_NP-complete_problems dbr:Edit_distance |
| is foaf:primaryTopic of | wikipedia-en:String-to-string_correction_problem |