Jaro–Winkler distance
In computer science and statistics, the Jaro–Winkler distance is a string metric measuring an edit distance between two sequences. It is a variant proposed in 1990 by William E. Winkler of the Jaro distance metric (1989, Matthew A. Jaro). The Jaro–Winkler distance uses a prefix scale formula_1 which gives more favourable ratings to strings that match from the beginning for a set prefix length formula_2. The lower the Jaro–Winkler distance for two strings is, the more similar the strings are. The score is normalized such that 1 means an exact match and 0 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. Definition. Jaro similarity. The Jaro similarity formula_3 of two given strings formula_4 and formula_5 is Where: Two characters from formula_4 and formula_5 respectively, are considered "matching" only if they are the same and not farther than formula_13 characters  apart. Each character of formula_4 is compared with all its matching characters in formula_5. 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 apart than 1 (the result of formula_16). 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 formula_1  which gives more favorable ratings to strings that match from the beginning for a set prefix length formula_2. Given two strings formula_4 and formula_5, their Jaro–Winkler similarity formula_21 is: where: The Jaro–Winkler distance formula_30 is defined as formula_31. 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 formula_32. Relationship with other edit distance metrics. 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.