In computer science and statistics, the Jaro–Winkler similarity is a string metric measuring an edit distance between two sequences. It is a variant of the Jaro distance metric[1] (1989, Matthew A. Jaro) proposed in 1990 by William E. Winkler.[2]
The Jaro–Winkler distance uses a prefix scale
p
\ell
The higher the Jaro–Winkler distance for two strings is, the less similar the strings are. The score is normalized such that 0 means an exact match and 1 means there is no similarity. The original paper actually defined the metric in terms of similarity, so the distance is defined as the inversion of that value (distance = 1 − similarity).
Although often referred to as a distance metric, the Jaro–Winkler distance is not a metric in the mathematical sense of that term because it does not obey the triangle inequality.
The Jaro similarity
simj
s1
s2
simj=\left\{ \begin{array}{ll} 0&ifm=0\\
| 1 | \left( | |
| 3 |
| m | |
| |s1| |
+
| m | |
| |s2| |
+
| m-t | |
| m |
\right)&otherwise\end{array}\right.
Where:
|si|
si
m
t
Jaro similarity score is 0 if the strings do not match at all, and 1 if they are an exact match. In the first step, each character of
s1
s2
s1
s2
| \left\lfloor | max(|s1|,|s2|) |
| 2 |
\right\rfloor-1
\lfloor\tfrac{max(9,9)}{2}\rfloor-1
If non-zero matching characters are found, the next step is to find the number of transpositions. Transposition is the number of matching characters that are not in the right order divided by two. In the above example between FAREMVIEL and FARMVILLE, 'E' and 'L' are the matching characters that are not in the right order. So the number of transposition is one.
Finally, plugging in the number of matching characters
m
t
| 1 | \left( | |
| 3 |
| 8 | |
| 9 |
+
| 8 | |
| 9 |
+
| 8-1 | |
| 8 |
\right)=0.88
Jaro–Winkler similarity uses a prefix scale
p
\ell
s1
s2
simw
simw=simj+\ellp(1-simj),
where:
simj
s1
s2
\ell
p
p
p=0.1
The Jaro–Winkler distance
dw
dw=1-simw
Although often referred to as a distance metric, the Jaro–Winkler distance is not a metric in the mathematical sense of that term because it does not obey the triangle inequality.[4] The Jaro–Winkler distance also does not satisfy the identity axiom
d(x,y)=0\leftrightarrowx=y
See main article: Edit distance. There are other popular measures of edit distance, which are calculated using a different set of allowable edit operations. For instance,
Edit distance is usually defined as a parameterizable metric calculated with a specific set of allowed edit operations, and each operation is assigned a cost (possibly infinite). This is further generalized by DNA sequence alignment algorithms such as the Smith–Waterman algorithm, which make an operation's cost depend on where it is applied.