Incomputer science andstatistics, theJaro–Winkler similarity is astring metric measuring anedit distance between two sequences. It is a variant of theJaro distance metric^[1] (1989, Matthew A. Jaro) proposed in 1990 byWilliam E. Winkler.^[2]

The Jaro–Winkler distance uses aprefix scale${\displaystyle p}$ which gives more favourable ratings to strings that match from the beginning for a set prefix length${\displaystyle \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 adistance metric, the Jaro–Winkler distance is not ametric in the mathematical sense of that term because it does not obey thetriangle inequality.

The Jaro similarity${\displaystyle {\text{sim}}_j}$ of two given strings${\displaystyle s_1}$ and${\displaystyle s_2}$ is

Where:

• ${\displaystyle |s_i|}$ is the length of the string${\displaystyle s_i}$;
• ${\displaystyle m}$ is the number ofmatching characters (see below);
• ${\displaystyle t}$ is the number oftranspositions (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 consideredmatching only if they are the same and not farther than${\displaystyle \lfloor \frac{max(|s_1|,|s_2|)}{2}\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 \frac{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 aprefix 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 {\text{sim}}_w}$ is:

${\displaystyle {\text{sim}}_w={\text{sim}}_j+\ell p(1-{\text{sim}}_j),}$

where:

• ${\displaystyle {\text{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 constantscaling 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-{\text{sim}}_w}$.

Although often referred to as adistance metric, the Jaro–Winkler distance is not ametric in the mathematical sense of that term because it does not obey thetriangle inequality.^[4] The Jaro–Winkler distance also does not satisfy the identity axiom${\displaystyle d(x,y)=0\leftrightarrow x=y}$.

There are other popular measures ofedit distance, which are calculated using a different set of allowable edit operations. For instance,

• theLevenshtein distance allows deletion, insertion and substitution;
• theDamerau–Levenshtein distance allows insertion, deletion, substitution, and thetransposition of two adjacent characters;
• thelongest common subsequence (LCS) distance allows only insertion and deletion, not substitution;
• theHamming distance allows only substitution, hence, it only applies to strings of the same length.

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 DNAsequence alignment algorithms such as theSmith–Waterman algorithm, which make an operation's cost depend on where it is applied.

• Record linkage
• Census

• 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.

• strcmp.c - Original C implementation by the author of the algorithm
• nltk.metrics.distance module- Python implementation in theNatural Language Toolkit

• String metrics

• CS1 maint: bot: original URL status unknown
• Articles with short description
• Short description matches Wikidata