performance - español - Diferencia entre Jaro-Winkler y Levenshtein distancia?

jaro winkler español

Question

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

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 da un puntaje coincidente entre 0.0 a 1.0. No entendí el algoritmo. Como necesito usar cualquiera de los dos algoritmos, necesito saber las diferencias exactas con respecto al rendimiento del algoritmo.

Answer 1

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 con 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 es más que la mitad de la longitud de la cuerda más larga en la distancia, teniendo en cuenta las transposiciones. Winkler modificó este algoritmo para respaldar la idea de que las diferencias cerca del inicio 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, ya que cada cadena debe compararse con todas las demás, y con millones de cadenas en su conjunto de datos, eso es un número tremendo de comparaciones. Eso es mucho más costoso que algo así como calcular una codificación fonética para cada cadena, y luego simplemente agrupar cadenas compartiendo 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 problemas prácticos

Según ese artículo, 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

con el más lento de 2 a 3 veces más rápido 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 no se han utilizado.