Similitudes Jaro-Winkler

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de diciembre de 2019; las comprobaciones requieren 9 ediciones .

En el campo de la informática y las estadísticas , la similitud de Jaro-Winkler es una medida de similitud de cadenas para medir la distancia entre dos secuencias de caracteres. Esta es una variante propuesta por William E. Winkler en 1999 basada en la distancia Jaro (1989, Matthew A. Jaro). De manera informal, la distancia de Jaro entre dos palabras es el número mínimo de transformaciones de un solo carácter necesarias para cambiar una palabra por otra.

Cuanto menor sea la distancia Jaro-Winkler para dos cadenas, más similares serán estas cadenas entre sí. El resultado se normaliza, por lo que significa que no hay similitud y significa coincidencia exacta. El parecido Jaro-Winkler es . $d_{w}$ ${\ estilo de visualización d_ {w} = 0}$ ${\ estilo de visualización d_ {w} = 1}$ ${\ Displaystyle 1-d_ {w}}$

Definición

Distancia Jaro

La distancia de Jaro entre dos cadenas dadas y esto: $DJ}$ $s_{1}$ $s_{2}$

d_{j}=\left\{{\begin{array}{ll}0&{\text{cuando }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {mt}{m}}\right)&{\text{de lo contrario}} \end{matriz}}\right.

Dónde:

${\ estilo de visualización | s_ {i} |}$ — longitud de la cadena ; $si}$
$metro$ — número de caracteres coincidentes (ver más abajo);
$t$ - la mitad del número de transposiciones (ver más abajo).

Se considera que dos caracteres de y respectivamente coinciden solo si son iguales y no más allá de . $s_{1}$ $s_{2}$ $\left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2))\right\rfloor -1$

Cada carácter de la cadena se compara con todos sus caracteres correspondientes en . El número de caracteres coincidentes (pero ordinales diferentes), que es divisible por 2, determina el número de transposiciones . Por ejemplo, al comparar la palabra CRATE con la palabra TRACE, solo 'R', 'A' y 'E' son caracteres coincidentes, es decir, m=3. Aunque 'C' y 'T' aparecen en ambas líneas, están más allá de 1, es decir, piso(5/2)-1=1. Por lo tanto, t=0. Al comparar DwAyNE con DuANE, las letras correspondientes ya están en el mismo orden DANE, por lo que no se necesitan permutaciones. $s_{1}$ $s_{2}$

Distancia Jaro-Winkler

La distancia de Jaro-Winkler utiliza un factor de escala , que otorga calificaciones más favorables a las cadenas que coinciden entre sí desde el principio hasta una determinada longitud , denominada prefijo. Dadas dos cadenas y . Su distancia Jaro-Winkler es: $pags$ $\ana$ $s_{1}$ $s_{2}$ $d_{w}$

d_{w}=d_{j}+(\ell p(1-d_{j}))

dónde:

$DJ}$ es la distancia Jaro para filas y $s_{1}$ $s_{2}$
$\ana$ - la longitud del prefijo común desde el principio de la cadena hasta un máximo de 4 caracteres
$pags$ es un factor de escala constante que se usa para ajustar la estimación hacia arriba para detectar la presencia de prefijos comunes. no debe exceder de 0,25, de lo contrario la distancia puede volverse mayor que 1. El valor estándar de esta constante en el trabajo de Winkler es: . $pags$ ${\ estilo de visualización p = 0,1}$

Si bien la distancia de Jaro-Winkler a menudo se denomina métrica de distancia , no es una métrica en el sentido matemático de la palabra porque no obedece a la desigualdad del triángulo . Además, la distancia Jaro-Winkler no satisface el axioma que dice que [1] . $d(x,y)=0\leftrightarrow x=y$

En algunas implementaciones del algoritmo de cálculo de distancia de Jaro-Winkler, se agrega una bonificación de prefijo solo si las cadenas comparadas tienen una distancia de Jaro por encima del "umbral de impulso" establecido . El umbral en la implementación de Winkler fue 0,7. $\ell p(1-d_{j})$ ${\ Displaystyle b_ {t}}$

d_{w}=\left\{{\begin{array}{ll}d_{j}&{\text{if }}d_{j}<b_{t}\\d_{j}+( \ell p(1-d_{j}))&{\text{de lo contrario}}\end{matriz}}\right.

Ejemplos

Cabe señalar que el código C de Winkler difiere en al menos dos lugares del trabajo publicado sobre la métrica de Jaro-Winkler. El primero es el uso de la tabla de errata (adjwt), y el segundo son algunas condiciones adicionales para cadenas largas.

Ejemplo 1

Se dan las cadenas MARTHA y MARHTA. Representemos su intersección en forma tabular: $s_{1}$ $s_{2}$

	METRO	A	R	T	H	A
METRO	una	0	0	0	0	0
A	0	una	0	0	0	0
R	0	0	una	0	0	0
H	0	0	0	0	una	0
T	0	0	0	una	0	0
A	0	0	0	0	0	una

Aquí, la distancia máxima es 6/2 - 1 = 2. Las celdas amarillas en la tabla anterior indican unos cuando los caracteres son idénticos (hay una coincidencia) y ceros en caso contrario.

Resulta:

${\ estilo de visualización m = 6}$
${\ estilo de visualización | s_ {1} | = 6}$
${\ estilo de visualización | s_ {2} | = 6}$
Hay caracteres T/H y H/T que no coinciden, lo que da como resultado: $t={\frac{2}{2}}=1$

Distancia Jaró:

d_{j}={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-1 {6}}\derecho)=0.9(4)

Para encontrar el resultado de Jaro-Winkler utilizando el peso estándar, seguimos buscando: ${\ estilo de visualización p = 0,1}$

{\ estilo de visualización \ ell = 3}

De este modo:

d_{w}=0.9(4)+(3\cdot 0.1(1-0.9(4)))=0.96(1)

Ejemplo 2

Se dan las cadenas DWAYNE y DUANE. Resulta: $s_{1}$ $s_{2}$

$metro=4$
${\ estilo de visualización | s_ {1} | = 6}$
${\ estilo de visualización | s_ {2} | = 5}$
$t={\frac{2}{2}}=1$

Distancia Jaró:

d_{j}={\frac {1}{3}}\left({\frac {4}{6}}+{\frac {4}{5}}+{\frac {4-1 {4}}\derecho)=0.73(8)

Para encontrar el resultado de Jaro-Winkler utilizando el peso estándar, seguimos buscando: ${\ estilo de visualización p = 0,1}$

{\ estilo de visualización \ ell = 1}

De este modo:

d_{w}=0,73(8)+(1\cdot 0,1(1-0,73(8)))=0,765

Ejemplo 3

Dadas las cadenas DIXON y DICKSONX . Resulta: $s_{1}$ $s_{2}$

	D	yo	X	O	norte
D	una	0	0	0	0
yo	0	una	0	0	0
C	0	0	0	0	0
k	0	0	0	0	0
S	0	0	0	0	0
O	0	0	0	una	0
norte	0	0	0	0	una
X	0	0	0	0	0

Aquí, las celdas llenas son la ventana correspondiente para cada carácter. Una unidad en una celda indica una coincidencia. Tenga en cuenta que las dos x (X) no se consideran una coincidencia porque están fuera de la tercera ventana de coincidencia.

$metro=4$
${\ estilo de visualización | s_ {1} | = 5}$
${\ estilo de visualización | s_ {2} | = 8}$
$t = 0$

Distancia Jaró:

d_{j}={\frac {1}{3}}\left({\frac {4}{5}}+{\frac {4}{8}}+{\frac {4-0 {4}}\derecho)=0.7(6)

Para encontrar el resultado de Jaro-Winkler utilizando el peso estándar, seguimos buscando: ${\ estilo de visualización p = 0,1}$

{\ estilo de visualización \ ell = 2}

De este modo:

d_{w}=0.7(6)+(2\cdot 0.1(1-0.7(6)))=0.81(3)

Relaciones con otras métricas de cambio de distancia

Hay otras medidas populares de cambio de distancia que se calculan utilizando un conjunto diferente de operaciones de edición válidas. Por ejemplo,

La distancia de Levenshtein permite borrar, insertar y reemplazar caracteres;
La distancia Damerau-Levenshtein permite la inserción, eliminación, reemplazo y permutación de dos caracteres adyacentes;
La subsecuencia común máxima solo permite inserciones y eliminaciones, no reemplazos;
La distancia de Hamming solo permite la sustitución, por lo que solo se aplica a cadenas de la misma longitud.

El cambio en la distancia generalmente se define como una métrica parametrizable que se calcula utilizando un determinado conjunto de operaciones de edición válidas, y a cada operación se le asigna un costo (quizás infinito). Esta es una generalización adicional de los algoritmos de alineación de secuencias genéticas , como el algoritmo de Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplique.

Aplicación práctica

Se utilizó el algoritmo de Jaro-Winkler para procesar los resultados del censo de población [2] .
El algoritmo de comparación de cadenas de Jaro-Winkler se implementa en Oracle DBMS [3] .

Implementaciones del algoritmo en varios lenguajes de programación

Implementación del algoritmo en C [4] * strcmp95 . c Versión 2 */ /* La función strcmp95 devuelve un valor de doble precisión de 0,0 ( desacuerdo total) a 1,0 (acuerdo carácter por carácter). El valor devuelto es una medida de la similitud de las dos cadenas. */ /* Fecha de lanzamiento: enero. 26, 1994 */ /* Modificado: 24 de abril de 1994 Se corrigió el procesamiento de las cadenas de caracteres de longitud única. Autores: esta función se escribió usando la lógica del código escrito por Bill Winkler, George McLaughlin y Matt Jaro con modificaciones de Maureen Lynch. Comentario: Este es el comparador oficial de cadenas que se usará para la comparación durante el Censo de prueba de 1995. */ # incluir <ctipo.h> # incluir <cadena.h> # define NOTNUM(c) ((c>57) || (c<48)) # define INRANGE(c) ((c>0) && (c<91)) # define MAX_VAR_SIZE 61 # define NULL60 " " doble strcmp95 ( char * ying , char * yang , long y_length , int * ind_c []) { /* Argumentos: ying y yang son punteros a las 2 cadenas que se van a comparar. Las cadenas no necesitan ser cadenas terminadas en NUL porque se pasa la longitud. y_length es la longitud de las cadenas. ind_c es una matriz que se utiliza para determinar si se deben activar ciertas opciones. Un valor distinto de cero indica que la opción está desactivada. Las opciones son: ind_c[0] Aumenta la probabilidad de una coincidencia cuando el número de caracteres coincidentes es grande. Esta opción permite un poco más de tolerancia cuando las cadenas son grandes. No es una prueba adecuada cuando se comparan campos de longitud fija, como números de teléfono y de seguridad social. ind_c[1] Todos los caracteres en minúsculas se convierten a mayúsculas antes de la comparación. Deshabilitar esta función significa que la cadena en minúsculas "código" no se reconocerá como la misma cadena en mayúsculas "CÓDIGO". Además, la sección de ajuste de caracteres similares solo se aplica a los caracteres en mayúsculas. Los valores sugeridos son todos ceros para cadenas de caracteres como nombres. */ static int pass = 0 , adjwt [ 91 ][ 91 ]; sp de caracteres estáticos [ 39 ][ 2 ] = { 'A' , 'E' , 'A' , 'I' , 'A' , 'O' , 'A' , 'U' , 'B' , 'V' , 'E' , 'I' , ' E' , 'O' , 'E' , 'U' , 'I' , 'O' , 'I' , 'U' , 'O' , 'U' , 'I' , 'Y' , 'E' , 'Y' , 'C' , 'G' , 'E ' , 'F' , 'W' , 'U' , 'W' , 'V' , 'X' , 'K' , 'S' , 'Z' , 'X' , 'S' , 'Q' , 'C' , 'U ' , 'V' , 'M' , 'N' , 'L' , 'I' , 'Q' , 'O' , 'P' , 'R' , 'I' , 'J' , '2' , 'Z' , '5 ' , 'S' , '8' , 'B' , '1' , 'I' , '1' , 'L' , '0' , 'O' , '0' , 'Q' , 'C' , 'K' , 'G ' , 'J' , 'E' , ' ' , 'Y' , ' ' , 'S' , ' ' }; char ying_hold [ MAX_VAR_SIZE ], yang_mantener [ MAX_VAR_SIZE ], bandera_ying [ MAX_VAR_SIZE ], yang_bandera [ MAX_VAR_SIZE ]; peso doble , Num_sim ; _ minv largo , rango_de_búsqueda , límite_bajo , longitud_ying , hilim , N_trans , Num_com , yang_length ; int yl1 , yi_st , N_simi ; registro int i , j , k ; /* Inicializar la matriz adjwt en la primera llamada a la función solamente. La matriz adjwt se utiliza para dar crédito parcial a los caracteres que pueden ser errores debido a errores fonéticos o de reconocimiento de caracteres conocidos. Un ejemplo típico es hacer coincidir la letra "O" con el número "0" */ si ( ! pasar ) { pasar ++ ; for ( i = 0 ; i < 91 ; i ++ ) for ( j = 0 ; j < 91 ; j ++ ) adjwt [ i ][ j ] = 0 ; para ( yo = 0 ; yo < 36 ; yo ++ ) { adjwt [ sp [ i ][ 0 ]][ sp [ i ][ 1 ]] = 3 ; adjwt [ sp [ i ][ 1 ]][ sp [ i ][ 0 ]] = 3 ; } } /* Si cualquiera de las cadenas está en blanco - retorno - agregado en la Versión 2 */ if ( ! strncmp ( ying , NULL60 , y_length )) return ( 0.0 ); if ( ! strncmp ( yang , NULL60 , y_length )) return ( 0.0 ); /* Identifique las cadenas que se compararán eliminando todos los espacios iniciales y finales. */ k = y_longitud - 1 ; for ( j = 0 ;(( ying [ j ] == ' ' ) && ( j < k )); j ++ ); for ( i = k ;(( ying [ i ] == ' ' ) && ( i > 0 )); i -- ); longitud_ying = i + 1 - j ; yi_st = j ; for ( j = 0 ;(( yang [ j ] == ' ' ) && ( j < k )); j ++ ); for ( i = k ;(( yang [ i ] == ' ' ) && ( i > 0 )); i -- ); yang_longitud = yo + 1 - j ; ying_hold [ 0 ] = yang_hold [ 0 ] = 0 ; strncat ( ying_hold , & ying [ yi_st ], ying_length ); strncat ( yang_hold , & yang [ j ], yang_length ); if ( longitud_ying > longitud_yang ) { rango_búsqueda = longitud_ying ; minv = yang_longitud ; } más { rango_búsqueda = longitud_yang ; minv = longitud_ying ; } /* Si cualquiera de las cadenas está en blanco, devuelve */ /* si (! minv) devuelve (0.0); eliminado en la versión 2 */ /* Borrar las banderas */ bandera_ying [ 0 ] = bandera_ying [ 0 ] = 0 ; strncat ( ying_flag , NULL60 , search_range ); strncat ( yang_flag , NULL60 , search_range ); rango_busqueda = ( rango_busqueda / 2 ) - 1 ; if ( rango_de_búsqueda < 0 ) rango_de_búsqueda = 0 ; /* añadido en la versión 2 */ /* Convierte todos los caracteres en minúsculas a mayúsculas. */ si ( ! ind_c [ 1 ]) { for ( i = 0 ; i < ying_length ; i ++ ) if ( islower ( ying_hold [ i ])) ying_hold [ i ] -= 32 ; for ( j = 0 ; j < yang_longitud ; j ++ ) if ( islower ( yang_hold [ j ])) yang_hold [ j ] -= 32 ; } /* Mirando solo dentro del rango de búsqueda, cuente y marque los pares coincidentes. */ num_com = 0 ; yl1 = yang_longitud - 1 ; for ( i = 0 ; i < longitud_ying ; i ++ ) { lowlim = ( i >= search_range ) ? i - search_range : 0 ; hilim = (( i + search_range ) <= yl1 ) ? ( i + rango_búsqueda ) : yl1 ; for ( j = límite bajo ; j <= hilo ; j ++ ) { if (( yang_flag [ j ] != '1' ) && ( yang_hold [ j ] == ying_hold [ i ])) { bandera_yang [ j ] = '1' ; bandera_ying [ i ] = '1' ; Num_com ++ ; romper ; } } } /* Si no hay caracteres en común - retorno */ si ( ! Num_com ) devuelve ( 0.0 ); /* Cuenta el numero de transposiciones */ k = N_trans = 0 ; for ( i = 0 ; i < longitud_ying ; i ++ ) { if ( bandera_ying [ i ] == '1' ) { para ( j = k ; j < longitud_yang ; j ++ ) { if ( yang_flag [ j ] == '1' ) { k = j + 1 ; romper ; } } if ( ying_hold [ i ] != yang_hold [ j ]) N_trans ++ ; } } N_trans = N_trans / 2 ; /* ajustar las similitudes en los caracteres que no coinciden */ N_sim = 0 ; if ( minv > Num_com ) { for ( i = 0 ; i < longitud_ying ; i ++ ) { if ( ying_flag [ i ] == ' ' && INRANGE ( ying_hold [ i ])) { for ( j = 0 ; j < yang_length ; j ++ ) { if ( yang_flag [ j ] == ' ' && INRANGE ( yang_hold [ j ])) { if ( adjwt [ ying_hold [ i ]][ yang_hold [ j ]] > 0 ) { N_simi += adjwt [ ying_hold [ i ]][ yang_hold [ j ]]; bandera_yang [ j ] = '2' ; romper ; } } } } } } Num_sim = (( doble ) N_simi ) / 10.0 + Num_com ; /* Cálculo del peso principal. */ peso = Num_sim / (( doble ) longitud_ying ) + Num_sim / (( doble ) longitud_yang ) + (( doble ) ( Num_com - N_trans )) / (( doble ) Num_com ); peso = peso / 3.0 ; /* Continuar aumentando el peso si las cadenas son similares */ si ( peso > 0.7 ) { /* Ajuste por tener hasta los primeros 4 caracteres en común */ j = ( minv >= 4 ) ? 4 : minv ; for ( i = 0 ;(( i < j ) && ( ying_hold [ i ] == yang_hold [ i ]) && ( NOTNUM ( ying_hold [ i ]))); i ++ ); si ( i ) peso += i * 0.1 * ( 1.0 - peso ); /* Opcionalmente ajuste para cadenas largas. */ /* Después de acordar los caracteres iniciales, al menos dos más deben coincidir y los caracteres coincidentes deben ser > .5 de los caracteres restantes. */ if (( ! ind_c [ 0 ]) && ( minv > 4 ) && ( Num_com > i + 1 ) && ( 2 * Num_com >= minv + i )) if ( NOTNUM ( ying_hold [ 0 ])) peso += ( doble ) ( 1.0 - peso ) * (( doble ) ( Num_com - i -1 ) / (( doble ) ( longitud_ying + longitud_yang - i * 2 + 2 ))); } retorno ( peso ); } /* strcmp95 */ Implementación del algoritmo en Delphi [5] función JaroWinkler ( prmT1 , prmT2 : Cadena ; p : Doble = 0.1 ) : Doble ; Var ecartMax , l1 , l2 , compteMatching , compteTransposition , longueurPrefix , i , j : entero ; c1 , c2 , t1Coincidencia , t2Coincidencia : cadena ; b1 , b2 : matriz de valores booleanos ; distanciaJaro : Doble ; etiqueta endfor , exitfor2 ; function TrouverMatches ( prmTextInitial : string ; b1 : array of Boolean ) : string ; var i : entero ; res : cadena _ begin // Calcule el nombre de las características que coinciden con i := 1 to Length ( prmTextInitial ) do begin if b1 [ i ] then //prmTextMatche[i]='_' then begin res := res + prmTextInitial [ i ] ; fin ; fin ; TrouverCoincidencias := res ; fin ; comenzar ecartMax := round ( Max ( Longitud ( prmT1 ) , Longitud ( prmT2 )) / 2 ) - 1 ; si (( prmT1 = '' ) o ( prmT2 = '' )) entonces empieza JaroWinkler := 0 ; salida ; fin ; compteMatching := 0 ; compteTransposition := 0 ; l1 := Longitud ( prmT1 ) ; l2 := Longitud ( prmT2 ) ; conjuntolongitud ( b1 , l1 + 1 ) ; Establecer longitud ( b2 , l2 + 1 ) ; para i := 0 a l1 empieza b1 [ i ] : = false ; fin ; para i := 0 a l2 empieza b2 [ i ] : = false ; fin ; for i := 1 to l1 do begin c1 := prmT1 [ i ] ; si ( i <= l2 ) entonces c2 := prmT2 [ i ] else c2 := '' ; para j := Max ( i - ecartMax , 1 ) a Min ( i + ecartMax , l2 ) comience c2 : = prmT2 [ j ] ; if c1 = c2 entonces //compteMatching avec transposition begin b1 [ i ] := true ; b2 [ j ] := verdadero ; // Le caractère a été matché, il n'est plus disponible Inc ( compteMatching ) ; romper ; fin ; fin ; fin ; si ( compteMatching = 0 ) luego comience JaroWinkler := 0 ; salida ; fin ; //Dans les caractères matchés, compte ceux qui ne matchent pas exactement t1Matche := TrouverMatches ( prmT1 , b1 ) ; t2Coincidencia := TrouverCoincidencias ( prmT2 , b2 ) ; si t1Matche <> t2Matche entonces comienza para i : = 1 hasta la longitud ( t1Matche ) comienza si t1Matche [ i ] <> t2Matche [ i ] luego Inc ( compleTransposition ) end ; end else begin compteTransposition := 0 ; fin ; distanciaJaro := 1 / 3 * (( compteMatching / l1 ) + ( compteMatching / l2 ) + (( compteMatching - Int ( compteTransposition / 2 )) / compteMatching )) ; // Calcular la distancia Winkler // Calcular el prefijo entre los 4 primeros coches aux max longueurPrefix := 0 ; for i := 1 to min ( 4 , min ( l1 , l2 )) do begin c1 := prmT1 [ i ] ; c2 := prmT2 [ i ] ; si c1 = c2 entonces inc ( prefijolongitudinal ) de lo contrario romper ; fin ; //Valor constante definido por el algoritmo JaroWinkler := distanciaJaro + ( longueurPrefix * p * ( 1 - distanciaJaro )) ; fin ; Implementación del algoritmo en PHP [6] <?php /* versión 1.2 Copyright (c) 2005-2010 Ivo Ugrina <[email protected]> Una biblioteca PHP que implementa la distancia Jaro y Jaro-Winkler , midiendo la similitud entre cadenas. El material teórico se puede encontrar en: Winkler, W.E. (1999). "El estado de la vinculación de registros y los problemas de investigación actuales". Estadísticas de la División de Ingresos, Servicio de Rentas Internas Publicación R99/04. http://www.census.gov/srd/papers/pdf/rr99-04.pdf. Este programa es software libre; puede redistribuirlo y/o modificarlo según los términos de la Licencia Pública General de GNU publicada por la Free Software Foundation; ya sea la versión 3 de la Licencia o (a su elección) cualquier versión posterior. Este programa se distribuye con la esperanza de que sea útil, pero SIN NINGUNA GARANTÍA; sin siquiera la garantía implícita de COMERCIABILIDAD o IDONEIDAD PARA UN PROPÓSITO PARTICULAR. Consulte la Licencia pública general de GNU para obtener más detalles. Debería haber recibido una copia de la Licencia Pública General de GNU junto con este programa. Si no, consulte <http://www.gnu.org/licenses/>. === Muchas gracias a Pierre Senellart <[email protected]> por encontrar un pequeño error en el código. */ función getCommonCharacters ( $ string1 , $ string2 , $allowedDistance ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); $temp_cadena2 = $cadena2 ; $caracterescomunes = '' ; para ( $i = 0 ; $i < $str1_len ; $i ++ ){ $noCoincidencia = Verdadero ; // comparar si el carácter coincide dentro de la distancia permitida dada // y si lo hace, agréguelo a caracteres comunes para ( $j = max ( 0 , $i - $distancia permitida ); $noCoincidencia && $j < min ( $i + $distancia permitida + 1 , $str2_len ); $j ++ ){ if ( $temp_string2 [ $j ] == $string1 [ $i ] ){ $noMatch = False ; $caracterescomunes .= $cadena1 [ $i ]; $temp_string2 [ $j ] = '' ; } } } devuelve $caracterescomunes ; } function Jaro ( $cadena1 , $cadena2 ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); // distancia teórica $distancia = piso ( min ( $str1_len , $str2_len ) / 2.0 ); // obtener caracteres comunes $commons1 = getCommonCharacters ( $string1 , $string2 , $distance ); $comunes2 = obtenerCaracteresComunes ( $cadena2 , $cadena1 , $distancia ); if ( ( $commons1_len = strlen ( $commons1 )) == 0 ) return 0 ; if ( ( $commons2_len = strlen ( $commons2 )) == 0 ) devuelve 0 ; // calcular transposiciones $ transposiciones = 0 ; $límitesuperior = min ( $comunes1_len , $comunes2_len ); for ( $i = 0 ; $i < $superiorBound ; $i ++ ){ if ( $comunes1 [ $i ] != $comunes2 [ $i ] ) $transposiciones ++ ; } $transposiciones /= 2.0 ; // devuelve el retorno de distancia Jaro ( $ commons1_len / ( $str1_len ) + $commons2_len / ( $str2_len ) + ( $commons1_len - $transpositions ) / ( $commons1_len )) / 3.0 ; } función getPrefixLength ( $cadena1 , $cadena2 , $MINPREFIXLENGTH = 4 ){ $n = min ( arreglo ( $MINPREFIXLENGTH , strlen ( $string1 ), strlen ( $ string2 ) )) ); for ( $i = 0 ; $i < $n ; $i ++ ){ if ( $cadena1 [ $i ] != $cadena2 [ $i ] ){ // devuelve el índice de la primera aparición de diferentes caracteres devuelve $i ; } } // los primeros n caracteres son iguales return $n ; } función JaroWinkler ( $cadena1 , $cadena2 , $PREFIXSCALE = 0.1 ){ $JaroDistancia = Jaro ( $cadena1 , $cadena2 ); $prefixLength = getPrefixLength ( $cadena1 , $cadena2 ); return $JaroDistance + $prefixLength * $PREFIXSCALE * ( 1.0 - $JaroDistance ); } ?>

Notas

↑ Algoritmos de vinculación de registros en F# - Extensiones a la distancia Jaro-Winkler (Parte 3) . Consultado el 21 de marzo de 2017. Archivado desde el original el 31 de diciembre de 2019. (indefinido)
↑ Algoritmos de comparación de texto aproximados, Parte 2 . Consultado el 21 de marzo de 2017. Archivado desde el original el 22 de marzo de 2017. (indefinido)
↑ Referencia de tipos y paquetes de PL/SQL de base de datos . Consultado el 21 de marzo de 2017. Archivado desde el original el 12 de enero de 2017. (indefinido)
↑ Copia archivada (enlace no disponible) . Consultado el 23 de febrero de 2011. Archivado desde el original el 23 de febrero de 2011. (indefinido)
↑ Distance de jaro-winkler Archivado el 22 de marzo de 2017 en Wayback Machine (FR)
↑ [1 ]

Enlaces

Cohen, WW Una comparación de métricas de distancia de cadenas para tareas de coincidencia de nombres // Taller KDD sobre limpieza de datos y consolidación de objetos: diario. - 2003. - vol. 3 . - Pág. 73-8 .
Jaro, MA 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 : revista. - 1989. - vol. 84 , núm. 406 . - P. 414-420 . -doi : 10.1080/ 01621459.1989.10478785 .
Jaro, MA Enlace probabilístico de un gran archivo de datos de salud pública (inglés) // Estadísticas en medicina: revista. - 1995. - vol. 14 , núm. 5-7 . - pág. 491-498 . -doi : 10.1002/ sim.4780140510 . — PMID 7792443 .
Winkler, WE String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage // Actas de la Sección sobre Métodos de Investigación de Encuestas: revista. - Asociación Estadounidense de Estadística, 1990. - P. 354-359 . Archivado desde el original el 13 de febrero de 2015.
Guillermo E. Winkler. Descripción general de la vinculación de registros y las direcciones de investigación actuales // Serie de informes de investigación, RRS: revista. — 2006.