En informática y estadística , la distancia Jaro-Winkler es una métrica de cadena que mide una distancia de edición entre dos secuencias. Es una variante propuesta en 1990 por William E. Winkler de la métrica de distancia de Jaro (1989, Matthew A. Jaro ).
La distancia Jaro-Winkler usa 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 menor sea la distancia Jaro-Winkler para dos cuerdas, más similares serán las cuerdas. La puntuación se normaliza de modo que 0 significa una coincidencia exacta y 1 significa que no hay similitud. El documento original realmente 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 denomina 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 del triángulo .
Definición
Similitud Jaro
La similitud de Jaro de dos cadenas dadas y es
Dónde:
- es la longitud de la cuerda ;
- es el número de caracteres coincidentes (ver más abajo);
- es el número de transposiciones (ver más abajo).
Dos personajes de y respectivamente, se consideran coincidentes solo si son iguales y no más allá de personajes aparte.
Cada personaje de se compara con todos sus caracteres coincidentes en . El número de caracteres coincidentes (pero en orden de secuencia diferente) dividido por 2 define el número de transposiciones . Por ejemplo, al comparar CRATE con TRACE, solo 'R' 'A' 'E' son los caracteres coincidentes, es decir, m = 3. Aunque 'C', 'T' aparecen en ambas cadenas, están más separadas que 1 (el resultado de). Por tanto, t = 0. En DwAyNE versus DuANE, las letras coincidentes ya están en el mismo orden DANE, por lo que no se necesitan transposiciones.
Similitud Jaro-Winkler
La similitud Jaro-Winkler usa 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 cuerdas y , su similitud Jaro-Winkler es:
dónde:
- es la similitud de Jaro para cuerdas 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 de cuánto se ajusta la puntuación hacia arriba para 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 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 denomina 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 del triángulo . [1] La distancia Jaro-Winkler tampoco satisface el axioma de identidad.
Relación con otras métricas de distancia de edición
Hay 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 más larga (LCS) permite solo la inserción y la eliminación, no la sustitución;
- la distancia de Hamming solo permite la sustitución, por lo tanto, solo 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 Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplique.
Ver también
Notas al pie
- ^ "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 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). "Vinculación probabilística de archivo de datos de salud pública grande". Estadística en Medicina . 14 (5–7): 491–8. doi : 10.1002 / sim.4780140510 . PMID 7792443 .
- Winkler, WE (1990). "Métricas del comparador de cadenas y reglas de decisión mejoradas en el modelo Fellegi-Sunter de vinculación de registros" (PDF) . Actas de la sección sobre 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 las direcciones de investigación actuales" (PDF) . Serie de informes de investigación, RRS .