En primer lugar, la distancia de Levenshtein se define como el número mínimo de ediciones requeridas para transformar la cadena A en la cadena B, donde una edición es la inserción o eliminación de un solo carácter, o el reemplazo de un carácter con otro carácter. Entonces, es en gran medida la "diferencia entre dos cadenas", para una cierta definición de distancia. =)
Parece que está buscando una función de distancia F (A, B) que proporcione una distancia entre las cadenas A y B y un umbral N donde las cadenas con una distancia menor que N entre sí son candidatas para errores tipográficos. Además de la distancia de Levenshtein, también puede considerar Needleman–Wunsch . Es básicamente lo mismo, pero le permite proporcionar una función para determinar qué tan cerca está un personaje dado de otro personaje. Podría usar ese algoritmo con un conjunto de pesos que reflejen las posiciones de las teclas en un teclado QWERTY para hacer un buen trabajo al encontrar errores tipográficos. Sin embargo, esto tendría problemas con los teclados internacionales.
Si tiene k cadenas y desea encontrar posibles errores tipográficos, la cantidad de comparaciones que necesita hacer es O (k ^ 2). Además, cada comparación es O(len(A)*len(B)). Entonces, si tiene un millón de cadenas, se encontrará en problemas si hace las cosas de manera ingenua. Aquí hay algunas sugerencias sobre cómo acelerar las cosas:
- Disculpas si esto es obvio, pero la distancia de Levenshtein es simétrica, así que asegúrate de no estar calculando F(A, B) y F(B, A).
- abs(len(A) - len(B)) es un límite inferior en la distancia entre las cadenas A y B. Por lo tanto, puede omitir la verificación de cadenas cuyas longitudes son demasiado diferentes.
Un problema con el que te puedes encontrar es que "1st St." tiene una distancia bastante alta de "First Street", aunque probablemente desee considerar que son idénticos. La forma más fácil de manejar esto es probablemente transformar las cadenas en una forma canónica antes de hacer las comparaciones. Por lo tanto, puede hacer que todas las cadenas estén en minúsculas, usar un diccionario que asigne "primero" a "primero", etc. Ese diccionario puede ser bastante grande, pero no conozco una mejor manera de lidiar con estos problemas.
Dado que etiquetó esta pregunta con php, supongo que desea usar php para esto. PHP tiene una función levenshtein() incorporada, pero ambas cadenas deben tener 255 caracteres o menos. Si eso no es suficiente, tendrás que hacer el tuyo propio. Alternativamente, investiga usando difflib de Python.
