Jaro-Winkler likhet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 december 2019; kontroller kräver 9 redigeringar .

Inom området datavetenskap och statistik är Jaro-Winkler- likhet ett mått på stränglikhet för att mäta avståndet mellan två teckensekvenser. Detta är en variant som föreslås av William E. Winkler 1999 baserad på Jaro-distansen (1989, Matthew A. Jaro). Informellt sett är Jaro-avståndet mellan två ord det minsta antalet enkaraktärstransformationer som krävs för att ändra ett ord till ett annat.

Ju mindre Jaro-Winkler-avståndet är för två strängar, desto mer lika dessa strängar är varandra. Resultatet är normaliserat så det betyder ingen likhet och betyder exakt matchning. Jaro-Winkler likheten är . $d_{w}$ $d_{w}=0$ $d_{w}=1$ ${\displaystyle 1-d_{w))$

Definition

Avstånd Jaro

Jaros avstånd mellan två givna strängar och detta: $d_{j}$ $s_{1}$ $s_{2}$

d_{j}=\left\{{\begin{array}{ll}0&{\text{när }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {mt}{m}}\right)&{\text{annars }} \end{array}}\right.

Var:

$|s_{i}|$ — stränglängd ; $si}$
$m$ — Antal matchande tecken (se nedan).
$t$ - hälften av antalet införlivanden (se nedan).

Två tecken från respektive anses matcha endast om de är lika och inte längre än . $s_{1}$ $s_{2}$ $\left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2))\right\rfloor -1$

Varje tecken i strängen jämförs med alla dess motsvarande tecken i . Antalet matchande (men olika ordningstecken), som är delbart med 2, bestämmer antalet transponeringar . Till exempel, när man jämför ordet CRATE med ordet TRACE, är endast 'R' 'A' och 'E' matchande tecken, dvs m=3. Även om 'C' och 'T' visas på båda raderna, är de längre än 1, det vill säga floor(5/2)-1=1. Därför är t=0 . När man jämför DwAyNE med DuANE är motsvarande bokstäver redan i samma DANE-ordning, så inga permutationer behövs. $s_{1}$ $s_{2}$

Jaro-Winkler avstånd

Jaro-Winkler-avståndet använder en skalningsfaktor , som ger gynnsammare betyg till strängar som matchar varandra från start upp till en viss längd , kallat prefix. Givet två strängar och . Deras avstånd Jaro-Winkler är: $sid$ $\aln$ $s_{1}$ $s_{2}$ $d_{w}$

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

var:

$d_{j}$ är Jaro-avståndet för rader och $s_{1}$ $s_{2}$
$\aln$ - längden på det gemensamma prefixet från början av strängen till högst 4 tecken
$sid$ är en konstant skalningsfaktor som används för att justera uppskattningen uppåt för att upptäcka förekomsten av vanliga prefix. får inte överstiga 0,25, annars kan avståndet bli större än 1. Standardvärdet för denna konstant i Winklers arbete är: . $sid$ $p=0.1$

Medan Jaro–Winkler-avståndet ofta hänvisas till som ett avståndsmått , är det inte ett mått i ordets matematiska betydelse eftersom det inte lyder triangelojämlikheten . Jaro-Winkler-avståndet uppfyller inte heller axiomet som säger att [1] . $d(x,y)=0\leftrightarrow x=y$

I vissa implementeringar av Jaro-Winklers avståndsberäkningsalgoritm, läggs en prefixbonus till endast om de jämförda strängarna har ett Jaro-avstånd över den inställda "boost-tröskeln" . Tröskeln i Winklers implementering var 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{annars}}\end{array}}\right.

Exempel

Det bör noteras att Winklers C-kod skiljer sig på åtminstone två ställen från det publicerade arbetet om Jaro-Winkler-metriken. Den första är dess användning av errata-tabellen (adjwt), och den andra är några ytterligare villkor för långa strängar.

Exempel 1

Strängarna MARTHA och MARHTA är givna. Låt oss representera deras skärningspunkt i tabellform: $s_{1}$ $s_{2}$

	M	A	R	T	H	A
M	ett	0	0	0	0	0
A	0	ett	0	0	0	0
R	0	0	ett	0	0	0
H	0	0	0	0	ett	0
T	0	0	0	ett	0	0
A	0	0	0	0	0	ett

Här är det maximala avståndet 6/2 - 1 = 2. De gula cellerna i tabellen ovan indikerar ettor när tecknen är identiska (det finns en matchning), och nollor annars.

Det visar sig:

$m=6$
$|s_{1}|=6$
$|s_{2}|=6$
Det finns felaktiga tecken T/H och H/T, vilket resulterar i: $t={\frac {2}{2}}=1$

Avstånd Jaro:

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

För att hitta Jaro-Winkler-resultatet med standardvikten fortsätter vi att leta: $p=0.1$

\ell =3

På det här sättet:

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

Exempel 2

Strängarna DWAYNE och DUANE är givna. Det visar sig: $s_{1}$ $s_{2}$

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

Avstånd Jaro:

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

För att hitta Jaro-Winkler-resultatet med standardvikten fortsätter vi att leta: $p=0.1$

\ell =1

På det här sättet:

d_{w}=0.73(8)+(1\cdot 0.1(1-0.73(8)))=0.765

Exempel 3

Givna strängar DIXON och DICKSONX . Det visar sig: $s_{1}$ $s_{2}$

	D	jag	X	O	N
D	ett	0	0	0	0
jag	0	ett	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	ett	0
N	0	0	0	0	ett
X	0	0	0	0	0

Här är de fyllda cellerna det matchande fönstret för varje tecken. En enhet i en cell indikerar en matchning. Observera att de två x (X) inte anses vara en matchning eftersom de är utanför det tredje matchningsfönstret.

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

Avstånd Jaro:

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

För att hitta Jaro-Winkler-resultatet med standardvikten fortsätter vi att leta: $p=0.1$

\ell =2

På det här sättet:

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

Relationer med andra avståndsförändringsmått

Det finns andra populära mått på avståndsförändringar som beräknas med en annan uppsättning giltiga redigeringsoperationer. Till exempel,

Levenshtein-avståndet tillåter radering, infogning och ersättning av tecken;
Avståndet Damerau-Levenshtein tillåter infogning, radering, ersättning och permutation av två intilliggande tecken;
Den största vanliga efterföljden tillåter endast infogningar och borttagningar, inte ersättningar;
Hamming distans tillåter bara substitution, så det gäller bara strängar av samma längd.

Förändringen i avstånd definieras vanligtvis som ett parametrerbart mått som beräknas med hjälp av en viss uppsättning giltiga redigeringsoperationer, och varje operation tilldelas en kostnad (kanske oändlig). Detta är en ytterligare generalisering av genetiska sekvensanpassningsalgoritmer , såsom Smith-Waterman-algoritmen , som gör kostnaden för en operation beroende på var den tillämpas.

Praktisk tillämpning

Jaro-Winkler-algoritmen användes för att bearbeta resultaten av folkräkningen [2] .
Algoritmen för Jaro-Winkler-strängjämförelse är implementerad i Oracle DBMS [3] .

Implementeringar av algoritmen i olika programmeringsspråk

Implementering av algoritmen i C [4] * strcmp95 . c Version 2 */ /* Funktionen strcmp95 returnerar ett dubbelt precisionsvärde från 0,0 (total oenighet) till 1,0 (överensstämmelse tecken för tecken). Det returnerade värdet är ett mått på likheten mellan de två strängarna. */ /* Releasedatum: Jan. 26, 1994 */ /* Ändrad: 24 april 1994 Korrigerade bearbetningen av teckensträngarna med enkel längd. Författare: Denna funktion skrevs med hjälp av logiken från kod skriven av Bill Winkler, George McLaughlin och Matt Jaro med modifieringar av Maureen Lynch. Kommentar: Detta är den officiella strängjämföraren som ska användas för matchning under 1995 års testcensus. */ # include <ctype.h> # include <string.h> # define NOTNUM(c) ((c>57) || (c<48)) # define INRANGE(c) ((c>0) && (c<91)) # define MAX_VAR_SIZE 61 # define NULL60 " " dubbel strcmp95 ( char * ying , char * yang , long y_length , int * ind_c []) { /* Argument: ying och yang är pekare till de två strängarna som ska jämföras. Strängarna behöver inte vara NUL-terminerade strängar eftersom längden är passerad. y_length är längden på strängarna. ind_c är en array som används för att avgöra om vissa alternativ ska aktiveras. Ett värde som inte är noll indikerar att alternativet är avaktiverat. Alternativen är: ind_c[0] Öka sannolikheten för en matchning när antalet matchade tecken är stort. Det här alternativet tillåter lite mer tolerans när strängarna är stora. Det är inte ett lämpligt test när man jämför fält med fast längd som telefon- och personnummer. ind_c[1] Alla gemener konverteras till versaler innan jämförelsen. Om du inaktiverar den här funktionen betyder det att den gemena strängen "code" inte kommer att kännas igen som densamma som versalsträngen "CODE". Dessutom gäller avsnittet justering för liknande tecken endast för versaler. De föreslagna värdena är alla nollor för teckensträngar som namn. */ statisk int pass = 0 , adjwt [ 91 ][ 91 ]; statisk 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_flagga [ MAX_VAR_SIZE ]; dubbelvikt , Num_sim ; _ long minv , search_range , lowlim , ying_length , hilim , N_trans , Num_com , yang_length ; int yl1 , yi_st , N_simi ; registrera int i , j , k ; /* Initiera adjwt-arrayen vid det första anropet endast till funktionen. Adjwt-matrisen används för att ge delvis kredit för tecken som kan vara fel på grund av kända fonetiska eller teckenigenkänningsfel. Ett typiskt exempel är att matcha bokstaven "O" med siffran "0" */ if ( ! passera ) { passera ++ ; för ( i = 0 ; i < 91 ; i ++ ) för ( j = 0 ; j < 91 ; j ++ ) adjwt [ i ][ j ] = 0 ; för ( i = 0 ; i < 36 ; i ++ ) { adjwt [ sp [ i ][ 0 ]][ sp [ i ][ 1 ]] = 3 ; adjwt [ sp [ i ][ 1 ]][ sp [ i ][ 0 ]] = 3 ; } } /* Om endera strängen är tom - returnera - tillagd i version 2 */ if ( ! strncmp ( ying , NULL60 , y_length )) return ( 0.0 ); if ( ! strncmp ( yang , NULL60 , y_längd )) return ( 0.0 ); /* Identifiera strängarna som ska jämföras genom att ta bort alla inledande och efterföljande mellanslag. */ k = y_längd - 1 ; för ( j = 0 ;(( ying [ j ] == ' ' ) && ( j < k )); j ++ ); för ( i = k ;(( ying [ i ] == ' ' ) && ( i > 0 )); i -- ); ying_längd = i + 1 - j ; yi_st = j ; för ( j = 0 ;(( yang [ j ] == ' ' ) && ( j < k )); j ++ ); för ( i = k ;(( yang [ i ] == ' ' ) && ( i > 0 )); i -- ); yang_längd = 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 ( ying_length > yang_length ) { sökintervall = ying_längd ; minv = yang_längd ; } annat { sökintervall = yang_längd ; minv = ying_längd ; } /* Om någon av strängarna är tom - returnera */ /* if (!minv) return(0.0); borttagen i version 2 */ /* Tomma ut flaggorna */ ying_flagga [ 0 ] = ying_flagga [ 0 ] = 0 ; strncat ( ying_flag , NULL60 , search_range ); strncat ( yang_flagga , NULL60 , sökområde ); sökområde = ( sökområde / 2 ) - 1 ; if ( sökområde < 0 ) sökområde = 0 ; /* tillagd i version 2 */ /* Konvertera alla gemener till versaler. */ if ( ! ind_c [ 1 ]) { för ( i = 0 ; i < ying_längd ; i ++ ) if ( islower ( ying_hold [ i ])) ying_hold [ i ] -= 32 ; för ( j = 0 ; j < yang_längd ; j ++ ) if ( är lägre ( yang_håll [ j ])) yang_håll [ j ] -= 32 ; } /* Om du bara tittar inom sökintervallet, räkna och flagga de matchade paren. */ Num_com = 0 ; yll = yang_längd - 1 ; for ( i = 0 ; i < ying_length ; i ++ ) { lowlim = ( i >= sökområde ) ? i - sökområde : 0 ; hilim = (( i + sökområde ) <= yl1 ) ? ( i + sökområde ) : yl1 ; för ( j = lowlim ; j <= hilim ; j ++ ) { if (( yang_flag [ j ] != '1' ) && ( yang_hold [ j ] == ying_hold [ i ])) { yang_flag [ j ] = '1' ; ying_flag [ i ] = '1' ; Num_com ++ ; bryta ; } } } /* Om inga tecken är gemensamma - returnera */ if ( ! Num_com ) return ( 0.0 ); /* Räkna antalet transponeringar */ k = N_trans = 0 ; for ( i = 0 ; i < ying_length ; i ++ ) { if ( ying_flag [ i ] == '1' ) { för ( j = k ; j < yang_längd ; j ++ ) { if ( yang_flagga [ j ] == '1' ) { k = j + 1 ; bryta ; } } if ( ying_hold [ i ] != yang_hold [ j ]) N_trans ++ ; } } N_trans = N_trans / 2 ; /* justera för likheter i icke-matchade tecken */ N_simi = 0 ; if ( minv > Num_com ) { for ( 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 ] == ' ' && INNRANGE ( 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' ; bryta ; } } } } } } Num_sim = (( dubbel ) N_simi ) / 10.0 + Num_com ; /* Huvudviktsberäkning. */ vikt = Num_sim / (( dubbel ) ying_längd ) + Num_sim / (( dubbel ) yang_längd ) + (( double ) ( Num_com - N_trans )) / (( double ) Num_com ); vikt = vikt / 3,0 ; /* Fortsätt att öka vikten om strängarna är lika */ if ( vikt > 0,7 ) { /* Justera för att ha upp till de fyra första tecknen gemensamma */ j = ( minv >= 4 ) ? 4 : minv ; för ( i = 0 ;(( i < j ) && ( ying_hold [ i ] == yang_hold [ i ]) && ( NOTNUM ( ying_hold [ i ]))); i ++ ); om ( i ) vikt += i * 0,1 * ( 1,0 - vikt ); /* Valfritt justera för långa strängar. */ /* Efter att ha kommit överens om inledande tecken måste minst två till överensstämma och de överensstämmande tecknen måste vara > .5 av de återstående tecknen. */ if (( ! ind_c [ 0 ]) && ( minv > 4 ) && ( Num_com > i + 1 ) && ( 2 * Num_com >= minv + i )) if ( NOTNUM ( ying_hold [ 0 ])) vikt += ( dubbel ) ( 1,0 - vikt ) * (( double ) ( Num_com - i -1 ) / (( double ) ( ying_length + yang_length - i * 2 + 2 ))); } retur ( vikt ); } /* strcmp95 */ Implementering av algoritmen i Delphi [5] function JaroWinkler ( prmT1 , prmT2 : String ; p : Double = 0,1 ) : Double ; Var ecartMax , l1 , l2 , compteMatching , compteTransposition , longueurPrefix , i , j : heltal ; c1 , c2 , t1Match , t2Match : sträng ; b1 , b2 : array av Boolean ; avstånd Jaro : Dubbel ; etikett endfor , exitfor2 ; function TrouverMatches ( prmTextInitial : sträng ; b1 : array av Boolean ) : sträng ; var i : heltal ; res : sträng _ börja // Beräkna le nombre de caractères qui match for i := 1 till Length ( prmTextInitial ) börjar om b1 [ i ] sedan //prmTextMatche[i]='_' sedan börjar res : = res + prmTextInitial [ i ] ; slut ; slut ; TrouverMatches := res ; slut ; börja ecartMax := rund ( Max ( Längd ( prmT1 ) , Längd ( prmT2 )) / 2 ) - 1 ; om (( prmT1 = '' ) eller ( prmT2 = '' )) börja då JaroWinkler := 0 ; avsluta ; slut ; compteMatching := 0 ; compteTransposition := 0 ; l1 := Längd ( prmT1 ) ; l2 := Längd ( prmT2 ) ; setlängd ( b1 , 11 + 1 ) ; Setlängd ( b2 , l2 + 1 ) ; för i := 0 till l1 börjar b1 [ i ] : = falskt ; slut ; för i := 0 till l2 börjar b2 [ i ] : = falskt ; slut ; för i := 1 till l1 börjar c1 : = prmT1 [ i ] ; if ( i <= l2 ) då c2 := prmT2 [ i ] annars c2 := '' ; för j := Max ( i - ecartMax , 1 ) till Min ( i + ecartMax , l2 ) börjar c2 : = prmT2 [ j ] ; om c1 = c2 börjar // compteMatching avec transponering b1 [ i ] := sant ; b2 [ j ] := sant ; //Le caractère a été matché, il n'est plus disponible Inc ( compteMatching ) ; bryta ; slut ; slut ; slut ; if ( compteMatching = 0 ) börja sedan JaroWinkler := 0 ; avsluta ; slut ; //Dans les caractères matchés, compte ceux qui ne matchent pas exactement t1Matche := TrouverMatches ( prmT1 , b1 ) ; t2Matche := TrouverMatches ( prmT2 , b2 ) ; om t1Matche <> t2Matche börjar då för i := 1 till längd ( t1Match ) börjar om t1 Match [ i ] <> t2 Match [ i ] då Inc ( compteTransposition ) slutar ; slut annars börja compteTransposition := 0 ; slut ; distanceJaro := 1 / 3 * (( compteMatching / l1 ) + ( compteMatching / l2 ) + (( compteMatching - Int ( compteTransposition / 2 )) / compteMatching )) ; // Beräkna la avstånd Winkler // Beräkna le prefix sur les 4 premiers car aux max longueurPrefix := 0 ; för i := 1 till min ( 4 , min ( l1 , 12 ) ) börjar c1 := prmT1 [ i ] ; c2 := prmT2 [ i ] ; om c1 = c2 så inc ( longueurPrefix ) annars bryta ; slut ; //Valeur constante définie par l'algo JaroWinkler := distanceJaro + ( longueurPrefix * p * ( 1 - distanceJaro )) ; slut ; Implementering av algoritmen i PHP [6] <?php /* version 1.2 Copyright (c) 2005-2010 Ivo Ugrina <[email protected]> Ett PHP-bibliotek som implementerar Jaro och Jaro-Winkler- avstånd, som mäter likheter mellan strängar. Teoretiska saker finns i: Winkler, W.E. (1999). "Tillståndet för rekordkoppling och aktuella forskningsproblem". Statistics of Income Division, Internal Revenue Service Publication R99/04. http://www.census.gov/srd/papers/pdf/rr99-04.pdf. Detta program är fri programvara; du kan omdistribuera den och/eller modifiera den enligt villkoren i GNU General Public License som publicerats av Free Software Foundation; antingen version 3 av licensen eller (efter eget val) någon senare version. Detta program distribueras i hopp om att det ska vara användbart, men UTAN NÅGON GARANTI; utan ens den underförstådda garantin för SÄLJBARHET eller LÄMPLIGHET FÖR ETT SÄRSKILT SYFTE. Se GNU General Public License för mer information. Du borde ha fått en kopia av GNU General Public License tillsammans med detta program. Om inte, se <http://www.gnu.org/licenses/>. === Ett stort tack går ut till Pierre Senellart <[email protected]> för att du hittade en liten bugg i koden. */ funktion getCommonCharacters ( $string1 , $string2 , $allowedDistance ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); $temp_string2 = $string2 ; $commonCharacters = '' ; för ( $i = 0 ; $i < $str1_len ; $i ++ ){ $noMatch = Sant ; // jämför om char stämmer överens med given allowDistance // och om den läggs till commonCharacters för ( $j = max ( 0 , $i - $allowedDistance ); $noMatch && $j < min ( $i + $allowedDistance + 1 , $str2_len ); $j ++ ){ if ( $temp_string2 [ $j ] == $string1 [ $i ] ){ $noMatch = Falskt ; $commonCharacters .= $string1 [ $i ]; $temp_string2 [ $j ] = '' ; } } } returnera $commonCharacters ; } function Jaro ( $string1 , $string2 ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); // teoretiskt avstånd $distans = golv ( min ( $str1_len , $str2_len ) / 2.0 ); // få vanliga tecken $commons1 = getCommonCharacters ( $string1 , $string2 , $distance ); $commons2 = getCommonCharacters ( $string2 , $string1 , $distance ); if ( ( $commons1_len = strlen ( $commons1 )) == 0 ) returnera 0 ; if ( ( $commons2_len = strlen ( $commons2 )) == 0 ) returnera 0 ; // beräkna transpositioner $transpositioner = 0 ; $upperBound = min ( $commons1_len , $commons2_len ); för ( $i = 0 ; $i < $upperBound ; $i ++ ){ if ( $commons1 [ $i ] != $commons2 [ $i ] ) $transpositioner ++ ; } $transpositioner /= 2.0 ; // returnera Jaro-avståndsreturen ( $commons1_len / ( $ str1_len ) + $commons2_len / ( $str2_len ) + ( $commons1_len - $transpositioner ) / ( $commons1_len )) / 3.0 ; } function getPrefixLength ( $string1 , $string2 , $MINPREFIXLENGTH = 4 ){ $n = min ( array ( $MINPREFIXLENGTH , strlen ( $string1 ), strlen ( $string2 ) ) ); for ( $i = 0 ; $i < $n ; $i ++ ){ if ( $string1 [ $i ] != $string2 [ $i ] ){ // returnera index för första förekomsten av olika tecken returnera $i ; } } // första n tecknen är samma return $n ; } funktion JaroWinkler ( $string1 , $string2 , $PREFIXSCALE = 0.1 ){ $JaroDistance = Jaro ( $string1 , $string2 ); $prefixLength = getPrefixLength ( $string1 , $string2 ); return $JaroDistance + $prefixLength * $PREFIXSCALE * ( 1.0 - $JaroDistance ); } ?>

Anteckningar

↑ Spela in länkningsalgoritmer i F# - Förlängningar till Jaro-Winkler-avstånd (del 3) . Hämtad 21 mars 2017. Arkiverad från originalet 31 december 2019. (obestämd)
↑ Ungefärliga algoritmer för textjämförelse, del 2 . Hämtad 21 mars 2017. Arkiverad från originalet 22 mars 2017. (obestämd)
↑ Referens för PL/SQL-databaspaket och -typer . Hämtad 21 mars 2017. Arkiverad från originalet 12 januari 2017. (obestämd)
↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 23 februari 2011. Arkiverad från originalet 23 februari 2011. (obestämd)
↑ Distance de jaro-winkler Arkiverad 22 mars 2017 på Wayback Machine (FR)
↑ [1 ]

Länkar

Cohen, WW En jämförelse av strängavståndsmått för namnmatchande uppgifter // KDD Workshop on Data Cleaning and Object Consolidation : journal. - 2003. - Vol. 3 . - S. 73-8 .
Jaro, MA Framsteg inom rekordlänkningsmetodik som tillämpas på 1985 års folkräkning i Tampa Florida // Journal of the American Statistical Association : tidskrift. - 1989. - Vol. 84 , nr. 406 . - s. 414-420 . - doi : 10.1080/01621459.1989.10478785 .
Jaro, MA Probabilistisk koppling av stor folkhälsodatafil (engelska) // Statistics in Medicine: journal. - 1995. - Vol. 14 , nr. 5-7 . - s. 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. - American Statistical Association, 1990. - P. 354-359 . Arkiverad från originalet den 13 februari 2015.
William E. Winkler. Översikt över postkopplingar och aktuella forskningsriktningar // Research Report Series, RRS: tidskrift. – 2006.

	M	A	R	T	H	A
M	ett	0	0	0	0	0
A	0	ett	0	0	0	0
R	0	0	ett	0	0	0
H	0	0	0	0	ett	0
T	0	0	0	ett	0	0
A	0	0	0	0	0	ett

	D	jag	X	O	N
D	ett	0	0	0	0
jag	0	ett	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	ett	0
N	0	0	0	0	ett
X	0	0	0	0	0

	M	A	R	T	H	A
M	ett	0	0	0	0	0
A	0	ett	0	0	0	0
R	0	0	ett	0	0	0
H	0	0	0	0	ett	0
T	0	0	0	ett	0	0
A	0	0	0	0	0	ett

	D	jag	X	O	N
D	ett	0	0	0	0
jag	0	ett	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	ett	0
N	0	0	0	0	ett
X	0	0	0	0	0

	M	A	R	T	H	A
M	ett	0	0	0	0	0
A	0	ett	0	0	0	0
R	0	0	ett	0	0	0
H	0	0	0	0	ett	0
T	0	0	0	ett	0	0
A	0	0	0	0	0	ett

	D	jag	X	O	N
D	ett	0	0	0	0
jag	0	ett	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	ett	0
N	0	0	0	0	ett
X	0	0	0	0	0