subcadena moore kmp definicion boyer algoritmos algorithm string-matching

algorithm - moore - Encontrar cuán similares son dos cadenas



kmp algorithm python (4)

Estoy buscando un algoritmo que tome 2 cadenas y me devuelva un "factor de similitud".

Básicamente, tendré una entrada que puede estar mal escrita, tener letras transpuestas, etc., y tengo que encontrar la (s) pareja (s) más cercana (s) en una lista de valores posibles que tengo.

Esto no es para buscar en una base de datos. Tendré una lista en memoria de aproximadamente 500 cadenas para hacer coincidir, todas menores de 30 caracteres, por lo que puede ser relativamente lenta.

Sé que esto existe, lo he visto antes, pero no recuerdo su nombre.

Editar: Gracias por señalar a Levenshtein y Hamming. Ahora, ¿cuál debo implementar? Básicamente miden cosas diferentes, que pueden usarse para lo que quiero, pero no estoy seguro de cuál es más apropiado.

He leído sobre los algoritmos, Hamming parece obviamente más rápido. Ya que ninguno detectará la transposición de dos caracteres (es decir, Jordan y Jodran), lo cual creo que será un error común, ¿cuál será más preciso para lo que quiero? ¿Puede alguien decirme un poco acerca de las concesiones?

Ok, entonces los algoritmos estándar son:

1) Distancia de Hamming Solo es bueno para cadenas de la misma longitud, pero muy eficiente. Básicamente, simplemente cuenta el número de caracteres distintos. No es útil para la búsqueda difusa de texto en lenguaje natural.

2) Distancia de Levenstein . La distancia de Levenstein mide la distancia en términos del número de "operaciones" requeridas para transformar una cadena en otra. Estas operaciones incluyen inserción, eliminación y substición. El enfoque estándar para calcular la distancia de Levenstein es usar programación dinámica.

3) Levenstein / distancia de Damerau-Levenshtein generalizada Esta distancia también toma en consideración las transposiciones de caracteres en una palabra, y es probablemente la distancia de edición más adecuada para la coincidencia difusa del texto ingresado manualmente. El algoritmo para calcular la distancia es un poco más complicado que la distancia de Levenstein (la detección de transposiciones no es fácil). Las implementaciones más comunes son una modificación del algoritmo bitap (como grep).

En general, es probable que desee considerar una implementación de la tercera opción implementada en algún tipo de búsqueda de vecino más cercano basado en un árbol kd.

la distancia Damerau-Levenshtein es similar a la distancia Levenshtein, pero también incluye la transposición de dos caracteres. la página wikipedia (vinculada) incluye pseudocódigo que debería ser bastante trivial para implementar.

  • Distancia Levenstein
  • Hamming distancia
  • soundex
  • metafonía