String-to-string correction problem

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the string-to-string correction problem refers to determining the minimum cost sequence of edit operations necessary to change one <a href="/facts/String_(computer_science)/4ChJu5WS">string</a> into another (i.e., computing the shortest <a href="/facts/Edit_distance/P8qVBmAD">edit distance</a>). Each type of edit operation has its own cost value. A single edit operation may be changing a single <a href="/facts/Character_(computing)/X2zKLFFB">symbol</a> 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 <a href="/facts/Levenshtein_distance/F0otyNSl">Levenshtein distance</a> of two strings.
Several <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> 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 <a href="/facts/Delta_encoding/2NQlyAUc">delta</a> 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 <a href="/facts/Molecular_biology/YgqU35ub">molecular biology</a> to provide some measure of kinship between different kinds of organisms based on the similarities of their <a href="/facts/Macromolecule/039ULSLg">macromolecules</a> (such as <a href="/facts/Protein/Jxmagu3E">proteins</a> or <a href="/facts/DNA/nB89Iauz">DNA</a>).

String-to-string correction problem open-in-new

String-to-string correction problem