In computer science and statistics, the Jaro–Winkler distance is a string metricmeasuring an edit distance between two sequences. It is a variant proposed in 1990 by William E. Winkler of the Jaro distancemetric. The Jaro–Winkler distance uses a prefix scale which gives more favourable ratings to strings that match from the beginning for a set prefix length. The lower the Jaro–Winkler distance for two strings is, the more similar the strings are. The score is normalized such that 0 means an exact match and 1 means there is no similarity. The Jaro–Winkler similarity is the inversion,. 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.
Definition
Jaro Similarity
The Jaro Similarity of two given strings and is Where:
Two characters from and respectively, are considered matching only if they are the same and not farther than characters apart. Each character of is compared with all its matching characters in. The number of matching 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 apart than 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 Similarity
Jaro–Winkler similarity uses a prefix scale which gives more favorable ratings to strings that match from the beginning for a set prefix length. Given two strings and, their Jaro–Winkler similarity is: where:
is the Jaro similarity for strings and
is the length of common prefix at the start of the string up to a maximum of four characters
is a constant scaling factor for how much the score is adjusted upwards for having common prefixes. should not exceed 0.25, otherwise the similarity could become larger than 1. The standard value for this constant in Winkler's work is
The Jaro-Winkler distance is defined as. 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–Winkler distance also does not satisfy the identity axiom.
the Hamming 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. 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.
