Distancia Jaro-Winkler

Medida de distancia de cuerda

En informática y estadística , la similitud Jaro-Winkler es una métrica de cadena que mide una 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 es la distancia Jaro-Winkler para dos cuerdas, menos similares son las cuerdas. La puntuación se normaliza de modo que 0 significa una coincidencia exacta y 1 significa que no hay similitud. En realidad, 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 la denomina métrica de distancia , la distancia de Jaro-Winkler no es una métrica en el sentido matemático del término porque no obedece a la desigualdad del triángulo .

Definición

Similitud con Jaro

La similitud Jaro de dos cadenas dadas y 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 cuerda ; ${\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 cuerdas. Además, 'M', 'V', 'I', 'E' y 'L' están a tres (resultado de ) caracteres de distancia. ^[3] Si no se encuentran caracteres coincidentes, entonces las cadenas no son similares y el algoritmo termina 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 distintos de 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 caracteres coincidentes que no están en el orden correcto. Entonces el número de transposición es uno.

Finalmente, al ingresar 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 entre Jaro y Winkler

La similitud 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 . Dadas dos cadenas y , su similitud 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}}$es la similitud de Jaro para cuerdas y ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$
• ${\displaystyle \ell }$es la longitud del prefijo común al inicio de la cadena hasta un máximo de 4 caracteres
• ${\displaystyle p}$es un factor de escala constante que indica cuánto se ajusta hacia arriba la puntuación por tener prefijos comunes. no debe exceder 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 de Jaro-Winkler se define como . ${\displaystyle d_{w}}$ ${\displaystyle d_{w}=1-sim_{w}}$

Aunque a menudo se la denomina métrica de distancia , la distancia de Jaro-Winkler no es una métrica en el sentido matemático del término porque no obedece a la desigualdad del triángulo . ^[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 supresió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 (LCS) más larga solo permite la inserción y eliminación, no la sustitución;
• la distancia de Hamming sólo permite sustitución, por lo tanto, sólo se aplica a cuerdas de la misma longitud.

La distancia de edición generalmente se define 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 alineación de secuencias de ADN , como el algoritmo de Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplica.

Ver también

• Vinculación de registros
• Censo

Notas a pie de página

1. Jaro, Matthew A. (1 de junio de 1989). "Avances en la metodología de vinculación de registros aplicada para comparar el 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 de vinculación de registros de Fellegi-Sunter".
3. "¿Qué es la similitud 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 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 1985 de Tampa, Florida". Revista de la Asociación Estadounidense de Estadística . 84 (406): 414–20. doi :10.1080/01621459.1989.10478785.
• Jaro, MA (1995). "Vínculo probabilístico de un gran archivo de datos de salud pública". Estadística en Medicina . 14 (5–7): 491–8. doi :10.1002/sim.4780140510. PMID  7792443.
• Winkler, NOSOTROS (1990). "Métricas de comparación de cadenas y reglas de decisión mejoradas en el modelo de vinculación de registros de Fellegi-Sunter" (PDF) . Actas de la Sección sobre Métodos de Investigación de Encuestas . Asociación Estadounidense de Estadística: 354–359.

• Winkler, NOSOTROS (2006). "Descripción general de la vinculación de registros y las 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