Pregunta Encontrar cuán similares son dos cadenas


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?


32
2018-02-23 12:18


origen


Respuestas:


Ok, entonces los algoritmos estándar son:

1) Hamming distancia  Solo es bueno para cuerdas 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 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) Generalizado Levenstein / (distancia Damerau-Levenshtein) Esta distancia también tiene en cuenta 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 de bitap algoritmo (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 vecinos cercanos basada en un árbol k-d.


33
2018-02-23 13:00



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

3
2018-02-23 12:25



el Distancia Damerau-Levenshtein es similar a la distancia de 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.


3
2018-02-23 12:55



Estás buscando el Distancia Levenshtein


2
2018-02-23 12:23