Jaro–Winkler distance

The Jaro similarity ${\displaystyle sim_{j}}$ of two given strings ${\displaystyle s_{1}}$ and ${\displaystyle s_{2}}$ is

${\displaystyle sim_{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.}$

Where:

• ${\displaystyle |s_{i}|}$ is the length of the string ${\displaystyle s_{i}}$;
• ${\displaystyle m}$ is the number of matching characters (see below);
• ${\displaystyle t}$ is the number of transpositions (see below).

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 ${\displaystyle s_{1}}$ is compared with all its matching characters in ${\displaystyle s_{2}}$. Two characters from ${\displaystyle s_{1}}$ and ${\displaystyle s_{2}}$ respectively, are considered matching only if they are the same and not farther than ${\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1}$ characters apart. For example, the following two nine character long strings, FAREMVIEL and FARMVILLE, have 8 matching characters. 'F', 'A' and 'R' are in the same position in both strings. Also 'M', 'V', 'I', 'E' and 'L' are within three (result of ${\displaystyle \lfloor {\tfrac {\max(9,9)}{2}}\rfloor -1}$) characters away.[3] If no matching characters are found then the strings are not similar and the algorithm terminates by returning Jaro similarity score 0.

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 ${\displaystyle m}$ and number of transpositions ${\displaystyle t}$ the Jaro similarity of FAREMVIEL and FARMVILLE can be calculated, ${\displaystyle {\frac {1}{3}}\left({\frac {8}{9}}+{\frac {8}{9}}+{\frac {8-1}{8}}\right)=0.88}$

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

${\displaystyle sim_{w}=sim_{j}+\ell p(1-sim_{j}),}$

where:

• ${\displaystyle sim_{j}}$ is the Jaro similarity for strings ${\displaystyle s_{1}}$ and ${\displaystyle s_{2}}$
• ${\displaystyle \ell }$ is the length of common prefix at the start of the string up to a maximum of 4 characters
• ${\displaystyle p}$ is a constant scaling factor for how much the score is adjusted upwards for having common prefixes. ${\displaystyle p}$ should not exceed 0.25 (i.e. 1/4, with 4 being the maximum length of the prefix being considered), otherwise the similarity could become larger than 1. The standard value for this constant in Winkler's work is ${\displaystyle p=0.1}$

The Jaro–Winkler distance ${\displaystyle d_{w}}$ is defined as ${\displaystyle d_{w}=1-sim_{w}}$.

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 ${\displaystyle d(x,y)=0\leftrightarrow x=y}$.