Jaro-Winkler lighed

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. december 2019; checks kræver 9 redigeringer .

Inden for datalogi og statistik er Jaro-Winkler- lighed et mål for strenglighed for at måle afstanden mellem to sekvenser af tegn. Dette er en variant foreslået af William E. Winkler i 1999 baseret på Jaro-afstanden (1989, Matthew A. Jaro). Uformelt er Jaro-afstanden mellem to ord det mindste antal enkelttegnstransformationer, der kræves for at ændre et ord til et andet.

Jo mindre Jaro-Winkler-afstanden er for to strenge, jo mere ligner disse strenge hinanden. Resultatet er normaliseret, så det betyder ingen lighed og betyder nøjagtig match. Jaro-Winkler ligheden er . $d_{w}$ $d_{w}=0$ $d_{w}=1$ ${\displaystyle 1-d_{w))$

Definition

Afstand Jaro

Jaros afstand mellem to givne strenge og dette: $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{ellers }} \end{array}}\right.

Hvor:

$|s_{i}|$ — strenglængde ; $s_{i}$
$m$ — antal matchende tegn (se nedenfor);
$t$ - halvdelen af antallet af transponeringer (se nedenfor).

To karakterer fra henholdsvis og anses kun for at matche , hvis de er ens og ikke længere end . $s_{1}$ $s_{2}$ $\venstre\lgulv {\frac {\max(|s_{1}|,|s_{2}|)}{2))\højre\rgulv -1$

Hvert tegn i strengen sammenlignes med alle dets tilsvarende tegn i . Antallet af matchende (men forskellige ordinære) tegn, som er deleligt med 2, bestemmer antallet af transpositioner . For eksempel, når man sammenligner ordet CRATE med ordet TRACE, er kun 'R' 'A' og 'E' matchende tegn, dvs. m=3. Selvom 'C' og 'T' vises på begge linjer, er de længere end 1, det vil sige floor(5/2)-1=1. Derfor er t=0. Ved sammenligning af DwAyNE med DuANE er de tilsvarende bogstaver allerede i samme DANE-rækkefølge, så der er ingen behov for permutationer. $s_{1}$ $s_{2}$

Jaro-Winkler distance

Jaro-Winkler-afstanden bruger en skaleringsfaktor , som giver mere gunstige vurderinger til strenge, der matcher hinanden fra starten op til en vis længde , kaldet præfikset. Givet to strenge og . Deres afstand mellem Jaro og Winkler er: $s$ $\ell$ $s_{1}$ $s_{2}$ $d_{w}$

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

hvor:

$d_{j}$ er Jaro-afstanden for rækker og $s_{1}$ $s_{2}$
$\ell$ - længden af det fælles præfiks fra begyndelsen af strengen til maksimalt 4 tegn
$s$ er en konstant skaleringsfaktor, der bruges til at justere estimatet opad for at detektere tilstedeværelsen af almindelige præfikser. må ikke overstige 0,25, ellers kan afstanden blive større end 1. Standardværdien af denne konstant i Winklers arbejde er :. $s$ $p=0.1$

Mens afstanden Jaro-Winkler ofte omtales som en afstandsmetrik , er den ikke en metrik i ordets matematiske betydning, fordi den ikke adlyder trekantens ulighed . Også Jaro-Winkler-afstanden opfylder ikke aksiomet, som siger, at [1] . $d(x,y)=0\leftrightarrow x=y$

I nogle implementeringer af Jaro-Winkler-afstandsberegningsalgoritmen tilføjes en præfiksbonus kun, hvis de sammenlignede strenge har en Jaro-afstand over den indstillede "boost-tærskel" . Tærsklen 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{ellers}}\end{array}}\right.

Eksempler

Det skal bemærkes, at Winklers C-kode adskiller sig mindst to steder fra det offentliggjorte arbejde om Jaro-Winkler-metrikken. Den første er dens brug af errata-tabellen (adjwt), og den anden er nogle yderligere betingelser for lange strenge.

Eksempel 1

Strengene MARTHA og MARHTA er givet. Lad os repræsentere deres skæringspunkt i tabelform: $s_{1}$ $s_{2}$

	M	EN	R	T	H	EN
M	en	0	0	0	0	0
EN	0	en	0	0	0	0
R	0	0	en	0	0	0
H	0	0	0	0	en	0
T	0	0	0	en	0	0
EN	0	0	0	0	0	en

Her er den maksimale afstand 6/2 - 1 = 2. De gule celler i ovenstående tabel angiver en, når tegnene er identiske (der er et match), og nuller ellers.

Det viser sig:

$m=6$
$|s_{1}|=6$
$|s_{2}|=6$
Der er uoverensstemmende tegn T/H og H/T, hvilket resulterer i: $t={\frac {2}{2}}=1$

Afstand Jaro:

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

For at finde Jaro-Winkler-resultatet ved hjælp af standardvægten fortsætter vi med at lede: $p=0.1$

\ell =3

På denne måde:

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

Eksempel 2

Strengene DWAYNE og DUANE er givet. Det viser sig: $s_{1}$ $s_{2}$

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

Afstand Jaro:

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

For at finde Jaro-Winkler-resultatet ved hjælp af standardvægten fortsætter vi med at lede: $p=0.1$

\ell =1

På denne måde:

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

Eksempel 3

Givet strenge DIXON og DICKSONX . Det viser sig: $s_{1}$ $s_{2}$

	D	jeg	x	O	N
D	en	0	0	0	0
jeg	0	en	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	en	0
N	0	0	0	0	en
x	0	0	0	0	0

Her er de udfyldte celler det matchende vindue for hver karakter. En enhed i en celle angiver et match. Bemærk, at de to x'er (X'er) ikke betragtes som et match, fordi de er uden for det tredje matchvindue.

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

Afstand Jaro:

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

For at finde Jaro-Winkler-resultatet ved hjælp af standardvægten fortsætter vi med at lede: $p=0.1$

\ell =2

På denne måde:

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

Relationer med andre afstandsændringsmetrikker

Der er andre populære mål for afstandsændring, der beregnes ved hjælp af et andet sæt gyldige redigeringsoperationer. For eksempel,

Levenshtein-afstanden tillader sletning, indsættelse og udskiftning af tegn;
Damerau-Levenshtein-afstanden tillader indsættelse, sletning, udskiftning og permutation af to tilstødende tegn;
Den største fælles efterfølger tillader kun indsættelser og sletninger, ikke erstatninger;
Hammerafstand tillader kun udskiftning, så det gælder kun strenge af samme længde.

Ændringen i afstand er normalt defineret som en parameter, der kan indstilles, beregnet ved hjælp af et bestemt sæt af gyldige redigeringsoperationer, og hver operation tildeles en omkostning (måske uendelig). Dette er en yderligere generalisering af genetiske sekvensjusteringsalgoritmer , såsom Smith-Waterman-algoritmen , der gør omkostningerne ved en operation afhængig af, hvor den anvendes.

Praktisk anvendelse

Jaro-Winkler-algoritmen blev brugt til at behandle resultaterne af folketællingen [2] .
Jaro-Winkler strengsammenligningsalgoritmen er implementeret i Oracle DBMS [3] .

Implementeringer af algoritmen i forskellige programmeringssprog

Implementering af algoritmen i C [4] * strcmp95 . c Version 2 */ /* Strcmp95-funktionen returnerer en dobbelt præcisionsværdi fra 0,0 (total uenighed) til 1,0 (tegn-for-tegn-aftale). Den returnerede værdi er et mål for ligheden mellem de to strenge. */ /* Udgivelsesdato: Jan. 26, 1994 */ /* Ændret: 24. april 1994 Rettede behandlingen af enkeltlængde tegnstrenge. Forfattere: Denne funktion blev skrevet ved hjælp af logikken fra kode skrevet af Bill Winkler, George McLaughlin og Matt Jaro med modifikationer af Maureen Lynch. Kommentar: Dette er den officielle strengkomparator, der skal bruges til matchning under 1995 Test Census. */ # 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 " " double strcmp95 ( char * ying , char * yang , long y_length , int * ind_c []) { /* Argumenter: ying og yang er pejlemærker til de 2 strenge, der skal sammenlignes. Strengene behøver ikke være NUL-terminerede strenge, fordi længden er passeret. y_length er længden af strengene. ind_c er et array, der bruges til at bestemme, om visse indstillinger skal aktiveres. En værdi, der ikke er nul, angiver, at indstillingen er deaktiveret. Indstillingerne er: ind_c[0] Forøg sandsynligheden for et match, når antallet af matchede tegn er stort. Denne mulighed giver mulighed for lidt mere tolerance, når strengene er store. Det er ikke en passende test, når man sammenligner felter med fast længde som telefon- og personnumre. ind_c[1] Alle små bogstaver konverteres til store bogstaver før sammenligningen. Deaktivering af denne funktion betyder, at den lille streng "kode" ikke vil blive genkendt som den samme som den store streng "CODE". Desuden gælder justeringen for lignende tegn kun for store bogstaver. De foreslåede værdier er alle nuller for tegnstrenge såsom navne. */ 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_flag [ MAX_VAR_SIZE ]; dobbeltvægt , Num_sim ; _ long minv , search_range , lowlim , ying_length , hilim , N_trans , Num_com , yang_length ; int yl1 , yi_st , N_simi ; register int i , j , k ; /* Initialiser kun adjwt-arrayet ved det første kald til funktionen. Adjwt-arrayet bruges til at give delvis kredit for tegn, der kan være fejl på grund af kendte fonetiske eller tegngenkendelsesfejl. Et typisk eksempel er at matche bogstavet "O" med tallet "0" */ if ( ! bestå ) { bestå ++ ; for ( i = 0 ; i < 91 ; i ++ ) for ( j = 0 ; j < 91 ; j ++ ) adjwt [ i ][ j ] = 0 ; for ( i = 0 ; i < 36 ; i ++ ) { adjwt [ sp [ i ][ 0 ]][ sp [ i ][ 1 ]] = 3 ; adjwt [ sp [ i ][ 1 ]][ sp [ i ][ 0 ]] = 3 ; } } /* Hvis en af strengene er tom - returner - tilføjet i version 2 */ if ( ! strncmp ( ying , NULL60 , y_længde )) return ( 0.0 ); if ( ! strncmp ( yang , NULL60 , y_længde )) return ( 0.0 ); /* Identificer strengene, der skal sammenlignes, ved at fjerne alle førende og efterfølgende mellemrum. */ k = y_længde - 1 ; for ( j = 0 ;(( ying [ j ] == ' ' ) && ( j < k )); j ++ ); for ( i = k ;(( ying [ i ] == ' ' ) && ( i > 0 )); i -- ); ying_længde = i + 1 - j ; yi_st = j ; for ( j = 0 ;(( yang [ j ] == ' ' ) && ( j < k )); j ++ ); for ( i = k ;(( yang [ i ] == ' ' ) && ( i > 0 )); i -- ); yang_længde = i + 1 - j ; ying_hold [ 0 ] = yang_hold [ 0 ] = 0 ; strncat ( ying_hold , & ying [ yi_st ], ying_length ); strncat ( yang_hold , & yang [ j ], yang_længde ); if ( ying_length > yang_length ) { søgeområde = ying_længde ; minv = yang_længde ; } andet { søgeområde = yang_længde ; minv = ying_længde ; } /* Hvis en af strengene er tom - returner */ /* if (!minv) return(0.0); fjernet i version 2 */ /* Tøm flagene */ ying_flag [ 0 ] = ying_flag [ 0 ] = 0 ; strncat ( ying_flag , NULL60 , søgeområde ); strncat ( yang_flag , NULL60 , søgeområde ); søgeområde = ( søgeområde / 2 ) - 1 ; if ( søgeområde < 0 ) søgeområde = 0 ; /* tilføjet i version 2 */ /* Konverter alle små bogstaver til store bogstaver. */ if ( ! ind_c [ 1 ]) { for ( i = 0 ; i < ying_længde ; i ++ ) if ( islower ( ying_hold [ i ])) ying_hold [ i ] -= 32 ; for ( j = 0 ; j < yang_længde ; j ++ ) if ( er lavere ( yang_hold [ j ])) yang_hold [ j ] -= 32 ; } /* Ser du kun inden for søgeområdet, tæl og marker de matchede par. */ Num_com = 0 ; yl1 = yang_længde - 1 ; for ( i = 0 ; i < ying_længde ; i ++ ) { lowlim = ( i >= søgeområde ) ? i - søgeområde : 0 ; hilim = (( i + søgeområde ) <= yl1 ) ? ( i + søgeområde ) : yl1 ; for ( 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 ++ ; bryde ; } } } /* Hvis ingen tegn til fælles - returner */ if ( ! Num_com ) return ( 0.0 ); /* Tæl antallet af transpositioner */ k = N_trans = 0 ; for ( i = 0 ; i < ying_længde ; i ++ ) { if ( ying_flag [ i ] == '1' ) { for ( j = k ; j < yang_længde ; j ++ ) { if ( yang_flag [ j ] == '1' ) { k = j + 1 ; bryde ; } } if ( ying_hold [ i ] != yang_hold [ j ]) N_trans ++ ; } } N_trans = N_trans / 2 ; /* juster for ligheder i ikke-matchede tegn */ N_simi = 0 ; if ( minv > Num_com ) { for ( i = 0 ; i < ying_længde ; 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' ; bryde ; } } } } } } Num_sim = (( dobbelt ) N_simi ) / 10.0 + Num_com ; /* Hovedvægtberegning. */ vægt = Antal_sim / (( dobbelt ) ying_længde ) + Antal_sim / (( dobbelt ) yang_længde ) + (( dobbelt ) ( Num_com - N_trans )) / (( double ) Num_com ); vægt = vægt / 3,0 ; /* Fortsæt med at øge vægten, hvis strengene ligner hinanden */ if ( vægt > 0,7 ) { /* Juster for at have op til de første 4 tegn til fælles */ j = ( minv >= 4 ) ? 4 : minv ; for ( i = 0 ;(( i < j ) && ( ying_hold [ i ] == yang_hold [ i ]) && ( NOTNUM ( ying_hold [ i ]))); i ++ ); hvis ( i ) vægt += i * 0,1 * ( 1,0 - vægt ); /* Juster eventuelt til lange strenge. */ /* Efter at have accepteret begyndende tegn, skal mindst to mere stemme overens, og de accepterende tegn skal være > .5 af de resterende tegn. */ if (( ! ind_c [ 0 ]) && ( minv > 4 ) && ( Num_com > i + 1 ) && ( 2 * Num_com >= minv + i )) if ( NOTNUM ( ying_hold [ 0 ])) vægt += ( dobbelt ) ( 1,0 - vægt ) * (( double ) ( Num_com - i -1 ) / (( double ) ( ying_length + yang_length - i * 2 + 2 ))); } retur ( vægt ); } /* strcmp95 */ Implementering af 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 : streng ; b1 , b2 : array af Boolean ; afstandJaro : Dobbelt ; mærke endfor , exitfor2 ; function TrouverMatches ( prmTextInitial : streng ; b1 : matrix af Boolean ) : streng ; var i : heltal ; res : streng _ start // Beregn le nombre de caractères qui match for i := 1 til Length ( prmTextInitial ) skal begynde hvis b1 [ i ] derefter //prmTextMatche[i]='_' derefter begynde res := res + prmTextInitial [ i ] ; ende ; ende ; TrouverMatches := res ; ende ; begynde ecartMax := runde ( Max ( Længde ( prmT1 ) , Længde ( prmT2 )) / 2 ) - 1 ; hvis (( prmT1 = '' ) eller ( prmT2 = '' )) så begynder JaroWinkler := 0 ; udgang ; ende ; compteMatching := 0 ; compteTransposition := 0 ; l1 := Længde ( prmT1 ) ; l2 := Længde ( prmT2 ) ; sætlængde ( b1 , 11 + 1 ) ; Setlængde ( b2 , l2 + 1 ) ; for i := 0 til l1 begynder b1 [ i ] : = falsk ; ende ; for i := 0 til l2 begynder b2 [ i ] : = falsk ; ende ; for i := 1 til l1 begynder c1 : = prmT1 [ i ] ; if ( i <= l2 ) så c2 := prmT2 [ i ] ellers c2 := '' ; for j := Max ( i - ecartMax , 1 ) til Min ( i + ecartMax , l2 ) begynder c2 : = prmT2 [ j ] ; hvis c1 = c2 så begynder //compteMatching avec transposition b1 [ i ] := sand ; b2 [ j ] := sand ; //Le caractère a été matché, il n'est plus disponible Inc ( compteMatching ) ; bryde ; ende ; ende ; ende ; if ( compteMatching = 0 ) så begynd JaroWinkler := 0 ; udgang ; ende ; //Dans les caractères matchés, compte ceux qui ne matchent pas exactement t1Matche := TrouverMatches ( prmT1 , b1 ) ; t2Matche := TrouverMatches ( prmT2 , b2 ) ; hvis t1Matche <> t2Matche så begynder for i := 1 til længde ( t1Matche ) begynder hvis t1Matche [ i ] <> t2 Match [ i ] så Inc ( compteTransposition ) slutter ; end else start compteTransposition := 0 ; ende ; distanceJaro := 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 ; for i := 1 til min ( 4 , min ( l1 , 12 )) begynder c1 : = prmT1 [ i ] ; c2 := prmT2 [ i ] ; hvis c1 = c2 så inc ( longueurPrefix ) else break ; ende ; //Valeur constante définie par l'algo JaroWinkler := distanceJaro + ( longueurPrefix * p * ( 1 - distanceJaro )) ; ende ; Implementering af algoritmen i PHP [6] <?php /* version 1.2 Copyright (c) 2005-2010 Ivo Ugrina <[email protected]> Et PHP-bibliotek, der implementerer afstanden Jaro og Jaro-Winkler , der måler lighed mellem strenge. Teoretiske ting kan findes i: Winkler, W.E. (1999). "Status for rekordforbindelse og aktuelle forskningsproblemer". Statistik over indkomstafdelingen, Internal Revenue Service Publication R99/04. http://www.census.gov/srd/papers/pdf/rr99-04.pdf. Dette program er gratis software; du kan videredistribuere det og/eller ændre det i henhold til betingelserne i GNU General Public License som udgivet af Free Software Foundation; enten version 3 af licensen eller (efter eget valg) enhver senere version. Dette program distribueres i håb om, at det vil være nyttigt, men UDEN NOGEN GARANTI; uden selv den underforståede garanti for SALGBARHED eller EGNETHED TIL ET BESTEMT FORMÅL. Se GNU General Public License for flere detaljer. Du skulle have modtaget en kopi af GNU General Public License sammen med dette program. Hvis ikke, se <http://www.gnu.org/licenses/>. === En stor tak går til Pierre Senellart <[email protected]> for at finde en lille fejl i koden. */ funktion getCommonCharacters ( $string1 , $string2 , $allowedDistance ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); $temp_string2 = $string2 ; $commonCharacters = '' ; for ( $i = 0 ; $i < $str1_len ; $i ++ ){ $noMatch = Sand ; // sammenlign, hvis char matcher inde i givet tilladtDistance //, og hvis det føjer det til commonCharacters for ( $j = max ( 0 , $i - $allowedDistance ); $noMatch && $j < min ( $i + $allowedDistance + 1 , $str2_len ); $j ++ ){ if ( $temp_string2 [ $j ] == $string1 [ $i ] ){ $noMatch = Falsk ; $commonCharacters .= $string1 [ $i ]; $temp_string2 [ $j ] = '' ; } } } returnere $commonCharacters ; } funktion Jaro ( $string1 , $string2 ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); // teoretisk afstand $distance = etage ( min ( $str1_len , $str2_len ) / 2.0 ); // få almindelige tegn $commons1 = getCommonCharacters ( $string1 , $string2 , $distance ); $commons2 = getCommonCharacters ( $string2 , $string1 , $distance ); if ( ( $commons1_len = strlen ( $commons1 )) == 0 ) returner 0 ; if ( ( $commons2_len = strlen ( $commons2 )) == 0 ) returner 0 ; // beregn transpositioner $transpositioner = 0 ; $upperBound = min ( $commons1_len , $commons2_len ); for ( $i = 0 ; $i < $øvergrænse ; $i ++ ){ if ( $commons1 [ $i ] != $commons2 [ $i ] ) $transpositioner ++ ; } $transpositioner /= 2.0 ; // returner Jaro-afstandsafkastet ( $commons1_len / ( $ str1_len ) + $commons2_len / ( $str2_len ) + ( $commons1_len - $transpositioner ) / ( $commons1_len )) / 3.0 ; } funktion getPrefixLength ( $string1 , $string2 , $MINPREFIXLENGTH = 4 ){ $n = min ( matrix ( $MINPREFIXLENGTH , strlen ( $string1 ), strlen ( $string2 ) ) ); for ( $i = 0 ; $i < $n ; $i ++ ){ if ( $string1 [ $i ] != $string2 [ $i ] ){ // returner indeks for første forekomst af forskellige tegn returnerer $i ; } } // første n tegn er det samme return $n ; } funktion JaroWinkler ( $string1 , $string2 , $PREFIXSCALE = 0.1 ){ $JaroDistance = Jaro ( $string1 , $string2 ); $prefixLength = getPrefixLength ( $string1 , $string2 ); return $JaroDistance + $prefixLength * $PREFIXSCALE * ( 1.0 - $JaroDistance ); } ?>

Noter

↑ Registrer koblingsalgoritmer i F# - Udvidelser til Jaro-Winkler-distance (del 3) . Hentet 21. marts 2017. Arkiveret fra originalen 31. december 2019. (ubestemt)
↑ Tilnærmede tekstsammenligningsalgoritmer, del 2 . Hentet 21. marts 2017. Arkiveret fra originalen 22. marts 2017. (ubestemt)
↑ Reference til database PL/SQL-pakker og -typer . Hentet 21. marts 2017. Arkiveret fra originalen 12. januar 2017. (ubestemt)
↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 23. februar 2011. Arkiveret fra originalen 23. februar 2011. (ubestemt)
↑ Distance de jaro-winkler Arkiveret 22. marts 2017 på Wayback Machine (FR)
↑ [1 ]

	D	jeg	x	O	N
D	en	0	0	0	0
jeg	0	en	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	en	0
N	0	0	0	0	en
x	0	0	0	0	0

	D	jeg	x	O	N
D	en	0	0	0	0
jeg	0	en	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	en	0
N	0	0	0	0	en
x	0	0	0	0	0

Jaro-Winkler lighed

Definition

Afstand Jaro

Jaro-Winkler distance

Eksempler

Eksempel 1

Eksempel 2

Eksempel 3

Relationer med andre afstandsændringsmetrikker

Praktisk anvendelse

Implementeringer af algoritmen i forskellige programmeringssprog

Noter

Links

	D	jeg	x	O	N
D	en	0	0	0	0
jeg	0	en	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	en	0
N	0	0	0	0	en
x	0	0	0	0	0