en>RjwilmsiBot: CiteCompletion, dates: 3, using AWB (9488)

2013-09-22T17:47:16Z

CiteCompletion, dates: 3, using AWB (9488)

New page

{{About|the measure|other uses|Jaro (disambiguation){{!}}Jaro}}

{{Original research|date=May 2013}}
{{Notability|date=May 2013}}

In [[computer science]] and [[statistics]], the '''Jaro–Winkler distance''' (Winkler, 1990) is a measure of similarity between two [[String (computer science)|strings]]. It is a variant of the '''Jaro distance''' metric (Jaro, 1989, 1995), a type of string [[edit distance]], and mainly {{Citation needed|date=January 2011}} used in the area of [[record linkage]] (duplicate detection). The higher the Jaro–Winkler distance for two strings is, the more similar the strings are. The Jaro–Winkler distance metric is designed and best suited for short strings such as person names. The score is normalized such that 0 equates to no similarity and 1 is an exact match.

== Definition ==

The Jaro distance <math>d_j</math> of two given strings <math>s_1</math> and <math>s_2</math> is

: <math>d_j = \left\{

\begin{array}{l l}
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.</math>

where:

* <math>m</math> is the number of ''matching characters'' (see below);
* <math>t</math> is half the number of ''transpositions'' (see below).

Two characters from <math>s_1</math> and <math>s_2</math> respectively, are considered ''matching'' only if they are the same and not farther than <math>\left\lfloor\frac{\max(|s_1|,|s_2|)}{2}\right\rfloor-1</math>.

Each character of <math>s_1</math> is compared with all its matching
characters in <math>s_2</math>. 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 <math>p</math> which gives more favourable ratings to strings that match from the beginning for a set prefix length <math>\ell</math>. Given two strings <math>s_1</math> and <math>s_2</math>, their Jaro–Winkler distance <math>d_w</math> is:

: <math>d_w = d_j + (\ell p (1 - d_j))</math>

where:

* <math>d_j</math> is the Jaro distance for strings <math>s_1</math> and <math>s_2</math>
* <math>\ell</math> is the length of common prefix at the start of the string up to a maximum of 4 characters
* <math>p</math> is a constant [[scaling factor]] for how much the score is adjusted upwards for having common prefixes. <math>p</math> should not exceed 0.25, otherwise the distance can become larger than 1. The standard value for this constant in Winkler's work is <math>p = 0.1</math>

Although often referred to as a ''distance metric'', the Jaro–Winkler distance is actually not a [[metric (mathematics)|metric]] in the mathematical sense of that term because it does not obey the [[triangle inequality]] [http://richardminerich.com/tag/jaro-winkler/].

In some implementations of Jaro-Winkler, the prefix bonus <math>\ell p (1 - d_j)</math> is only added when the compared strings have a Jaro distance above a set "boost threshold" <math>b_t</math>. The boost threshold in Winkler's implementation was 0.7.

: <math>d_w = \left\{

\begin{array}{l l}
d_j & \text{if }d_j < b_t\\
d_j + (\ell p (1 - d_j)) & \text{otherwise} \end{array} \right.</math>

== 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.''

Given the strings <math>s_1</math> ''MARTHA'' and <math>s_2 </math> ''MARHTA'' we find:

* <math>m = 6</math>
* <math>|s_1| = 6</math>
* <math>|s_2| = 6</math>
* There are mismatched characters T/H and H/T leading to <math>t = \frac{2}{2} = 1</math>

We find a Jaro score of:

<math>d_j = \frac{1}{3}\left(\frac{6}{6} + \frac{6}{6} + \frac{6-1}{6}\right) = 0.944</math>

To find the Jaro–Winkler score using the standard weight <math>p = 0.1</math>, we continue to find:

* <math>\ell = 3</math>

Thus:

: <math>d_w = 0.944 + (3 * 0.1 (1 - 0.944)) = 0.961</math>

Given the strings <math>s_1</math> ''DWAYNE'' and <math>s_2</math> ''DUANE'' we find:

* <math>m = 4</math>
* <math>|s_1| = 6</math>
* <math>|s_2| = 5</math>
* <math>t = 0</math>

We find a Jaro score of:

: <math>d_j = \frac{1}{3}\left(\frac{4}{6} + \frac{4}{5} + \frac{4-0}{4}\right) = 0.822</math>

To find the Jaro–Winkler score using the standard weight <math>p = 0.1</math>, we continue to find:

* <math>\ell = 1</math>

Thus:

: <math>d_w = 0.822 + (1 * 0.1 (1 - 0.822)) = 0.84</math>

Given the strings <math>s_1</math> ''DIXON'' and <math>s_2</math> ''DICKSONX'' we find:

{{elucidate|date=March 2013}}

{| class="wikitable"
|-
|
| 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
| 0
| 0
| 0
|}

* <math>m = 4</math> Note that the two ''X''s are not considered matches because they are outside the match window of 3.

* <math>|s_1| = 5</math>
* <math>|s_2| = 8</math>
* <math>t = 0</math>

We find a Jaro score of:

: <math>d_j = \frac{1}{3}\left(\frac{4}{5} + \frac{4}{8} + \frac{4-0}{4}\right) = 0.767</math>

To find the Jaro–Winkler score using the standard weight <math>p = 0.1</math>, we continue to find:

* <math>\ell = 2</math>

Thus:

: <math>d_w = 0.767 + (2 * 0.1 (1 - 0.767)) = 0.813</math>

== See also ==

* [[Levenshtein distance]]
* [[Record linkage]]
* [[Census]]

== References ==

* {{cite journal | author = [[Matthew A. Jaro|Jaro, M. A.]] | title = Advances in record linkage methodology as applied to the 1985 census of Tampa Florida | journal = Journal of the American Statistical Association | year = 1989 | volume = 84 | issue = 406 |pages=414–20| url = | doi = 10.1080/01621459.1989.10478785 }}
* {{cite journal |author=Jaro, M. A. |title=Probabilistic linkage of large public health data file |journal= Statistics in Medicine |year=1995 |volume=14 |issue=5–7 |pages=491–8 |pmid=7792443 |doi=10.1002/sim.4780140510}}
* {{cite journal

| author = [[William E. Winkler|Winkler, W. E.]]
| title = String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage
| journal = Proceedings of the Section on Survey Research Methods
| publisher = American Statistical Association
| pages = 354–359
| year = 1990
| url = http://www.amstat.org/sections/srms/Proceedings/papers/1990_056.pdf }}

* {{cite journal | author = [[William E. Winkler|Winkler, W. E.]] | title = Overview of Record Linkage and Current Research Directions | journal = Research Report Series, RRS | year = 2006 | volume = | issue = | url = http://www.census.gov/srd/papers/pdf/rrs2006-02.pdf}}

== External links ==

* [http://web.archive.org/web/20100227020019/http://www.census.gov/geo/msb/stand/strcmp.c strcmp.c - Original C Implementation by the author of the algorithm]

{{DEFAULTSORT:Jaro-Winkler distance}}

[[Category:String similarity measures]]

Parallax barrier - Revision history

en>RjwilmsiBot: CiteCompletion, dates: 3, using AWB (9488)