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 .
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
Dónde:
- es la longitud de la cadena ;
- es el número de caracteres coincidentes (ver más abajo);
- 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.
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.
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:
dónde:
- ¿Cuál es la similitud de Jaro para cadenas y
- es la longitud del prefijo común al comienzo de la cadena hasta un máximo de 4 caracteres
- 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
La distancia Jaro-Winkler se define como .
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 .
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 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
Notas al pie
- ^ 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.
- ^ 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".
- ^ "¿Qué es la similitud de Jaro-Winkler?". www.baseclass.io . Archivado desde el original el 28 de enero de 2024. Consultado el 26 de julio de 2012 .
{{cite web}}
: CS1 maint: bot: estado de URL original desconocido ( enlace ) - ^ "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