Jaro–Winkler distance

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] metric (1989, Matthew A. Jaro) proposed in 1990 by William E. Winkler.[2]

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

Definition

Jaro similarity

The Jaro similarity of two given strings and is

Where:

  • is the length of the string ;
  • is the number of matching characters (see below);
  • 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 is compared with all its matching characters in . Two characters from and respectively, are considered matching only if they are the same and not farther than 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 ) 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 and number of transpositions the Jaro similarity of FAREMVIEL and FARMVILLE can be calculated,

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 4 characters
  • is a constant scaling factor for how much the score is adjusted upwards for having common prefixes. 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

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.[4] The Jaro–Winkler distance also does not satisfy the identity axiom .

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.

See also

Footnotes

  1. Jaro, Matthew A. (1 June 1989). "Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida". Journal of the American Statistical Association. pp. 414–420. doi:10.1080/01621459.1989.10478785.
  2. Winkler, William E. (1990). "String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage".
  3. "What is Jaro-Winkler Similarity?". www.baseclass.io. Retrieved 26 July 2012.
  4. "Jaro-Winkler «  Inviting Epiphany". RichardMinerich.com. Retrieved 12 June 2017.

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.