Jaro-Winkler hasonlóságok

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. december 22-én felülvizsgált verziótól ; az ellenőrzések 9 szerkesztést igényelnek .

A számítástechnika és a statisztika területén a Jaro-Winkler hasonlóság a karakterlánc-hasonlóság mértéke két karaktersorozat közötti távolság mérésére. Ez egy William E. Winkler által 1999-ben javasolt változat a Jaro-távolság alapján (1989, Matthew A. Jaro). Informálisan a két szó közötti Jaro-távolság az egykarakteres transzformációk minimális száma, amely az egyik szó megváltoztatásához szükséges.

Minél kisebb a Jaro-Winkler távolság két húrnál, annál jobban hasonlítanak ezek a húrok egymáshoz. Az eredmény normalizálva van, így nincs hasonlóság, és pontos egyezést jelent. A Jaro-Winkler hasonlóság az . $d_{w}$ $d_{w}=0$ $d_{w}=1$ ${\displaystyle 1-d_{w))$

Definíció

Távolság Jaro

Jaro távolsága két megadott karakterlánc között, és ez: $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}}\jobbra)&{\text{egyébként }} \end{tömb}}\jobbra.

Ahol:

$|s_{i}|$ - húrhossz ; $s_{i}$
$m$ — az egyező karakterek száma (lásd alább);
$t$ - az átültetések számának fele (lásd alább).

A és a két karakter csak akkor egyezik meg, ha megegyezik, és legfeljebb . $s_{1}$ $s_{2}$ $\left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2))\right\rfloor -1$

A karakterlánc minden egyes karakterét a rendszer összehasonlítja a megfelelő karakterekkel . Az egyező (de eltérő sorszámú) karakterek száma, amely osztható 2-vel, határozza meg az átültetések számát . Például a CRATE szó és a TRACE szó összehasonlításakor csak az 'R' 'A' és 'E' egyező karakter, azaz m=3. Bár mindkét sorban megjelenik a 'C' és a 'T', ezek távolabb vannak 1-től, vagyis floor(5/2)-1=1. Ezért t=0. A DwAyNE és a DuANE összehasonlításakor a megfelelő betűk már ugyanabban a DANE sorrendben vannak, így nincs szükség permutációra. $s_{1}$ $s_{2}$

Jaro-Winkler távolság

A Jaro-Winkler távolság egy skálázási tényezőt használ , amely kedvezőbb minősítést ad az egymáshoz illeszkedő karakterláncoknak az elejétől egy bizonyos hosszúságig , amelyet előtagnak nevezünk. Adott két karakterlánc és . Jaro-Winkler távolságuk : $p$ $\ell$ $s_{1}$ $s_{2}$ $d_{w}$

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

ahol:

$d_{j}$ a Jaro távolság a sorokhoz és $s_{1}$ $s_{2}$
$\ell$ - a közös előtag hossza a karakterlánc elejétől maximum 4 karakterig
$p$ egy állandó skálázási tényező, amelyet a becslés felfelé állítására használnak, hogy észleljék a közös előtagok jelenlétét. nem haladhatja meg a 0,25-öt, különben a távolság 1-nél nagyobb lehet. Ennek az állandónak a standard értéke Winkler munkájában: . $p$ $p=0,1$

Míg a Jaro–Winkler távolságot gyakran távolságmérőnek nevezik , ez nem metrika a szó matematikai értelmében, mert nem engedelmeskedik a háromszög egyenlőtlenségnek . A Jaro-Winkler távolság sem felel meg az [1] axiómának . $d(x,y)=0\leftrightarrow x=y$

A Jaro-Winkler távolságszámítási algoritmus egyes megvalósításaiban csak akkor adunk hozzá előtag bónuszt, ha az összehasonlított karakterláncok Jaro-távolsága meghaladja a beállított "növelési küszöböt" . A Winkler implementációjában a küszöb 0,7 volt. $\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{egyébként}}\end{tömb}}\jobbra.

Példák

Meg kell jegyezni, hogy Winkler C kódja legalább két helyen eltér a Jaro-Winkler metrikáról publikált munkától. Az első az errata tábla (adjwt) használata, a második pedig néhány további feltétel a hosszú karakterláncokhoz.

1. példa

A MARTHA és MARHTA húrok adottak. A metszéspontjukat táblázatos formában ábrázoljuk: $s_{1}$ $s_{2}$

	M	A	R	T	H	A
M	egy	0	0	0	0	0
A	0	egy	0	0	0	0
R	0	0	egy	0	0	0
H	0	0	0	0	egy	0
T	0	0	0	egy	0	0
A	0	0	0	0	0	egy

Itt a maximális távolság 6/2 - 1 = 2. A fenti táblázat sárga cellái egyeseket jelölnek, ha a karakterek azonosak (egyezés van), egyébként nullákat.

Kiderül:

$m=6$
$|s_{1}|=6$
$|s_{2}|=6$
A T/H és a H/T karakterek nem egyeznek, ami a következőket eredményezi: $t={\frac {2}{2}}=1$

Jaro távolság:

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

Ahhoz, hogy megtaláljuk a Jaro-Winkler eredményt a standard súly használatával, folyamatosan keressük: $p=0,1$

\ell =3

Ilyen módon:

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

2. példa

A DWAYNE és DUANE húrok adottak. Kiderül: $s_{1}$ $s_{2}$

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

Jaro távolság:

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

Ahhoz, hogy megtaláljuk a Jaro-Winkler eredményt a standard súly használatával, folyamatosan keressük: $p=0,1$

\ell =1

Ilyen módon:

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

3. példa

Adott DIXON és DICKSONX karakterláncok . Kiderül: $s_{1}$ $s_{2}$

	D	én	x	O	N
D	egy	0	0	0	0
én	0	egy	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	egy	0
N	0	0	0	0	egy
x	0	0	0	0	0

Itt a kitöltött cellák az egyes karakterek megfelelő ablakai. A cellában lévő egység az egyezést jelzi. Ne feledje, hogy a két x (X) nem számít egyezésnek, mert a harmadik egyezési ablakon kívül vannak.

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

Jaro távolság:

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

Ahhoz, hogy megtaláljuk a Jaro-Winkler eredményt a standard súly használatával, folyamatosan keressük: $p=0,1$

\ell =2

Ilyen módon:

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

Kapcsolatok más távolságváltozási mérőszámokkal

A távolság változásának más népszerű mértékei is vannak, amelyeket más érvényes szerkesztési műveletekkel számítanak ki. Például,

A Levenshtein távolság lehetővé teszi a karakterek törlését, beszúrását és cseréjét;
A Damerau-Levenshtein távolság lehetővé teszi két szomszédos karakter beillesztését, törlését, cseréjét és permutációját ;
A legnagyobb közös részsorozat csak beszúrásokat és törléseket tesz lehetővé, cseréket nem;
A Hamming-távolság csak helyettesítést tesz lehetővé, tehát csak azonos hosszúságú húrokra vonatkozik.

A távolság változását általában egy paraméterezhető mérőszámként definiálják, amelyet érvényes szerkesztési műveletek bizonyos halmazával számítanak ki, és minden művelethez hozzárendelnek egy költséget (talán végtelen). Ez a genetikai szekvencia-illesztési algoritmusok további általánosítása , mint például a Smith-Waterman algoritmus , amelyek egy művelet költségét az alkalmazás helyétől teszik függővé.

Gyakorlati alkalmazás

A népszámlálás eredményeit a Jaro-Winkler algoritmussal dolgozták fel [2] .
A Jaro-Winkler karakterlánc-összehasonlító algoritmus az Oracle DBMS -ben [3] valósult meg .

Az algoritmus implementációi különböző programozási nyelveken

Az algoritmus implementációja C -ben [4] * strcmp95 . c 2. verzió */ /* Az strcmp95 függvény dupla pontosságú értéket ad vissza 0,0-tól (teljes nézeteltérés) 1,0-ig (karakterenkénti megegyezés). A visszaadott érték a két karakterlánc hasonlóságának mértéke. */ /* Megjelenés dátuma: jan. 1994. 26. */ /* Módosítva: 1994. április 24. Javítottuk az egy hosszúságú karakterláncok feldolgozását. Szerzők: Ez a függvény a Bill Winkler, George McLaughlin és Matt Jaro által írt kód logikájával készült , Maureen Lynch módosításaival. Megjegyzés: Ez a hivatalos karakterlánc-összehasonlító, amelyet az 1995-ös tesztösszeírás során használnak az egyeztetéshez . */ # include <ctype.h> # include <string.h> # NOTNUM(c) meghatározása ((c>57) || (c<48) # INRANGE(c) meghatározása ((c>0) && (c<91)) # MAX_VAR_SIZE meghatározása 61 # NULL60 meghatározása " " double strcmp95 ( char * ying , char * yang , hosszú y_length , int * ind_c []) { /* Érvek: A ying és a yang mutat a két összehasonlítandó karakterláncra. A karakterláncoknak nem kell NUL-végű karakterláncoknak lenniük, mert a hossz át van adva. y_length a karakterláncok hossza. Az ind_c egy tömb, amely annak meghatározására szolgál, hogy bizonyos beállításokat aktiválni kell-e . A nullától eltérő érték azt jelzi, hogy az opció ki van kapcsolva. A lehetőségek a következők: ind_c[0] Növelje az egyezés valószínűségét, ha az egyező karakterek száma nagy. Ez az opció egy kicsit nagyobb toleranciát tesz lehetővé, ha a húrok nagyok. Ez nem megfelelő teszt a rögzített hosszúságú mezők, például a telefonszámok és a társadalombiztosítási számok összehasonlításakor. ind_c[1] Az összehasonlítás előtt minden kisbetűs karaktert nagybetűvé alakítunk . Ennek a funkciónak a letiltása azt jelenti, hogy a kisbetűs "code" karakterlánc nem azonos a nagybetűs "CODE" karakterlánccal. Ezenkívül a hasonló karakterekre vonatkozó beállítás csak a nagybetűkre vonatkozik. A javasolt értékek mind nullák a karakterláncok, például a nevek esetében. */ static int pass = 0 , adjwt [ 91 ][ 91 ]; statikus karakter 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 ]; duplasúly , Num_sim ; _ long minv , search_range , lowlim , ying_length , hilim , N_trans , Num_com , yang_length ; int yl1 , yi_st , N_simi ; regiszter int i , j , k ; /* Csak a függvény első meghívásakor inicializálja az adjwt tömböt. Az adjwt tömb olyan karakterek részleges besorolására szolgál, amelyek ismert fonetikai vagy karakterfelismerési hibák miatt hibásak lehetnek. Tipikus példa az "O" betű és a "0" szám párosítása */ if ( ! pass ) { pass ++ ; ha ( i = 0 ; i < 91 ; i ++ ) ha ( 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 ; } } /* Ha bármelyik karakterlánc üres - visszatérés - hozzáadva a 2-es verzióhoz */ if ( ! strncmp ( ying , NULL60 , y_length )) return ( 0.0 ); if ( ! strncmp ( yang , NULL60 , y_length )) return ( 0.0 ); /* Határozza meg az összehasonlítandó karakterláncokat az összes kezdő és záró szóköz eltávolításával . */ k = y_hossz - 1 ; for ( j = 0 ;(( ying [ j ] == ' ' ) && ( j < k )); j ++ ); for ( i = k ;(( ying [ i ] == ' ' ) && ( i > 0 )); i -- ); ying_length = i + 1 - j ; yi_st = j ; for ( j = 0 ;(( yang [ j ] == ' ' ) && ( j < k )); j ++ ); for ( 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 ( ying_length > yang_length ) { keresési_tartomány = ying_length ; minv = yang_length ; } else { keresési_tartomány = yang_length ; minv = ying_length ; } /* Ha bármelyik karakterlánc üres - vissza */ /* if (!minv) return(0.0); eltávolítva a 2. verzióban */ /* Ürítse ki a zászlókat */ ying_flag [ 0 ] = ying_ flag [ 0 ] = 0 ; strncat ( ying_zászló , NULL60 , keresési_tartomány ); strncat ( yang_flag , NULL60 , keresési_tartomány ); keresési_tartomány = ( keresési_tartomány / 2 ) - 1 ; if ( keresési_tartomány < 0 ) keresési_tartomány = 0 ; /* hozzáadva a 2. verzióban */ /* Minden kisbetűs karakter nagybetűvé alakítása. */ if ( ! ind_c [ 1 ]) { for ( i = 0 ; i < ying_length ; i ++ ) if ( kisebb ( ying_hold [ i ] )) ying_hold [ i ] -= 32 ; for ( j = 0 ; j < yang_length ; j ++ ) if ( kisebb ( yang_hold [ j ] )) yang_hold [ j ] -= 32 ; } /* Ha csak a keresési tartományon belül néz, számolja meg és jelölje meg az egyező párokat. */ Num_com = 0 ; yl1 = yang_length - 1 ; for ( i = 0 ; i < ying_length ; i ++ ) { lowlim = ( i >= keresési_tartomány ) ? i - keresési_tartomány : 0 ; hilim = (( i + keresési_tartomány ) <= yl1 ) ? ( i + keresési_tartomány ) : 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 ++ ; szünet ; } } } /* Ha nincs közös karakter - vissza */ if ( ! Num_com ) return ( 0.0 ); /* Számolja meg az átültetések számát */ k = N_transz = 0 ; for ( i = 0 ; i < ying_length ; i ++ ) { if ( ying_flag [ i ] == '1' ) { for ( j = k ; j < yang_length ; j ++ ) { if ( yang_flag [ j ] == '1' ) { k = j + 1 ; szünet ; } } if ( ying_hold [ i ] != yang_hold [ j ]) N_trans ++ ; } } N_transz = N_transz / 2 ; /* korrigálja a nem egyező karakterek hasonlóságait */ 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 ] == ' ' && 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' ; szünet ; } } } } } _ Num_sim = (( double ) N_simi ) / 10.0 + Num_com ; /* Fő súlyszámítás. */ súly = Num_sim / ( ( dupla ) ying_length ) + Num_sim / ( ( dupla ) yang_length ) + (( double ) ( Num_com - N_trans )) / (( double ) Num_com ); tömeg = súly / 3,0 ; /* Folytassa a súly növelését, ha a karakterláncok hasonlóak */ if ( tömeg > 0,7 ) { /* Állítsa be úgy, hogy legfeljebb az első 4 közös karakter legyen */ j = ( minv >= 4 ) ? 4 : minv ; for ( i = 0 ;(( i < j ) && ( ying_hold [ i ] == yang_hold [ i ]) && ( NOTNUM ( ying_hold [ i ]))); i ++ ); ha ( i ) súly += i * 0,1 * ( 1,0 - tömeg ); /* Opcionálisan beállíthatja a hosszú karakterláncokhoz. */ /* A kezdeti karakterek megegyezése után legalább kettőnek egyeznie kell, és az egyetértő karaktereknek > 0,5-nek kell lenniük a fennmaradó karakterekből. */ if (( ! ind_c [ 0 ]) && ( minv > 4 ) && ( Num_com > i + 1 ) && ( 2 * Num_com >= minv + i )) if ( NOTNUM ( ying_hold [ 0 ])) súly += ( double ) ( 1,0 súly ) * _ (( double ) ( Num_com - i -1 ) / (( double ) ( ying_length + yang_length - i * 2 + 2 ))); } visszatérés ( súly ); } /* strcmp95 */ Az algoritmus implementációja Delphiben [5] függvény JaroWinkler ( prmT1 , prmT2 : Karakterlánc ; p : Double = 0.1 ) : Double ; Var ecartMax , l1 , l2 , compteMatching , compteTransposition , longueurPrefix , i , j : integer ; c1 , c2 , t1Match , t2Match : string ; b1 , b2 : logikai tömb ; _ távolságJaro : Dupla ; címke endfor , exitfor2 ; függvény TrouverMatches ( prmTextInitial : string ; b1 : logikai tömb ) : string ; _ var i : integer ; res : string _ 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 ] ; vége ; vége ; TrouverMatches := res ; vége ; begin ecartMax := round ( Max ( Length ( prmT1 ) , Length ( prmT2 )) / 2 ) - 1 ; if (( prmT1 = '' ) vagy ( prmT2 = '' )) akkor kezdődik a JaroWinkler := 0 ; kilépés ; vége ; compteMatching := 0 ; compteTransposition := 0 ; l1 := Hossz ( prmT1 ) ; l2 := Hossz ( prmT2 ) ; setlength ( b1 , l1 + 1 ) ; Setlength ( b2 , l2 + 1 ) ; mert i := 0 -tól l1 - ig kezdõdik b1 [ i ] := false ; vége ; mert i := 0 -tól l2 -ig nem kezdődik b2 [ i ] := false ; vége ; mert i := 1 -től l1 - ig kezdje a c1 := prmT1 [ i ] ; if ( i <= l2 ) akkor c2 := prmT2 [ i ] else c2 := '' ; j : = Max ( i - ecartMax , 1 ) - Min ( i + ecartMax , l2 ) esetén kezdje c2 := prmT2 [ j ] ; ha c1 = c2 akkor //compteMatching avec transzpozíció kezdődik b1 [ i ] := true ; b2 [ j ] := igaz ; //Le caractère a été matché, il n'est plus disponible Inc ( compteMatching ) ; szünet ; vége ; vége ; vége ; if ( compteMatching = 0 ) akkor kezdődik JaroWinkler := 0 ; kilépés ; vége ; //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 long ( t1Matche ) ne kezdődik if t1Matche [ i ] <> t2Matche [ i ] then Inc ( compteTransposition ) vége ; end else begin compteTransposition := 0 ; vége ; távolságJaro := 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 ; ha i := 1 -től min ( 4 , min ( l1 , l2 )) kezdődik c1 : = prmT1 [ i ] ; c2 := prmT2 [ i ] ; ha c1 = c2 akkor inc ( longueurPrefix ) else break ; vége ; //Valeur permanente définie par l'algo JaroWinkler := distanceJaro + ( longueurPrefix * p * ( 1 - distanceJaro )) ; vége ; Az algoritmus megvalósítása PHP -ben [6] <?php /* 1.2-es verzió Copyright (c) 2005-2010 Ivo Ugrina <[email protected]> A Jaro és Jaro-Winkler távolságot megvalósító PHP könyvtár, amely a karakterláncok közötti hasonlóságot méri. Az elméleti anyagok megtalálhatók: Winkler, W.E. (1999). "A rekordkapcsolat helyzete és a jelenlegi kutatási problémák". Jövedelemosztály statisztika, Belső Bevételi Szolgálat Kiadvány R99/04. http://www.census.gov/srd/papers/pdf/rr99-04.pdf. Ez a program ingyenes szoftver; tovább terjesztheti és/vagy módosíthatja a Free Software Foundation által közzétett GNU General Public License feltételei szerint ; vagy a Licenc 3-as verzióját, vagy (az Ön választása szerint) bármely későbbi verziót. Ezt a programot abban a reményben terjesztjük, hogy hasznos lesz, de MINDEN GARANCIA NÉLKÜL; még az ELADHATÓSÁGRA vagy A MEGHATÁROZOTT CÉLRA VALÓ ALKALMASSÁGRA vonatkozó hallgatólagos garancia nélkül. További részletekért lásd a GNU General Public License-t. Ezzel a programmal együtt meg kellett volna kapnia a GNU General Public License egy példányát . Ha nem, lásd: <http://www.gnu.org/licenses/>. === Nagy köszönet illeti Pierre Senellart <[email protected]> , hogy apró hibát talált a kódban. */ function getCommonCharacters ( $string1 , $string2 , $allowedDistance ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); $temp_karakterlánc2 = $ karakterlánc2 ; $commonCharacters = '' ; for ( $i = 0 ; $i < $str1_len ; $i ++ ){ $noMatch = Igaz ; // Hasonlítsa össze, hogy a karakter megegyezik-e a megadott megengedett távolságon belül // és ha igen, adja hozzá a commonCharacters for ( $j = max ( 0 , $i - $allowedDistance ); $noMatch && $j < min ( $i + $allowedDistance + 1 , $str2_len ); $j ++ ){ if ( $temp_string2 [ $j ] == $karakterlánc1 [ $i ] ){ $noMatch = False ; $commonCharacters .= $karakterlánc1 [ $i ]; $temp_string2 [ $j ] = '' ; } } } return $commonCharacters ; } function Jaro ( $karakterlánc1 , $ karakterlánc2 ){ $str1_len = strlen ( $string1 ); $str2_len = strlen ( $string2 ); // elméleti távolság $távolság = emelet ( min ( $str1_len , $str2_len ) / 2.0 ); // gyakori karakterek beszerzése $commons1 = getCommonCharacters ( $karakterlánc1 , $ karakterlánc2 , $távolság ); $commons2 = getCommonCharacters ( $ karakterlánc2 , $karakterlánc1 , $távolság ); if ( ( $commons1_len = strlen ( $commons1 )) == 0 ) return 0 ; if ( ( $commons2_len = strlen ( $commons2 )) == 0 ) return 0 ; // transzpozíciók kiszámítása $transzpozíciók = 0 ; $upperBound = min ( $commons1_len , $commons2_len ); for ( $i = 0 ; $i < $upperBound ; $i ++ ){ if ( $commons1 [ $i ] != $commons2 [ $i ] ) $transpositions ++ ; } $transzpozíciók /= 2.0 ; // a Jaro távolság visszaadása ( $commons1_len / ( $str1_len ) + $commons2_len / ( $str2_len ) + ( $commons1_len - $transpositions ) / ( $commons1_len )) / 3.0 ; } function getPrefixLength ( $karakterlánc1 , $karakterlánc2 , $ MINPREFIXLENGTH = 4 ){ $n = min ( tömb ( $ MINPREFIXLENGTH , strlen ( $karakterlánc1 ), strlen ( $karakterlánc2 ) ) ); for ( $i = 0 ; $i < $n ; $i ++ ){ if ( $karakterlánc1 [ $i ] != $ karakterlánc2 [ $ i ] ){ // a különböző karakterek első előfordulásának indexe return $i ; } } // az első n karakter ugyanaz . return $n ; } function JaroWinkler ( $karakterlánc1 , $karakterlánc2 , $ PREFIXSCALE = 0,1 ){ $JaroDistance = Jaro ( $karakterlánc1 , $ karakterlánc2 ); $prefixLength = getPrefixLength ( $karakterlánc1 , $ karakterlánc2 ); return $JaroDistance + $prefixLength * $PREFIXSCALE * ( 1.0 - $JaroDistance ); } ?>

Az algoritmus implementálása C# nyelven
Az algoritmus implementációja Java nyelven

Jegyzetek

↑ Összekapcsolási algoritmusok rögzítése F#-ban – Jaro-Winkler távolság kiterjesztése (3. rész) . Letöltve: 2017. március 21. Az eredetiből archiválva : 2019. december 31. (határozatlan)
↑ Hozzávetőleges szöveg-összehasonlító algoritmusok, 2. rész . Letöltve: 2017. március 21. Az eredetiből archiválva : 2017. március 22. (határozatlan)
↑ Adatbázis PL/SQL-csomagok és -típusok referencia . Letöltve: 2017. március 21. Az eredetiből archiválva : 2017. január 12. (határozatlan)
↑ Archivált másolat (a hivatkozás nem elérhető) . Letöltve: 2011. február 23. Az eredetiből archiválva : 2011. február 23.. (határozatlan)
↑ Distance de jaro-winkler Archiválva : 2017. március 22., a Wayback Machine -nél (FR)
↑ [1 ]

Linkek

Cohen, WW A karakterlánc-távolság metrikáinak összehasonlítása névillesztési feladatokhoz // KDD Workshop on Data Cleaning and Object Consolidation : Journal. - 2003. - 1. évf. 3 . - P. 73-8 .
Jaro, MA Előrelépések a rekordösszekapcsolási módszertanban a Tampa Florida 1985-ös népszámlálásánál // Journal of the American Statistical Association : folyóirat. - 1989. - 1. évf. 84 , sz. 406 . - P. 414-420 . - doi : 10.1080/01621459.1989.10478785 .
Jaro, MA Probabilistic linkage of large public health data file (angol) // Statistics in Medicine : Journal. - 1995. - 1. évf. 14 , sz. 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. - American Statistical Association, 1990. - P. 354-359 . Archiválva az eredetiből 2015. február 13-án.
William E. Winkler. A rekordok kapcsolatának áttekintése és a jelenlegi kutatási irányok // Research Report Series, RRS : folyóirat. – 2006.

	M	A	R	T	H	A
M	egy	0	0	0	0	0
A	0	egy	0	0	0	0
R	0	0	egy	0	0	0
H	0	0	0	0	egy	0
T	0	0	0	egy	0	0
A	0	0	0	0	0	egy

	D	én	x	O	N
D	egy	0	0	0	0
én	0	egy	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	egy	0
N	0	0	0	0	egy
x	0	0	0	0	0

	M	A	R	T	H	A
M	egy	0	0	0	0	0
A	0	egy	0	0	0	0
R	0	0	egy	0	0	0
H	0	0	0	0	egy	0
T	0	0	0	egy	0	0
A	0	0	0	0	0	egy

	D	én	x	O	N
D	egy	0	0	0	0
én	0	egy	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	egy	0
N	0	0	0	0	egy
x	0	0	0	0	0

	M	A	R	T	H	A
M	egy	0	0	0	0	0
A	0	egy	0	0	0	0
R	0	0	egy	0	0	0
H	0	0	0	0	egy	0
T	0	0	0	egy	0	0
A	0	0	0	0	0	egy

	D	én	x	O	N
D	egy	0	0	0	0
én	0	egy	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	egy	0
N	0	0	0	0	egy
x	0	0	0	0	0