¿Diferencia entre Jaro-Winkler y la distancia de Levenshtein? [cerrado]

Tengo un caso de uso en el que necesito hacer una coincidencia aproximada de millones de registros de varios archivos. Identifiqué dos algoritmos para eso: distancia de edición de Jaro-Winkler y Levenshtein .

Cuando comencé a explorar ambos, no pude entender cuál es la diferencia exacta entre los dos. Parece que Levenshtein da el número de ediciones entre dos cadenas y Jaro-Winkler proporciona una puntuación normalizada entre 0,0 y 1,0. No entendí el algoritmo.

Como necesito usar cualquiera de los algoritmos, necesito saber cuáles son las diferencias fundamentales entre estos dos algoritmos.

En segundo lugar, me gustaría conocer la diferencia de rendimiento entre estos dos algoritmos.

Levenshtein cuenta el número de ediciones (inserciones, eliminaciones o sustituciones) necesarias para convertir una cadena en otra. Damerau-Levenshtein es una versión modificada que también considera las transposiciones como ediciones únicas. Aunque la salida es el número entero de ediciones, esto se puede normalizar para dar un valor de similitud mediante la fórmula

1 - (edit distance / length of the larger of the two strings)

El algoritmo de Jaro es una medida de caracteres en común, que no tiene más de la mitad de la longitud de la cadena más larga en distancia, teniendo en cuenta las transposiciones. Winkler modificó este algoritmo para respaldar la idea de que las diferencias cerca del comienzo de la cadena son más significativas que las diferencias cerca del final de la cadena. Jaro y Jaro-Winkler son adecuados para comparar cadenas más pequeñas como palabras y nombres.

Decidir cuál usar no es solo una cuestión de rendimiento. Es importante elegir un método que se adapte a la naturaleza de las cadenas que está comparando. Sin embargo, en general, los dos algoritmos que mencionó pueden ser costosos, porque cada cadena debe compararse con todas las demás cadenas, y con millones de cadenas en su conjunto de datos, es una gran cantidad de comparaciones. Eso es mucho más caro que algo como calcular una codificación fonética para cada cadena y luego simplemente agrupar cadenas que comparten codificaciones idénticas.

Existe una gran cantidad de información detallada sobre estos algoritmos y otros algoritmos de coincidencia de cadenas difusas en Internet. Este te dará un comienzo:

Una comparación de la coincidencia de nombres personales: técnicas y cuestiones prácticas

Según ese documento, la velocidad de los cuatro algoritmos de Jaro y Levenshtein que he mencionado son de la más rápida a la más lenta:

• Jaro
• Jaro-Winkler
• Levenshtein
• Damerau-Levenshtein

y el más lento tarda de 2 a 3 veces más que el más rápido. Por supuesto, estos tiempos dependen de la longitud de las cadenas y las implementaciones, y hay formas de optimizar estos algoritmos que pueden no haberse utilizado.