Asemănarea Jaro-Winkler

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 decembrie 2019; verificările necesită 9 modificări .

În domeniul informaticii și statisticii , asemănarea Jaro-Winkler este o măsură a asemănării șirurilor pentru a măsura distanța dintre două secvențe de caractere. Aceasta este o variantă propusă de William E. Winkler în 1999 pe baza distanței Jaro (1989, Matthew A. Jaro). În mod informal, distanța Jaro dintre două cuvinte este numărul minim de transformări cu un singur caracter necesare pentru a schimba un cuvânt cu altul.

Cu cât distanța Jaro-Winkler este mai mică pentru două șiruri, cu atât aceste șiruri sunt mai asemănătoare între ele. Rezultatul este normalizat, astfel încât nu înseamnă nicio asemănare și înseamnă potrivire exactă. Asemănarea Jaro-Winkler este . $d_{w}$ $d_{w}=0$ $d_{w}=1$ $1-d_{w)$

Definiție

Distanța Jaro

Distanța lui Jaro între două șiruri date și aceasta: $d_{j}$ $s_{1}$ $s_{2}$

d_{j}=\left\{{\begin{array}{ll}0&{\text{when }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {mt}{m}}\right)&{\text{altfel }} \end{matrice}}\right.

Unde:

$|s_{i}|$ - lungimea șirului ; $si}$
$m$ — numărul de caractere care se potrivesc (vezi mai jos);
$t$ - jumătate din numărul de transpuneri (vezi mai jos).

Două caractere de la și respectiv sunt considerate a se potrivi numai dacă sunt aceleași și nu mai mult de . $s_{1}$ $s_{2}$ $\left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2))\right\rfloor -1$

Fiecare caracter din șir este comparat cu toate caracterele sale corespunzătoare în . Numărul de caractere care se potrivesc (dar ordinale diferite), care este divizibil cu 2, determină numărul de transpoziții . De exemplu, când se compară cuvântul CRATE cu cuvântul TRACE, doar „R” „A” și „E” sunt caractere care se potrivesc, adică m=3. Deși „C” și „T” apar pe ambele linii, ele sunt mai departe de 1, adică floor(5/2)-1=1. Prin urmare, t=0. În compararea DwAyNE cu DuANE, literele corespunzătoare sunt deja în aceeași ordine DANE, deci nu sunt necesare permutări. $s_{1}$ $s_{2}$

Distanța Jaro-Winkler

Distanța Jaro-Winkler folosește un factor de scalare , care oferă evaluări mai favorabile șirurilor care se potrivesc între ele de la început până la o anumită lungime , numită prefix. Date două șiruri și . Distanța lor Jaro-Winkler este: $p$ $\ell$ $s_{1}$ $s_{2}$ $d_{w}$

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

Unde:

$d_{j}$ este distanța Jaro pentru rânduri și $s_{1}$ $s_{2}$
$\ell$ - lungimea prefixului comun de la începutul șirului până la maximum 4 caractere
$p$ este un factor de scalare constant utilizat pentru a ajusta estimarea în sus pentru a detecta prezența prefixelor comune. nu trebuie să depășească 0,25, altfel distanța poate deveni mai mare de 1. Valoarea standard a acestei constante în opera lui Winkler este: . $p$ $p=0,1$

În timp ce distanța Jaro-Winkler este adesea menționată ca metrică a distanței , nu este o metrică în sensul matematic al cuvântului, deoarece nu se supune inegalității triunghiului . De asemenea distanța Jaro-Winkler nu satisface axioma care spune că [1] . $d(x,y)=0\leftrightarrow x=y$

În unele implementări ale algoritmului de calcul al distanței Jaro-Winkler, un bonus de prefix este adăugat numai dacă șirurile comparate au o distanță Jaro peste „pragul de creștere” setat . Pragul în implementarea lui Winkler a fost 0,7. $\ell p(1-d_{j})$ $b_{t)$

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

Exemple

Trebuie remarcat faptul că codul C al lui Winkler diferă în cel puțin două locuri de lucrarea publicată asupra metricii Jaro-Winkler. Prima este utilizarea tabelului errata (adjwt), iar a doua este unele condiții suplimentare pentru șiruri lungi.

Exemplul 1

Sunt date șirurile MARTHA și MARHTA. Să reprezentăm intersecția lor în formă tabelară: $s_{1}$ $s_{2}$

	M	A	R	T	H	A
M	unu	0	0	0	0	0
A	0	unu	0	0	0	0
R	0	0	unu	0	0	0
H	0	0	0	0	unu	0
T	0	0	0	unu	0	0
A	0	0	0	0	0	unu

Aici, distanța maximă este 6/2 - 1 = 2. Celulele galbene din tabelul de mai sus indică unele când caracterele sunt identice (există o potrivire), iar zerouri în caz contrar.

Se dovedește:

$m=6$
$|s_{1}|=6$
$|s_{2}|=6$
Există caractere nepotrivite T/H și H/T, rezultând: $t={\frac {2}{2}}=1$

Distanța Jaro:

d_{j}={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-1 }{6}}\right)=0,9(4)

Pentru a găsi rezultatul Jaro-Winkler folosind greutatea standard, continuăm să căutăm: $p=0,1$

\ell =3

În acest fel:

d_{w}=0,9(4)+(3\cdot 0,1(1-0,9(4)))=0,96(1)

Exemplul 2

Sunt date șirurile DWAYNE și DUANE. Se dovedește: $s_{1}$ $s_{2}$

$m=4$
$|s_{1}|=6$
$|s_{2}|=5$
$t={\frac {2}{2}}=1$

Distanța Jaro:

d_{j}={\frac {1}{3}}\left({\frac {4}{6}}+{\frac {4}{5}}+{\frac {4-1 }{4}}\right)=0,73(8)

Pentru a găsi rezultatul Jaro-Winkler folosind greutatea standard, continuăm să căutăm: $p=0,1$

\ell =1

În acest fel:

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

Exemplul 3

Corzile date DIXON și DICKSONX . Se dovedește: $s_{1}$ $s_{2}$

	D	eu	X	O	N
D	unu	0	0	0	0
eu	0	unu	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	unu	0
N	0	0	0	0	unu
X	0	0	0	0	0

Aici, celulele umplute sunt fereastra potrivită pentru fiecare caracter. O unitate dintr-o celulă indică o potrivire. Rețineți că cele două x-uri (X-uri) nu sunt considerate potriviri deoarece se află în afara celei de-a treia ferestre de potrivire.

$m=4$
$|s_{1}|=5$
$|s_{2}|=8$
$t = 0$

Distanța Jaro:

d_{j}={\frac {1}{3}}\left({\frac {4}{5}}+{\frac {4}{8}}+{\frac {4-0 }{4}}\right)=0,7(6)

Pentru a găsi rezultatul Jaro-Winkler folosind greutatea standard, continuăm să căutăm: $p=0,1$

\ell =2

În acest fel:

d_{w}=0,7(6)+(2\cdot 0,1(1-0,7(6)))=0,81(3)

Relațiile cu alte valori ale modificării distanței

Există și alte măsuri populare de modificare a distanței care sunt calculate folosind un set diferit de operațiuni de editare valide. De exemplu,

Distanța Levenshtein permite ștergerea, inserarea și înlocuirea caracterelor;
Distanța Damerau-Levenshtein permite inserarea, ștergerea, înlocuirea și permutarea a două caractere adiacente;
Cea mai mare subsecvență comună permite doar inserții și ștergeri, nu înlocuiri;
Distanța de hamming permite doar înlocuirea, deci se aplică doar șirurilor de aceeași lungime.

Modificarea distanței este de obicei definită ca o metrică parametrizabilă calculată folosind un anumit set de operații de editare valide și fiecărei operații i se atribuie un cost (poate infinit). Aceasta este o generalizare suplimentară a algoritmilor de aliniere a secvenței genetice , cum ar fi algoritmul Smith-Waterman , care fac ca costul unei operații să depindă de locul în care este aplicat.

Aplicație practică

Algoritmul Jaro-Winkler a fost utilizat pentru procesarea rezultatelor recensământului populației [2] .
Algoritmul de comparare a șirurilor Jaro-Winkler este implementat în Oracle DBMS [3] .

Implementări ale algoritmului în diferite limbaje de programare

Implementarea algoritmului în C [4] * strcmp95 . c Versiunea 2 */ /* Funcția strcmp95 returnează o valoare dublă de precizie de la 0,0 ( dezacord total) la 1,0 (acord caracter cu caracter). Valoarea returnată este o măsură a asemănării celor două șiruri. */ /* Data lansării: ian. 26, 1994 */ /* Modificat: 24 aprilie 1994 S-a corectat procesarea șirurilor de caractere cu o singură lungime. Autorii: Această funcție a fost scrisă folosind logica din codul scris de Bill Winkler, George McLaughlin și Matt Jaro cu modificări de Maureen Lynch. Comentariu: Acesta este comparatorul oficial de șiruri care va fi utilizat pentru potrivire în timpul recensământului de testare din 1995. */ # include <ctype.h> # include <string.h> # definește NOTNUM(c) ((c>57) || (c<48)) # define INRANGE(c) ((c>0) && (c<91)) # define MAX_VAR_SIZE 61 # define NULL60 " " double strcmp95 ( char * ying , char * yang , lung y_length , int * ind_c []) { /* Argumente: ying și yang sunt indicii către cele 2 șiruri care trebuie comparate. Șirurile nu trebuie să fie șiruri terminate cu NUL, deoarece lungimea este trecută. y_length este lungimea șirurilor. ind_c este o matrice care este folosită pentru a determina dacă anumite opțiuni ar trebui activate. O valoare diferită de zero indică că opțiunea este dezactivată. Opțiunile sunt: ind_c[0] Mărește probabilitatea unei potriviri atunci când numărul de caractere potrivite este mare. Această opțiune permite puțin mai multă toleranță atunci când șirurile sunt mari. Nu este un test adecvat atunci când se compară câmpuri cu lungime fixă, cum ar fi numerele de telefon și de securitate socială. ind_c[1] Toate caracterele mici sunt convertite în majuscule înainte de comparare. Dezactivarea acestei funcții înseamnă că șirul „cod” cu majuscule nu va fi recunoscut ca fiind același cu șirul cu majuscule „COD”. De asemenea, secțiunea de ajustare pentru caractere similare se aplică numai caracterelor majuscule. Valorile sugerate sunt toate zerouri pentru șirurile de caractere, cum ar fi numele. */ static int trecere = 0 , adjwt [ 91 ][ 91 ]; static char sp [ 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_hold [ MAX_VAR_SIZE ], ying_flag [ MAX_VAR_SIZE ], yang_flag [ MAX_VAR_SIZE ]; greutate dublă , Num_sim ; _ long minv , search_range , lowlim , ying_length , hilim , N_trans , Num_com , yang_length ; int yl1 , yi_st , N_simi ; înregistrare int i , j , k ; /* Inițializați matricea adjwt numai la primul apel la funcție. Matricea adjwt este folosită pentru a acorda credit parțial caracterelor care pot fi erori din cauza unor erori fonetice sau de recunoaștere a caracterelor cunoscute. Un exemplu tipic este să potriviți litera „O” cu numărul „0” */ dacă ( ! trece ) { trece ++ ; pentru ( i = 0 ; i < 91 ; i ++ ) pentru ( j = 0 ; j < 91 ; j ++ ) adjwt [ i ][ j ] = 0 ; pentru ( i = 0 ; i < 36 ; i ++ ) { adjwt [ sp [ i ][ 0 ]][ sp [ i ][ 1 ]] = 3 ; adjwt [ sp [ i ][ 1 ]][ sp [ i ][ 0 ]] = 3 ; } } /* Dacă oricare șir este gol - return - adăugat în versiunea 2 */ if ( ! strncmp ( ying , NULL60 , y_length )) return ( 0,0 ); if ( ! strncmp ( yang , NULL60 , y_length )) return ( 0.0 ); /* Identificați șirurile care trebuie comparate prin eliminarea tuturor spațiilor de început și de final. */ k = y_lungime - 1 ; pentru ( j = 0 ;(( ying [ j ] == ' ' ) && ( j < k )); j ++ ); pentru ( i = k ;(( ying [ i ] == ' ' ) && ( i > 0 )); i -- ); ying_length = i + 1 - j ; yi_st = j ; pentru ( j = 0 ;(( yang [ j ] == ' ' ) && ( j < k )); j ++ ); pentru ( i = k ;(( yang [ i ] == ' ' ) && ( i > 0 )); i -- ); yang_length = i + 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 ( lungime_ying > lungime_yang ) { interval_căutare = lungime_ying ; minv = yang_length ; } else { interval_căutare = lungime_yang ; minv = ying_length ; } /* Dacă oricare șir este gol - returnează */ /* dacă (!minv) return(0.0); eliminat în versiunea 2 */ /* Golește steagurile */ ying_flag [ 0 ] = ying_flag [ 0 ] = 0 ; strncat ( ying_flag , NULL60 , search_range ); strncat ( yang_flag , NULL60 , search_range ); interval_căutare = ( interval_căutare / 2 ) - 1 ; if ( interval_căutare < 0 ) interval_căutare = 0 ; /* adăugat în versiunea 2 */ /* Convertește toate caracterele minuscule în majuscule. */ dacă ( ! ind_c [ 1 ]) { for ( i = 0 ; i < ying_length ; i ++ ) if ( islower ( ying_hold [ i ])) ying_hold [ i ] -= 32 ; for ( j = 0 ; j < yang_length ; j ++ ) if ( islower ( yang_hold [ j ])) yang_hold [ j ] -= 32 ; } /* Căutând numai în intervalul de căutare, numărați și semnalizați perechile potrivite. */ Num_com = 0 ; yl1 = yang_length - 1 ; pentru ( i = 0 ; i < ying_length ; i ++ ) { lowlim = ( i >= search_range ) ? i - interval_căutare : 0 ; hilim = (( i + search_range ) <= yl1 ) ? ( i + interval_căutare ) : yl1 ; pentru ( j = lowlim ; j <= hilim ; j ++ ) { dacă (( yang_flag [ j ] != '1' ) && ( yang_hold [ j ] == ying_hold [ i ])) { yang_flag [ j ] = '1' ; ying_flag [ i ] = '1' ; Num_com ++ ; rupe ; } } } /* Dacă nu există caractere în comun - returnează */ if ( ! Num_com ) return ( 0.0 ); /* Numără numărul de transpoziții */ k = N_trans = 0 ; pentru ( i = 0 ; i < ying_length ; i ++ ) { if ( ying_flag [ i ] == '1' ) { pentru ( j = k ; j < yang_length ; j ++ ) { if ( yang_flag [ j ] == '1' ) { k = j + 1 ; rupe ; } } if ( ying_hold [ i ] != yang_hold [ j ]) N_trans ++ ; } } N_trans = N_trans / 2 ; /* ajustați pentru asemănări în caracterele nepotrivite */ N_simi = 0 ; if ( minv > Num_com ) { pentru ( i = 0 ; i < ying_length ; 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 ]]; yang_flag [ j ] = '2' ; rupe ; } } } } } } Num_sim = (( dublu ) N_simi ) / 10.0 + Num_com ; /* Calculul greutății principale. */ greutate = Num_sim / (( dublu ) ying_length ) + Num_sim / (( dublu ) yang_length ) + (( dublu ) ( Num_com - N_trans )) / (( dublu ) Num_com ); greutate = greutate / 3,0 ; /* Continuați să creșteți greutatea dacă șirurile sunt similare */ dacă ( greutate > 0,7 ) { /* Ajustați pentru a avea până la primele 4 caractere comune */ j = ( minv >= 4 ) ? 4 : minv ; pentru ( i = 0 ;(( i < j ) && ( ying_hold [ i ] == yang_hold [ i ]) && ( NOTNUM ( ying_hold [ i ]))); i ++ ); dacă ( i ) greutate += i * 0,1 * ( 1,0 - greutate ); /* Ajustați opțional pentru șiruri lungi. */ /* După ce sunt de acord caracterele de început, cel puțin încă două trebuie să fie de acord, iar caracterele de acord trebuie să fie > .5 din caracterele rămase. */ if (( ! ind_c [ 0 ]) && ( minv > 4 ) && ( Num_com > i + 1 ) && ( 2 * Num_com >= minv + i )) if ( NOTNUM ( ying_hold [ 0 ])) greutate += ( dublu ) ( 1,0 - greutate ) * (( dublu ) ( Num_com - i -1 ) / (( dublu ) ( ying_length + yang_length - i * 2 + 2 ))); } întoarcere ( greutate ); } /* strcmp95 */ Implementarea algoritmului în Delphi [5] funcţia JaroWinkler ( prmT1 , prmT2 : String ; p : Double = 0,1 ) : Double ; Var ecartMax , l1 , l2 , compteMatching , compteTransposition , longueurPrefix , i , j : integer ; c1 , c2 , t1Match , t2Match : șir ; b1 , b2 : tablou de boolean ; distantaJaro : Dublu ; label endfor , exitfor2 ; function FindMatches ( prmTextInitial : string ; b1 : array of Boolean ) : string ; var i : întreg ; res : șir _ begin // Calcule le nombre de caractères qui match for i := 1 to Length ( prmTextInitial ) do begin if b1 [ i ] then //prmTextMatche[i]='_' then begin res := res + prmTextInitial [ i ] ; sfârşitul ; sfârşitul ; FindMatch-uri := res ; sfârşitul ; începe ecartMax := rotund ( Max ( Lungime ( prmT1 ) , Lungime ( prmT2 )) / 2 ) - 1 ; if (( prmT1 = '' ) sau ( prmT2 = '' )) atunci începe JaroWinkler := 0 ; ieșire ; sfârşitul ; contMatching := 0 ; compteTransposition := 0 ; l1 := Lungime ( prmT1 ) ; l2 := Lungime ( prmT2 ) ; lungimea stabilită ( b1 , l1 + 1 ) ; Setlength ( b2 , l2 + 1 ) ; for i := 0 to l1 do begin b1 [ i ] := false ; sfârşitul ; for i := 0 to l2 do begin b2 [ i ] := false ; sfârşitul ; pentru i := 1 la l1 nu începe c1 := prmT1 [ i ] ; dacă ( i <= l2 ) atunci c2 := prmT2 [ i ] else c2 := '' ; pentru j := Max ( i - ecartMax , 1 ) la Min ( i + ecartMax , l2 ) nu începe c2 := prmT2 [ j ] ; if c1 = c2 then //compteMatching avec transposition begin b1 [ i ] := true ; b2 [ j ] := adevărat ; //Le caractère a été matché, il n'est plus disponible Inc ( compteMatching ) ; rupe ; sfârşitul ; sfârşitul ; sfârşitul ; if ( compteMatching = 0 ) atunci începe JaroWinkler := 0 ; ieșire ; sfârşitul ; //Dans les caractères matchés, compte ceux qui ne matchent pas exactement t1Matche := TrouverMatches ( prmT1 , b1 ) ; t2Matche := TrouverMatches ( prmT2 , b2 ) ; if t1Matche <> t2Matche then begin for i := 1 to length ( t1Matche ) do begin if t1Matche [ i ] <> t2Matche [ i ] then Inc ( compteTransposition ) end ; end else begin compteTransposition := 0 ; sfârşitul ; distantaJaro := 1 / 3 * (( compteMatching / l1 ) + ( compteMatching / l2 ) + (( compteMatching - Int ( compteTransposition / 2 )) / compteMatching )) ; // Calcule la distance Winkler // Calcule le prefix sur les 4 premiers car aux max longueurPrefix := 0 ; pentru i := 1 la min ( 4 , min ( l1 , l2 )) nu începe c1 := prmT1 [ i ] ; c2 := prmT2 [ i ] ; if c1 = c2 then inc ( longueurPrefix ) else break ; sfârşitul ; //Valeur constante définie par l'algo JaroWinkler := distanceJaro + ( longueurPrefix * p * ( 1 - distanceJaro )) ; sfârşitul ; Implementarea algoritmului în PHP [6] <?php /* versiunea 1.2 Copyright (c) 2005-2010 Ivo Ugrina <ivo@iugrina.com> O bibliotecă PHP care implementează distanța Jaro și Jaro-Winkler , măsurând asemănarea dintre șiruri. Lucruri teoretice pot fi găsite în: Winkler, W.E. (1999). „Starea legăturii înregistrărilor și problemele actuale de cercetare”. Divizia Statistica Venituri, Serviciul Fiscal Intern Publicația R99/04. http://www.census.gov/srd/papers/pdf/rr99-04.pdf. Acest program este software gratuit; îl puteți redistribui și/sau modifica în conformitate cu termenii Licenței Publice Generale GNU publicate de Free Software Foundation; fie versiunea 3 a Licenței, fie (la alegerea dvs.) orice versiune ulterioară. Acest program este distribuit în speranța că va fi util, dar FĂRĂ NICIO GARANȚIE; fără nici măcar garanția implicită de VANTABILITATE sau ADECVARE PENTRU UN ANUMIT SCOP. Consultați Licența publică generală GNU pentru mai multe detalii. Ar fi trebuit să primiți o copie a licenței publice generale GNU împreună cu acest program. Dacă nu, consultați <http://www.gnu.org/licenses/>. === Îi mulțumim lui Pierre Senellart <pierre@senellart.com> pentru că a găsit o mică eroare în cod. */ funcția getCommonCharacters ( $ șir1 , $șir2 , $allowedDistance ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); $temp_șir2 = $șir2 ; $commonCharacters = '' ; pentru ( $i = 0 ; $i < $str1_len ; $i ++ ){ $noMatch = Adevărat ; // compară dacă caracterul se potrivește în interiorul dat allowDistance // și dacă îl adaugă la commonCharacters pentru ( $j = max ( 0 , $i - $allowedDistance ); $noMatch && $j < min ( $i + $allowedDistance + 1 , $str2_len ); $j ++ ){ if ( $temp_string2 [ $j ] == $string1 [ $i ] ){ $noMatch = False ; $commonCharacters .= $ șir1 [ $i ]; $temp_string2 [ $j ] = '' ; } } } returnează $commonCharacters ; } funcția Jaro ( $ șir1 , $șir2 ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); // distanta teoretica $distanta = etaj ( min ( $str1_len , $str2_len ) / 2.0 ); // obține caractere comune $commons1 = getCommonCharacters ( $ șir1 , $șir2 , $distanță ); $commons2 = getCommonCharacters ( $șir2 , $ șir1 , $distanță ); if ( ( $commons1_len = strlen ( $commons1 )) == 0 ) return 0 ; if ( ( $commons2_len = strlen ( $commons2 )) == 0 ) return 0 ; // calculează transpoziții $transpoziții = 0 ; $upperBound = min ( $commons1_len , $commons2_len ); for ( $i = 0 ; $i < $UpperBound ; $i ++ ){ if ( $comun1 [ $i ] != $commons2 [ $i ] ) $transpozitii ++ ; } $transpuneri /= 2.0 ; // returnează returnarea distanței Jaro ( $commons1_len / ( $str1_len ) + $commons2_len / ( $str2_len ) + ( $commons1_len - $transpoziții ) / ( $commons1_len )) / 3.0 ; } funcția getPrefixLength ( $ șir1 , $șir2 , $MINPREFIXLENGTH = 4 ){ $n = min ( matrice ( $MINPREFIXLENGTH , strlen ( $ șir1 ), strlen ( $ șir2 ) ) ); pentru ( $i = 0 ; $i < $n ; $i ++ ){ if ( $șir1 [ $i ] != $șir2 [ $i ] ){ // returnează indicele primei apariții a diferitelor caractere returnează $i ; } } // primele n caractere sunt aceleași returnează $n ; } funcția JaroWinkler ( $ șir1 , $șir2 , $PREFIXSCALE = 0,1 ){ $JaroDistanța = Jaro ( $ șir1 , $șir2 ); $prefixLength = getPrefixLength ( $ șir1 , $șir2 ); returnează $JaroDistance + $prefixLength * $PREFIXSCALE * ( 1.0 - $JaroDistance ); } ?>

Implementarea algoritmului in C#
Implementarea algoritmului în Java

Note

↑ Înregistrați algoritmi de legătură în F# - Extensii la distanța Jaro-Winkler (Partea 3) . Preluat la 21 martie 2017. Arhivat din original la 31 decembrie 2019. (nedefinit)
↑ Algoritmi aproximativi de comparare a textului, partea a 2-a . Preluat la 21 martie 2017. Arhivat din original la 22 martie 2017. (nedefinit)
↑ Referință pentru pachete și tipuri de baze de date PL/SQL . Preluat la 21 martie 2017. Arhivat din original la 12 ianuarie 2017. (nedefinit)
↑ Copie arhivată (link nu este disponibil) . Consultat la 23 februarie 2011. Arhivat din original pe 23 februarie 2011. (nedefinit)
↑ Distance de jaro-winkler Arhivat 22 martie 2017 la Wayback Machine (FR)
↑ [1 ]

Link -uri

Cohen, WW O comparație a valorilor distanței șirurilor pentru sarcinile de potrivire a numelor // KDD Workshop on Data Cleaning and Object Consolidation : journal. - 2003. - Vol. 3 . - P. 73-8 .
Jaro, MA Progrese în metodologia de conectare a înregistrărilor aplicată la recensământul din 1985 din Tampa Florida // Jurnalul Asociației Americane de Statistică : jurnal. - 1989. - Vol. 84 , nr. 406 . - P. 414-420 . - doi : 10.1080/01621459.1989.10478785 .
Jaro, MA Legătura probabilistică a fișierelor mari de date de sănătate publică (engleză) // Statistics in Medicine: journal. - 1995. - Vol. 14 , nr. 5-7 . - P. 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 // Proceedings of the Section on Survey Research Methods : journal. - Asociaţia Americană de Statistică, 1990. - P. 354-359 . Arhivat din original pe 13 februarie 2015.
William E. Winkler. Prezentare generală a legăturii înregistrărilor și direcțiilor curente de cercetare // Seria de rapoarte de cercetare, RRS : jurnal. — 2006.

	M	A	R	T	H	A
M	unu	0	0	0	0	0
A	0	unu	0	0	0	0
R	0	0	unu	0	0	0
H	0	0	0	0	unu	0
T	0	0	0	unu	0	0
A	0	0	0	0	0	unu

	D	eu	X	O	N
D	unu	0	0	0	0
eu	0	unu	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	unu	0
N	0	0	0	0	unu
X	0	0	0	0	0

	M	A	R	T	H	A
M	unu	0	0	0	0	0
A	0	unu	0	0	0	0
R	0	0	unu	0	0	0
H	0	0	0	0	unu	0
T	0	0	0	unu	0	0
A	0	0	0	0	0	unu

	D	eu	X	O	N
D	unu	0	0	0	0
eu	0	unu	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	unu	0
N	0	0	0	0	unu
X	0	0	0	0	0

	M	A	R	T	H	A
M	unu	0	0	0	0	0
A	0	unu	0	0	0	0
R	0	0	unu	0	0	0
H	0	0	0	0	unu	0
T	0	0	0	unu	0	0
A	0	0	0	0	0	unu

	D	eu	X	O	N
D	unu	0	0	0	0
eu	0	unu	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	unu	0
N	0	0	0	0	unu
X	0	0	0	0	0