En informática , el problema de corrección de cadena a cadena se refiere a determinar el número mínimo de operaciones de edición necesarias para cambiar una cadena a otra (es decir, calcular la distancia de edición más corta ). Una sola operación de edición puede ser cambiar un solo símbolo de la cadena por otro, eliminar o insertar un símbolo. La longitud de la secuencia de edición proporciona una medida de la distancia entre las dos cadenas.
Existen varios algoritmos para proporcionar una forma eficaz de determinar la distancia de la cadena y especificar el número mínimo de operaciones de transformación necesarias. Dichos algoritmos son particularmente útiles para operaciones de creación delta donde algo se almacena como un conjunto de diferencias relativas a una versión base. Esto permite almacenar varias versiones de un solo objeto de manera mucho más eficiente que almacenarlas por separado. Esto es válido incluso para versiones únicas de varios objetos si no difieren mucho, o algo intermedio. En particular, estos algoritmos de diferencia se utilizan en biología molecular para proporcionar alguna medida de parentesco entre diferentes tipos de organismos en función de las similitudes de sus macromoléculas (como proteínas o ADN ).
Ver también
Referencias
- Wagner, Robert A .; Fischer, Michael J. (1974). "El problema de corrección de cadena a cadena". Revista de la ACM . 21 (1): 168-173. doi : 10.1145 / 321796.321811 .
- Tichy, Walter F. (1984). "El problema de corrección de cuerda a cuerda con movimientos de bloque" . Transacciones ACM en sistemas informáticos . 2 (4): 309–321. doi : 10.1145 / 357401.357404 .