Encontrar cómo dos cadenas similares son

Question

Estoy buscando un algoritmo que toma 2 cadenas y me devolverá un "factor de similitud".

Básicamente, tendré una entrada que puede estar mal escrita, tener letras transpuestas, etc., y tengo que encontrar la (s) coincidencia (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 Levenshtein and 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 algo sobre las concesiones?

Answer 1

Ok, por lo que los algoritmos estándar son:

1) Hamming distance Sólo bueno para las 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) . 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) Generalized Levenstein/(Damerau–Levenshtein distance) 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 concordancia 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 implementado en una especie de búsqueda del vecino más próximo sobre la base de un árbol kd

Answer 2

Usted está buscando el Levenshtein distance

Answer 3

• Levenstein distancia
• distancia de Hamming
• soundex
• metaphone

Answer 4

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