Distancia Jaro-Winkler

Medida de distancia de cuerda

En informática y estadística , la similitud de Jaro-Winkler es una métrica de cadena que mide la distancia de edición entre dos secuencias. Es una variante de la métrica de distancia de Jaro ^[1] (1989, Matthew A. Jaro) propuesta en 1990 por William E. Winkler . ^[2]

La distancia Jaro-Winkler utiliza una escala de prefijo que otorga calificaciones más favorables a las cadenas que coinciden desde el principio para una longitud de prefijo establecida . ${\displaystyle p}$ ${\displaystyle \ell }$

Cuanto mayor sea la distancia de Jaro-Winkler para dos cadenas, menos similares serán. La puntuación se normaliza de modo que 0 significa una coincidencia exacta y 1 significa que no hay similitud. El artículo original definió la métrica en términos de similitud, por lo que la distancia se define como la inversión de ese valor (distancia = 1 − similitud).

Aunque a menudo se hace referencia a ella como una métrica de distancia , la distancia de Jaro-Winkler no es una métrica en el sentido matemático de ese término porque no obedece a la desigualdad triangular .

Definición

Similitud con Jaro

La similitud de Jaro de dos cadenas dadas es ${\displaystyle sim_{j}}$ ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$

${\displaystyle sim_{j}=\left\{{\begin{array}{l l}0&{\text{if }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)&{\text{otherwise}}\end{array}}\right.}$

Dónde:

• ${\displaystyle |s_{i}|}$es la longitud de la cadena ; ${\displaystyle s_{i}}$
• ${\displaystyle m}$es el número de caracteres coincidentes (ver más abajo);
• ${\displaystyle t}$es el número de transposiciones (ver más abajo).

La puntuación de similitud de Jaro es 0 si las cadenas no coinciden en absoluto y 1 si coinciden exactamente. En el primer paso, cada carácter de se compara con todos sus caracteres coincidentes en . Dos caracteres de y respectivamente, se consideran coincidentes solo si son iguales y no están separados por más de caracteres. Por ejemplo, las siguientes dos cadenas de nueve caracteres, FAREMVIEL y FARMVILLE, tienen 8 caracteres coincidentes. 'F', 'A' y 'R' están en la misma posición en ambas cadenas. Además, 'M', 'V', 'I', 'E' y 'L' están a tres (resultado de ) caracteres de distancia. ^[3] Si no se encuentran caracteres coincidentes, las cadenas no son similares y el algoritmo finaliza devolviendo una puntuación de similitud de Jaro de 0. ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$ ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$ ${\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1}$ ${\displaystyle \lfloor {\tfrac {\max(9,9)}{2}}\rfloor -1}$

Si se encuentran caracteres coincidentes que no sean cero, el siguiente paso es encontrar el número de transposiciones. La transposición es el número de caracteres coincidentes que no están en el orden correcto dividido por dos. En el ejemplo anterior entre FAREMVIEL y FARMVILLE, "E" y "L" son los caracteres coincidentes que no están en el orden correcto. Por lo tanto, el número de transposiciones es uno.

Finalmente, introduciendo el número de caracteres coincidentes y el número de transposiciones, se puede calcular la similitud Jaro de FAREMVIEL y FARMVILLE. ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle {\frac {1}{3}}\left({\frac {8}{9}}+{\frac {8}{9}}+{\frac {8-1}{8}}\right)=0.88}$

Similitud de Jaro-Winkler

La similitud de Jaro-Winkler utiliza una escala de prefijos que otorga calificaciones más favorables a las cadenas que coinciden desde el principio para una longitud de prefijo establecida . Dadas dos cadenas y , su similitud de Jaro-Winkler es: ${\displaystyle p}$ ${\displaystyle \ell }$ ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$ ${\displaystyle sim_{w}}$

${\displaystyle sim_{w}=sim_{j}+\ell p(1-sim_{j}),}$

dónde:

• ${\displaystyle sim_{j}}$¿Cuál es la similitud de Jaro para cadenas y ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$
• ${\displaystyle \ell }$es la longitud del prefijo común al comienzo de la cadena hasta un máximo de 4 caracteres
• ${\displaystyle p}$es un factor de escala constante que determina cuánto se ajusta hacia arriba la puntuación por tener prefijos comunes. no debe superar 0,25 (es decir, 1/4, siendo 4 la longitud máxima del prefijo que se considera), de lo contrario, la similitud podría llegar a ser mayor que 1. El valor estándar para esta constante en el trabajo de Winkler es ${\displaystyle p}$ ${\displaystyle p=0.1}$

La distancia Jaro-Winkler se define como . ${\displaystyle d_{w}}$ ${\displaystyle d_{w}=1-sim_{w}}$

Aunque a menudo se hace referencia a ella como una métrica de distancia , la distancia de Jaro-Winkler no es una métrica en el sentido matemático de ese término porque no obedece la desigualdad triangular . ^[4] La distancia de Jaro-Winkler tampoco satisface el axioma de identidad . ${\displaystyle d(x,y)=0\leftrightarrow x=y}$

Relación con otras métricas de distancia de edición

Existen otras medidas populares de distancia de edición , que se calculan utilizando un conjunto diferente de operaciones de edición permitidas. Por ejemplo,

• La distancia de Levenshtein permite la eliminación, inserción y sustitución;
• La distancia Damerau-Levenshtein permite la inserción, eliminación, sustitución y transposición de dos caracteres adyacentes;
• La distancia de subsecuencia común más larga (LCS) solo permite inserción y eliminación, no sustitución;
• La distancia de Hamming solo permite sustitución, por lo tanto, solo se aplica a cadenas de la misma longitud.

La distancia de edición suele definirse como una métrica parametrizable calculada con un conjunto específico de operaciones de edición permitidas, y a cada operación se le asigna un costo (posiblemente infinito). Esto se generaliza aún más mediante algoritmos de alineamiento de secuencias de ADN como el algoritmo Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplica.

Véase también

• Vinculación de registros
• Censo

Notas al pie

1. Jaro, Matthew A. (1 de junio de 1989). "Avances en la metodología de vinculación de registros aplicada a la comparación del censo de 1985 de Tampa, Florida". Revista de la Asociación Estadounidense de Estadística . págs. 414–420. doi :10.1080/01621459.1989.10478785.
2. Winkler, William E. (1990). "Métricas de comparación de cadenas y reglas de decisión mejoradas en el modelo Fellegi-Sunter de vinculación de registros".
3. "¿Qué es la similitud de Jaro-Winkler?". www.baseclass.io . Consultado el 26 de julio de 2012 .
4. "Jaro-Winkler « Invitando a la Epifanía ». RichardMinerich.com . Consultado el 12 de junio de 2017 .

Referencias

• Cohen, WW; Ravikumar, P.; Fienberg, SE (2003). "Una comparación de métricas de distancia de cadenas para tareas de coincidencia de nombres" (PDF) . Taller de KDD sobre limpieza de datos y consolidación de objetos . 3 : 73–8.
• Jaro, MA (1989). "Avances en la metodología de vinculación de registros aplicada al censo de Tampa, Florida, de 1985". Revista de la Asociación Estadounidense de Estadística . 84 (406): 414–20. doi :10.1080/01621459.1989.10478785.
• Jaro, MA (1995). "Enlace probabilístico de grandes archivos de datos de salud pública". Estadísticas en Medicina . 14 (5–7): 491–8. doi :10.1002/sim.4780140510. PMID  7792443.
• Winkler, WE (1990). "Métricas de comparación de cadenas y reglas de decisión mejoradas en el modelo Fellegi-Sunter de vinculación de registros" (PDF) . Actas de la Sección de métodos de investigación de encuestas . Asociación Estadounidense de Estadística: 354–359.

• Winkler, WE (2006). "Descripción general de la vinculación de registros y direcciones de investigación actuales" (PDF) . Serie de informes de investigación, RRS .

Enlaces externos

• strcmp.c - Implementación original en C del autor del algoritmo
• Módulo nltk.metrics.distance: implementación de Python en Natural Language Toolkit