Problema de corrección de cadena a cadena

En informática , el problema de corrección de cadena a cadena se refiere a determinar la secuencia de operaciones de edición de costo mínimo necesarias para cambiar una cadena por otra (es decir, calcular la distancia de edición más corta ). Cada tipo de operación de edición tiene su propio valor de costo. ^{[ 1 ]} Una sola operación de edición puede ser cambiar un solo símbolo de la cadena por otro (costo W _C ), eliminar un símbolo (costo W _D ) o insertar un nuevo símbolo (costo W _I ). ^{[ 2 ]}

Si todas las operaciones de edición tienen los mismos costos unitarios (W _C = W _D = W _I = 1), el problema es el mismo que calcular la distancia de Levenshtein de dos cadenas.

Existen varios algoritmos para determinar de manera eficiente la distancia entre cadenas y especificar el número mínimo de operaciones de transformación necesarias. ^{[ 3 ] [ 4 ]} Estos algoritmos son particularmente útiles para operaciones de creación de deltas , donde algo se almacena como un conjunto de diferencias con respecto a una versión base. Esto permite almacenar varias versiones de un mismo objeto de forma mucho más eficiente que si se almacenaran por separado. Esto se aplica incluso a versiones únicas de varios objetos si no difieren mucho, o a cualquier caso intermedio. Cabe destacar que estos algoritmos de diferencia se utilizan en biología molecular para proporcionar una medida de parentesco entre diferentes tipos de organismos basándose en las similitudes de sus macromoléculas (como proteínas o ADN ).

La variante extendida del problema incluye un nuevo tipo de operación de edición: intercambiar dos símbolos adyacentes cualesquiera, con un coste de W _S .

Esta versión se puede resolver en tiempo polinomial bajo ciertas restricciones en los costos de las operaciones de edición. ^{[ 2 ] [ 5 ]}

Robert A. Wagner (1975) demostró que el problema general es NP-completo . En particular, probó que cuando W _I < W _C = W _D = ∞ y 0 < W _S < ∞ (o equivalentemente, no se permiten cambios ni eliminaciones), el problema es NP-completo. ^{[ 5 ]}