Jaro–Winkler distance

This article is about the measure. For other uses, see Jaro.

In computer science and statistics, the Jaro–Winkler distance (Winkler, 1990) is a measure of similarity between two strings. It is a variant of the Jaro distance metric (Jaro, 1989, 1995), a type of string edit distance, and was developed in the area of record linkage (duplicate detection) (Winkler, 1990). The lower the Jaro–Winkler distance for two strings is, the more similar the strings are. The Jaro-Winkler similarity (for equation see below) is given by 1 - Jaro Winkler distance. The Jaro–Winkler distance metric is designed and best suited for short strings such as person names. The similarity score is normalized such that 0 equates to no similarity and 1 is an exact match.

Definition

The Jaro distance $d_{j}$ of two given strings $s_{1}$ and $s_{2}$ is

d_{j}=\left\{{\begin{array}{ll}0&{\text{if }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)&{\text{otherwise}}\end{array}}\right.

Where:

$m$ is the number of matching characters (see below);
$t$ is half the number of transpositions (see below).

Two characters from $s_{1}$ and $s_{2}$ respectively, are considered matching only if they are the same and not farther than $\left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1$ .

Each character of $s_{1}$ is compared with all its matching characters in $s_{2}$ . The number of matching (but different sequence order) characters divided by 2 defines the number of transpositions. For example, in comparing CRATE with TRACE, only 'R' 'A' 'E' are the matching characters, i.e. m=3. Although 'C', 'T' appear in both strings, they are farther than 1, i.e., floor(5/2)-1=1. Therefore, t=0 . In DwAyNE versus DuANE the matching letters are already in the same order D-A-N-E, so no transpositions are needed.

Jaro–Winkler distance uses a prefix scale $p$ which gives more favourable ratings to strings that match from the beginning for a set prefix length $\ell$ . Given two strings $s_{1}$ and $s_{2}$ , their Jaro–Winkler distance $d_{w}$ is:

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

where:

$d_{j}$ is the Jaro distance for strings $s_{1}$ and $s_{2}$
$\ell$ is the length of common prefix at the start of the string up to a maximum of 4 characters
$p$ is a constant scaling factor for how much the score is adjusted upwards for having common prefixes. $p$ should not exceed 0.25, otherwise the distance can become larger than 1. The standard value for this constant in Winkler's work is $p=0.1$

Although often referred to as a distance metric, the Jaro–Winkler distance is actually not a metric in the mathematical sense of that term because it does not obey the triangle inequality . In fact the Jaro–Winkler distance also does not satisfy that axiom that states that $d(x,y)=0\leftrightarrow x=y$ .

In some implementations of Jaro-Winkler, the prefix bonus $\ell p(1-d_{j})$ is only added when the compared strings have a Jaro distance above a set "boost threshold" $b_{t}$ . The boost threshold in Winkler's implementation was 0.7.

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.

Example

Note that Winkler's "reference" C code differs in at least two ways from published accounts of the Jaro–Winkler metric. First is his use of a typo table (adjwt) and also some optional additional tolerance for long strings.

Example #1

Given the strings $s_{1}$ MARTHA and $s_{2}$ MARHTA we find:

$m=6$
$|s_{1}|=6$
$|s_{2}|=6$
There are mismatched characters T/H and H/T leading to $t={\frac {2}{2}}=1$

We find a Jaro score of:

d_{j}={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-1}{6}}\right)=0.944

To find the Jaro–Winkler score using the standard weight $p=0.1$ , we continue to find:

\ell =3

Thus:

d_{w}=0.944+(3*0.1(1-0.944))=0.961

Given the strings $s_{1}$ DWAYNE and $s_{2}$ DUANE we find:

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

We find a Jaro score of:

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

To find the Jaro–Winkler score using the standard weight $p=0.1$ , we continue to find:

\ell =1

Thus:

d_{w}=0.822+(1*0.1(1-0.822))=0.84

Example #2

Given the strings $s_{1}$ DIXON and $s_{2}$ DICKSONX we find:

	D	I	X	O	N
D	1	0	0	0	0
I	0	1	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	1	0
N	0	0	0	0	1
X	0	0	1	0	0

Here, the shaded cells are the match window for each character. A 1 in a cell indicates a match. Note that the two Xs are not considered matches because they are outside the match window of 3.

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

We find a Jaro score of:

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

To find the Jaro–Winkler score using the standard weight $p=0.1$ , we continue to find:

\ell =2

Thus:

d_{w}=0.767+(2*0.1(1-0.767))=0.814

References

Cohen, W. W.; Ravikumar, P.; Fienberg, S. E. (2003). "A comparison of string distance metrics for name-matching tasks" (PDF). KDD Workshop on Data Cleaning and Object Consolidation. 3: 73–8.
Jaro, M. A. (1989). "Advances in record linkage methodology as applied to the 1985 census of Tampa Florida". Journal of the American Statistical Association. 84 (406): 414–20. doi:10.1080/01621459.1989.10478785.
Jaro, M. A. (1995). "Probabilistic linkage of large public health data file". Statistics in Medicine. 14 (5–7): 491–8. doi:10.1002/sim.4780140510. PMID 7792443.
Winkler, W. E. (1990). "String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage" (PDF). Proceedings of the Section on Survey Research Methods. American Statistical Association: 354–359.

Winkler, W. E. (2006). "Overview of Record Linkage and Current Research Directions" (PDF). Research Report Series, RRS.

External links

strcmp.c - Original C Implementation by the author of the algorithm

Strings

String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm

String searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp string search algorithm

Multiple string searching	Aho–Corasick Commentz-Walter algorithm Rabin–Karp

Regular expression	Comparison of regular expression engines Regular tree grammar Thompson's construction Nondeterministic finite automaton

Sequence alignment	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm

Data structures	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie

Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting

This article is issued from Wikipedia - version of the 11/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Jaro–Winkler distance

Definition

Example

Example #1

Example #2

See also

References

External links