Haga coincidir dos cadenas pero permita un cierto grado de error

¿Cómo puedo hacer coincidir dos cadenas, pero al mismo tiempo permitir que X número de caracteres sean incorrectos en la coincidencia? El número de errores debe ser una variable controlable.

Si bien el número X de caracteres no puede coincidir en la cadena, debe haber un límite en cuanto a cuántos se ejecutan en una secuencia. Dadas dos cadenas, podría permitir que 5 caracteres sean diferentes, pero no más de 2 seguidos.

Estoy buscando un algoritmo recomendado para comparar estas dos cadenas, o tal vez ya existe una solución conocida para esto.

Un punto de inicio de búsqueda de cadena aproximado es el de la distancia de Levenshtein . Este algoritmo cuenta el número de ediciones de un solo carácter (insertar, eliminar y sustituir) para cambiar una palabra por otra.

Un ejemplo de esto es kitten-> sittingque tiene una distancia de edición de tres

1. k itten -> s itten (sustituya 's' por 'k')
2. sitt e n -> sitt i n (sustituya 'i' por 'e')
3. sittin -> sittin g (agregue 'g' al final)

Hay variaciones en este algoritmo, especialmente la distancia Damerau – Levenshtein que permite la transposición de dos caracteres adyacentes ('hte' a 'the' tiene una distancia DL de 1 y una distancia Levenshtein de 2) y, por lo tanto, a menudo es más apropiado para corrección ortográfica. Existen otras variaciones para aplicaciones donde las brechas son importantes (cadenas de ADN).

La distancia de Levenshtein es bien conocida y no es demasiado difícil de encontrar (una vez tuve que buscar una implementación como función en Oracle : fue mucho más rápido que extraer todos los datos y luego ejecutar el lado del código de consulta). Rosettacode tiene una multitud (54) de implementaciones de la distancia de Levenshtein (tenga en cuenta que algunos idiomas tienen esto como parte de la biblioteca de cadenas en algún lugar; si está utilizando Java, mire el lenguaje de apache commons ). Wikibooks tiene 31 implementaciones y una mirada superficial a las dos no muestra el mismo código para el mismo idioma.

La forma en que esto funciona es que construye una matriz que corresponde a la relación entre las dos cadenas:

 .kitten
.0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443

La .fila y la columna representan que puede llegar a la cadena de destino 'simplemente' insertando cada letra de una cadena vacía. Este no es el caso ideal, pero está ahí para sembrar el algoritmo.

Si el valor es el mismo que el punto ('i' == 'i'), el valor es el mismo que el valor en diagonal hacia la izquierda. Si los dos puntos son diferentes ('s'! = 'K') el valor es el mínimo de:

• diagonal hacia arriba y hacia la izquierda + 1 (una sustitución)
• directamente encima de + 1 (una inserción)
• directamente a la izquierda + 1 (una eliminación)

El valor de retorno de la distancia de edición es el valor en la esquina inferior derecha de la matriz.

Si sigue desde la esquina inferior derecha hasta la esquina superior izquierda con el mínimo, puede ver las ediciones realizadas:

 .kitten
.0.   .
s.1   .
i  1  .
t   1 .
t    1.
i.....2
n      2
g......3

Tenga en cuenta que este es el enfoque más intensivo en memoria. Se puede reducir en el alcance de la memoria al no construir la matriz completa: todo lo que le importa al algoritmo es un subconjunto de datos y se puede reducir de un N*Mespacio a otro 2*max(N,M)simplemente almacenando la fila anterior (y lo que se ha calculado en el actual fila). Code Project muestra cómo se puede hacer esto (con el código C # para descargar).