String-to-string correction problem

The string-to-string correction problem refers to the minimum number of edit operations necessary to change one string into the other. A single edit operation may be changing a single symbol ("character") of the string into another, deleting or inserting a symbol. The length of the edit sequence provides a measure of the differences (or "distance") between the two strings.

Several algorithms exist to provide an efficient way to determine string distance and specify the minimum amount 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 to store several versions of a single object 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 (like proteins or DNA).