Podobnosti Jaro-Winkler

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. prosince 2019; kontroly vyžadují 9 úprav .

V oblasti informatiky a statistiky je podobnost Jaro-Winkler mírou podobnosti řetězců pro měření vzdálenosti mezi dvěma sekvencemi znaků. Jedná se o variantu navrženou Williamem E. Winklerem v roce 1999 na základě Jarovy vzdálenosti (1989, Matthew A. Jaro). Neformálně je Jaro vzdálenost mezi dvěma slovy minimální počet jednoznakových transformací potřebných ke změně jednoho slova na druhé.

Čím menší je vzdálenost Jaro-Winkler pro dvě struny, tím jsou si tyto struny podobnější. Výsledek je normalizován, takže to neznamená žádnou podobnost a znamená přesnou shodu. Podobnost Jaro-Winkler je . $d_{w}$ $d_{w}=0$ $d_{w}=1$ ${\displaystyle 1-d_{w))$

Definice

Vzdálenost Jaro

Jarova vzdálenost mezi dvěma danými strunami a toto: $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{jinak }} \end{array}}\right.

Kde:

$|s_{i}|$ — délka struny ; $s_{i}$
$m$ — počet odpovídajících znaků (viz níže);
$t$ - poloviční počet transpozic (viz níže).

Dva znaky z a jsou považovány za odpovídající pouze v případě, že jsou stejné a ne dále než . $s_{1}$ $s_{2}$ $\left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2))\right\rfloor -1$

Každý znak v řetězci je porovnán se všemi jeho odpovídajícími znaky v . Počet odpovídajících (ale odlišných řadových) znaků, který je dělitelný 2, určuje počet transpozic . Například při porovnávání slova CRATE se slovem TRACE jsou shodné znaky pouze 'R', 'A' a 'E', tj. m=3. Ačkoli se na obou řádcích objevují 'C' a 'T', jsou dále než 1, tedy patro(5/2)-1=1. Proto t=0. Při porovnávání DwAyNE s DuANE jsou odpovídající písmena již ve stejném pořadí DANE, takže nejsou potřeba žádné permutace. $s_{1}$ $s_{2}$

Vzdálenost Jaro-Winkler

Vzdálenost Jaro-Winkler používá faktor škálování , který dává příznivější hodnocení řetězcům, které si navzájem odpovídají od začátku až do určité délky , nazývané prefix. Dané dva řetězce a . Jejich vzdálenost Jaro-Winkler je: $p$ $\ell$ $s_{1}$ $s_{2}$ $d_{w}$

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

kde:

$d_{j}$ je vzdálenost Jaro pro řádky a $s_{1}$ $s_{2}$
$\ell$ - délka společné předpony od začátku řetězce do maximálně 4 znaků
$p$ je konstantní škálovací faktor používaný k úpravě odhadu směrem nahoru za účelem zjištění přítomnosti společných předpon. nesmí překročit 0,25, jinak může být vzdálenost větší než 1. Standardní hodnota této konstanty ve Winklerově práci je: . $p$ $p=0,1$

Zatímco vzdálenost Jaro–Winkler je často označována jako metrika vzdálenosti , není to metrika v matematickém smyslu slova, protože se neřídí trojúhelníkovou nerovností . Také vzdálenost Jaro-Winkler nesplňuje axiom, který říká, že [1] . $d(x,y)=0\leftrightarrow x=y$

V některých implementacích algoritmu výpočtu vzdálenosti Jaro-Winkler je přidán prefixový bonus pouze v případě, že porovnávané struny mají vzdálenost Jaro nad nastavenou "práh zesílení" . Prahová hodnota ve Winklerově implementaci byla 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{jinak}}\end{array}}\right.

Příklady

Je třeba poznamenat, že Winklerův kód C se minimálně na dvou místech liší od publikované práce o metrice Jaro-Winkler. Prvním je použití tabulky errata (adjwt) a druhým jsou některé dodatečné podmínky pro dlouhé řetězce.

Příklad 1

Jsou uvedeny struny MARTHA a MARHTA. Představme si jejich průsečík ve formě tabulky: $s_{1}$ $s_{2}$

	M	A	R	T	H	A
M	jeden	0	0	0	0	0
A	0	jeden	0	0	0	0
R	0	0	jeden	0	0	0
H	0	0	0	0	jeden	0
T	0	0	0	jeden	0	0
A	0	0	0	0	0	jeden

Zde je maximální vzdálenost 6/2 - 1 = 2. Žluté buňky ve výše uvedené tabulce označují jedničky, pokud jsou znaky shodné (existuje shoda), a jinak nuly.

Ukazuje se:

$m=6$
$|s_{1}|=6$
$|s_{2}|=6$
Existují neshodné znaky T/H a H/T, což má za následek: $t={\frac {2}{2}}=1$

Vzdálenost Jaro:

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

Abychom našli výsledek Jaro-Winkler pomocí standardní váhy, stále hledáme: $p=0,1$

\ell =3

Takto:

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

Příklad 2

Jsou dány struny DWAYNE a DUANE. Ukazuje se: $s_{1}$ $s_{2}$

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

Vzdálenost Jaro:

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

Abychom našli výsledek Jaro-Winkler pomocí standardní váhy, stále hledáme: $p=0,1$

\ell =1

Takto:

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

Příklad 3

Dané řetězce DIXON a DICKSONX . Ukazuje se: $s_{1}$ $s_{2}$

	D	já	X	Ó	N
D	jeden	0	0	0	0
já	0	jeden	0	0	0
C	0	0	0	0	0
K	0	0	0	0	0
S	0	0	0	0	0
Ó	0	0	0	jeden	0
N	0	0	0	0	jeden
X	0	0	0	0	0

Zde jsou vyplněné buňky odpovídajícím oknem pro každý znak. Jednotka v buňce označuje shodu. Všimněte si, že dvě x (X) nejsou považována za shodu, protože jsou mimo třetí okno shody.

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

Vzdálenost Jaro:

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

Abychom našli výsledek Jaro-Winkler pomocí standardní váhy, stále hledáme: $p=0,1$

\ell =2

Takto:

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

Vztahy s jinými metrikami změny vzdálenosti

Existují další populární míry změny vzdálenosti, které se počítají pomocí jiné sady platných editačních operací. Například,

Levenshteinova vzdálenost umožňuje mazání, vkládání a nahrazování znaků;
Vzdálenost Damerau-Levenshtein umožňuje vložení, odstranění, nahrazení a permutaci dvou sousedních znaků;
Největší společná podsekvence umožňuje pouze inzerce a delece, nikoli nahrazení;
Hammingova vzdálenost umožňuje pouze substituci, takže platí pouze pro struny stejné délky.

Změna vzdálenosti je obvykle definována jako parametrizovatelná metrika vypočítaná pomocí určité sady platných editačních operací a každé operaci je přiřazena cena (možná nekonečná). Toto je další zobecnění algoritmů zarovnání genetických sekvencí , jako je Smith-Watermanův algoritmus , který činí náklady operace závislými na tom, kde je aplikován.

Praktická aplikace

Pro zpracování výsledků sčítání lidu byl použit algoritmus Jaro-Winkler [2] .
Algoritmus pro porovnání řetězců Jaro-Winkler je implementován v Oracle DBMS [3] .

Implementace algoritmu v různých programovacích jazycích

Implementace algoritmu v C [4] * strcmp95 . c Verze 2 */ /* Funkce strcmp95 vrací hodnotu s dvojnásobnou přesností od 0,0 (celkový nesouhlas) do 1,0 (shoda znak po znaku). Vrácená hodnota je mírou podobnosti dvou řetězců. */ /* Datum vydání: leden. 26, 1994 */ /* Upraveno: 24. dubna 1994 Opraveno zpracování řetězců znaků s jednou délkou. Autoři: Tato funkce byla napsána pomocí logiky z kódu, který napsali Bill Winkler, George McLaughlin a Matt Jaro s úpravami Maureen Lynch. Komentář: Toto je oficiální porovnávač řetězců, který má být použit pro párování během sčítání v roce 1995. */ # include <ctype.h> # include <string.h> # definovat NOTNUM(c) ((c>57) || (c<48)) # definovat INRANGE(c) ((c>0) && (c<91)) # definovat MAX_VAR_SIZE 61 # definovat NULL60 " " double strcmp95 ( char * ying , char * yang , long y_length , int * ind_c []) { /* Argumenty: ying a yang jsou ukazatele na 2 řetězce, které mají být porovnány. Řetězce nemusí být řetězce zakončené NUL, protože délka je předána. y_length je délka řetězců. ind_c je pole, které se používá k určení, zda mají být aktivovány určité možnosti. Nenulová hodnota znamená, že možnost je deaktivována. Možnosti jsou: ind_c[0] Zvyšuje pravděpodobnost shody, když je počet shodných znaků velký. Tato možnost umožňuje trochu větší toleranci, když jsou řetězce velké. Není to vhodný test při porovnávání polí s pevnou délkou, jako jsou telefonní čísla a čísla sociálního zabezpečení. ind_c[1] Všechna malá písmena jsou před porovnáním převedena na velká písmena. Zakázání této funkce znamená, že řetězec malých písmen "kód" nebude rozpoznán jako stejný jako řetězec velkých písmen "CODE". Část úpravy pro podobné znaky se také vztahuje pouze na velká písmena. Navrhované hodnoty jsou všechny nuly pro znakové řetězce, jako jsou jména. */ static int pass = 0 , adjwt [ 91 ][ 91 ]; statický znak 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 ], jang_flag [ MAX_VAR_SIZE ]; doubleweight , Num_sim ; _ long minv , search_range , lowlim , ying_length , hilim , N_trans , Num_com , yang_length ; int yl1 , yi_st , N_simi ; registr int i , j , k ; /* Inicializuje pole adjwt pouze při prvním volání funkce. Pole adjwt se používá k přidělení částečného uznání znakům, které mohou být chybami v důsledku známých fonetických chyb nebo chyb v rozpoznávání znaků. Typickým příkladem je shoda písmene „O“ s číslem „0“ */ if ( ! pass ) { projít ++ ; 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 ; } } /* Pokud je některý řetězec prázdný - return - přidáno ve verzi 2 */ if ( ! strncmp ( ying , NULL60 , y_length )) return ( 0.0 ); if ( ! strncmp ( yang , NULL60 , y_length )) return ( 0.0 ); /* Identifikujte řetězce, které se mají porovnávat, odstraněním všech úvodních a koncových mezer. */ k = y_délka - 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 -- ); délka_jangu = 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 ) { rozsah_hledání = délka_jingu ; minv = délka_jangu ; } jinak { rozsah_hledání = délka_jangu ; minv = délka_jingu ; } /* Pokud je některý řetězec prázdný - vrátí */ /* if (!minv) return(0.0); odstraněno ve verzi 2 */ /* Vymažte příznaky */ ying_flag [ 0 ] = ying_flag [ 0 ] = 0 ; strncat ( ying_flag , NULL60 , search_range ); strncat ( yang_flag , NULL60 , search_range ); rozsah_hledání = ( rozsah_hledání / 2 ) - 1 ; if ( rozsah_hledani < 0 ) rozsah_hledani = 0 ; /* přidáno ve verzi 2 */ /* Převede všechna malá písmena na velká. */ if ( ! 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 ; } /* Podívejte se pouze do vyhledávacího rozsahu, spočítejte a označte odpovídající páry. */ Num_com = 0 ; yl1 = délka_jangu - 1 ; for ( i = 0 ; i < ying_length ; i ++ ) { lowlim = ( i >= rozsah_hledání ) ? i - rozsah_hledání : 0 ; hilim = (( i + rozsah_hledání ) <= yl1 ) ? ( i + rozsah_hledání ) : yl1 ; for ( j = lowlim ; j <= hilim ; j ++ ) { if (( yang_flag [ j ] != '1' ) && ( yang_hold [ j ] == ying_hold [ i ])) { jang_flag [ j ] = '1' ; ying_flag [ i ] = '1' ; Num_com ++ ; zlomit ; } } } /* Pokud žádné znaky nejsou společné - vrátí */ if ( ! Num_com ) return ( 0.0 ); /* Spočítejte počet transpozic */ k = N_trans = 0 ; for ( i = 0 ; i < ying_length ; i ++ ) { if ( ying_flag [ i ] == '1' ) { for ( j = k ; j < délka_jangu ; j ++ ) { if ( yang_flag [ j ] == '1' ) { k = j + 1 ; zlomit ; } } if ( ying_hold [ i ] != yang_hold [ j ]) N_trans ++ ; } } N_trans = N_trans / 2 ; /* upravit pro podobnosti v neshodných znacích */ 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 ]]; jang_flag [ j ] = '2' ; zlomit ; } } } } } _ Num_sim = (( double ) N_simi ) / 10,0 + Num_com ; /* Výpočet hlavní hmotnosti. */ váha = Num_sim / (( double ) ying_length ) + Num_sim / (( double ) yang_length ) + (( double ) ( Num_com - N_trans )) / (( double ) Num_com ); hmotnost = hmotnost / 3,0 ; /* Pokračujte ve zvyšování hmotnosti, pokud jsou struny podobné */ if ( hmotnost > 0,7 ) { /* Upravte tak, aby byly společné až první 4 znaky */ j = ( minv >= 4 ) ? 4 : minv ; for ( i = 0 ;(( i < j ) && ( ying_hold [ i ] == yang_hold [ i ]) && ( NOTNUM ( ying_hold [ i ]))); i ++ ); if ( i ) hmotnost += i * 0,1 * ( 1,0 - hmotnost ); /* Volitelně upravit pro dlouhé řetězce. */ /* Po odsouhlasení počátečních znaků musí souhlasit alespoň dva další a souhlasné znaky musí být > 0,5 ze zbývajících znaků. */ if (( ! ind_c [ 0 ]) && ( minv > 4 ) && ( Num_com > i + 1 ) && ( 2 * Num_com >= minv + i )) if ( NOTNUM ( ying_hold [ 0 ])) hmotnost += ( double ) ( 1,0 - hmotnost ) * (( double ) ( Num_com - i -1 ) / (( double ) ( ying_length + yang_length - i * 2 + 2 ))); } návrat ( váha ); } /* strcmp95 */ Implementace algoritmu v Delphi [5] funkce JaroWinkler ( prmT1 , prmT2 : String ; p : Double = 0,1 ) : Double ; Var ecartMax , l1 , l2 , compteMatching , compteTransposition , longueurPrefix , i , j : integer ; c1 , c2 , t1Match , t2Match : string ; b1 , b2 : pole Boolean ; _ vzdálenostJaro : Double ; label endfor , exitfor2 ; function TrouverMatches ( prmTextInitial : string ; b1 : pole Boolean ) : string ; _ var i : celé číslo ; res : řetězec _ begin // Vypočítat 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 ] ; konec ; konec ; TrouverMatches := res ; konec ; begin ecartMax := round ( Max ( Length ( prmT1 ) , Length ( prmT2 )) / 2 ) - 1 ; if (( prmT1 = '' ) nebo ( prmT2 = '' )) then begin JaroWinkler := 0 ; výstup ; konec ; compteMatching := 0 ; compteTransposition := 0 ; l1 := Délka ( prmT1 ) ; l2 := Délka ( prmT2 ) ; setlength ( b1 , l1 + 1 ) ; Setlength ( b2 , l2 + 1 ) ; for i := 0 až l1 do begin b1 [ i ] := false ; konec ; for i := 0 až l2 do begin b2 [ i ] := false ; konec ; for i := 1 až l1 do begin c1 := prmT1 [ i ] ; if ( i <= l2 ) then c2 := prmT2 [ i ] else c2 := '' ; for j := Max ( i - ecartMax , 1 ) až Min ( i + ecartMax , l2 ) do begin c2 := prmT2 [ j ] ; if c1 = c2 then //compteMatching avec transposition begin b1 [ i ] := true ; b2 [ j ] := true ; //Le caractère a été matché, il n'est plus disponible Inc ( compteMatching ) ; zlomit ; konec ; konec ; konec ; if ( compteMatching = 0 ) then begin JaroWinkler := 0 ; výstup ; konec ; //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 ; konec ; 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 až min ( 4 , min ( l1 , l2 )) do begin c1 := prmT1 [ i ] ; c2 := prmT2 [ i ] ; if c1 = c2 then inc ( longueurPrefix ) else break ; konec ; //Valeur Constante définie par l' algo JaroWinkler := distanceJaro + ( longueurPrefix * p * ( 1 - distanceJaro )) ; konec ; Implementace algoritmu v PHP [6] <?php /* verze 1.2 Copyright (c) 2005-2010 Ivo Ugrina <[email protected]> PHP knihovna implementující vzdálenost Jaro a Jaro-Winkler , měřící podobnost mezi řetězci. Teoretické věci lze nalézt v: Winkler, W.E. (1999). „Stav propojení záznamů a aktuální problémy výzkumu“ . Statistika divize příjmů, publikace Internal Revenue Service R99/04. http://www.census.gov/srd/papers/pdf/rr99-04.pdf. Tento program je svobodný software; můžete jej redistribuovat a/nebo upravovat podle podmínek GNU General Public License, jak je zveřejněna Free Software Foundation; buď verze 3 licence, nebo (dle vašeho uvážení) jakákoli pozdější verze. Tento program je distribuován v naději, že bude užitečný, ale BEZ JAKÉKOLI ZÁRUKY; dokonce bez předpokládané záruky PRODEJNOSTI nebo VHODNOSTI PRO KONKRÉTNÍ ÚČEL. Další podrobnosti najdete v GNU General Public License. Spolu s tímto programem byste měli obdržet kopii GNU General Public License . Pokud ne, podívejte se na <http://www.gnu.org/licenses/>. === Velké díky patří Pierru Senellartovi <[email protected]> za nalezení malé chyby v kódu. */ function getCommonCharacters ( $ string1 , $ string2 , $allowedDistance ){ $str1_len = strlen ( $ string1 ); $str2_len = strlen ( $ string2 ); $temp_string2 = $ string2 ; $commonCharacters = '' ; for ( $i = 0 ; $i < $str1_len ; $i ++ ){ $noMatch = Pravda ; // porovnejte, zda se znak shoduje uvnitř dané povolené vzdálenosti // a zda jej přidá do společných znaků pro ( $j = max ( 0 , $i - $allowedDistance ); $noMatch && $j < min ( $i + $allowedDistance + 1 , $str2_len ); $j ++ ){ if ( $temp_string2 [ $j ] == $string1 [ $i ] ){ $noMatch = False ; $commonCharacters .= $ string1 [ $i ]; $temp_string2 [ $j ] = '' ; } } } return $commonCharacters ; } function Jaro ( $string1 , $string2 ){ $str1_len = strlen ( $ string1 ); $str2_len = strlen ( $ string2 ); // teoretická vzdálenost $vzdálenost = podlaha ( min ( $str1_len , $str2_len ) / 2,0 ); // získání běžných znaků $commons1 = getCommonCharacters ( $ string1 , $ string2 , $vzdálenost ); $commons2 = getCommonCharacters ( $ string2 , $ string1 , $vzdálenost ); if ( ( $commons1_len = strlen ( $commons1 )) == 0 ) return 0 ; if ( ( $commons2_len = strlen ( $commons2 )) == 0 ) return 0 ; // výpočet transpozice $transpozice = 0 ; $upperBound = min ( $commons1_len , $commons2_len ); for ( $i = 0 ; $i < $upperBound ; $i ++ ){ if ( $commons1 [ $i ] != $commons2 [ $i ] ) $transpozice ++ ; } $transpozice /= 2,0 ; // return the Jaro distance return ( $commons1_len / ( $str1_len ) + $commons2_len / ( $str2_len ) + ( $commons1_len - $transpositions ) / ( $commons1_len )) / 3.0 ; } function getPrefixLength ( $ string1 , $ string2 , $MINPREFIXLENGTH = 4 ){ $n = min ( pole ( $MINPREFIXLENGTH , strlen ( $ string1 ), strlen ( $string2 ) ) ); for ( $i = 0 ; $i < $n ; $i ++ ){ if ( $string1 [ $i ] != $string2 [ $i ] ){ // návrat indexu prvního výskytu různých znaků return $i ; } } // prvních n znaků je stejných return $n ; } function JaroWinkler ( $ string1 , $ string2 , $PREFIXSCALE = 0,1 ){ $JaroDistance = Jaro ( $ string1 , $ string2 ); $prefixLength = getPrefixLength ( $ string1 , $ string2 ); return $JaroDistance + $prefixLength * $PREFIXSCALE * ( 1,0 - $JaroDistance ); } ?>

Poznámky

↑ Record Linkage Algorithms in F# - Extensions to Jaro-Winkler Distance (Part 3) . Získáno 21. března 2017. Archivováno z originálu 31. prosince 2019. (neurčitý)
↑ Algoritmy pro přibližné porovnávání textu, část 2 . Získáno 21. března 2017. Archivováno z originálu dne 22. března 2017. (neurčitý)
↑ Databáze PL/SQL balíčků a typů Reference . Získáno 21. března 2017. Archivováno z originálu 12. ledna 2017. (neurčitý)
↑ Archivovaná kopie (odkaz není dostupný) . Získáno 23. února 2011. Archivováno z originálu 23. února 2011. (neurčitý)
↑ Distance de jaro-winkler Archived 22. března 2017 na Wayback Machine (FR)
↑ [1 ]

Odkazy

Cohen, WW Porovnání metrik vzdálenosti řetězců pro úlohy přiřazování názvů // KDD Workshop on Data Cleaning and Object Consolidation: journal. - 2003. - Sv. 3 . - S. 73-8 .
Jaro, MA Pokroky v metodologii propojování záznamů aplikované na sčítání lidu v Tampě na Floridě v roce 1985 // Journal of the American Statistical Association : journal. - 1989. - Sv. 84 , č. 406 . - str. 414-420 . - doi : 10.1080/01621459.1989.10478785 .
Jaro, MA Pravděpodobnostní propojení velkého souboru dat o veřejném zdraví (anglicky) // Statistics in Medicine : journal. - 1995. - Sv. 14 , č. 5-7 . - str. 491-498 . - doi : 10.1002/sim.4780140510 . — PMID 7792443 .
Winkler, WE String Comparator Metrics and Enhanced Decision Rules in Fellegi-Sunter Model of Record Linkage // Proceedings of the Section on Survey Research Methods: journal. - Americká statistická asociace, 1990. - S. 354-359 . Archivováno z originálu 13. února 2015.
William E. Winkler. Přehled propojení záznamů a aktuální směry výzkumu // Research Report Series, RRS: journal. — 2006.