Number Representations & States

"how numbers are stored and used in computers"

StringsDistance
EmbeddingSearchSimilarity

Jaro-Winkler Distance

The Jaro-Winkler distance is a sophisticated string similarity metric designed to measure how alike two strings are. It builds upon the Jaro distance metric by incorporating an additional factor that gives a higher score to strings that share a common prefix. This makes it particularly useful in applications where the beginning of the strings is more significant, such as in name matching.

O(m·n)
space
O(1)
O(n)·O(n)
Cosine distance
O(n)·O(1)
Hamming distance
O(m+n)·O(m+n)
Jaccard distance
Sorensen-Dice coefficient
Overlap coefficient
O(m·n)·O(m·n)
Levenshtein distance
Damerau-Levenshtein distance
O(m·n)·O(1)
Jaro-Winkler distance
O(n)
time
O(m·n)

Mathematical Definition

The Jaro-Winkler distance, denoted as , between two strings and is mathematically expressed as:

In this formula:

  • represents the Jaro distance, which is a foundational component of the Jaro-Winkler distance.
  • is the length of the common prefix shared by the two strings, with a maximum consideration of 4 characters. This parameter helps in boosting the similarity score for strings that start similarly.
  • is the scaling factor, typically set to 0.1, which determines the weight of the prefix in the overall similarity score.

The Jaro distance itself is calculated using the formula:

Here, represents the number of matching characters between the two strings. Characters are considered matching if they are the same and not farther apart than half the length of the longer string. The variable is half the number of transpositions, which are instances where matching characters appear in a different order. The symbols and denote the lengths of the strings and , respectively.

The Jaro-Winkler distance ranges from 0 to 1, where 0 indicates completely different strings and 1 indicates identical strings. The distance is symmetric, meaning . However, it does not satisfy the triangle inequality, which means it is not a true metric. Since it provides a boost to strings that share common prefixes, it is particularly useful for applications where the start of the string is significant.

The Jaro-Winkler distance is widely used in various fields. In record linkage, it helps identify records that refer to the same entity across different datasets. For name matching, it is used to compare names in databases to find duplicates or similar entries. In spell checking, it suggests corrections for misspelled words based on similarity. It is also employed in duplicate detection to identify duplicate entries in datasets and in data cleaning to improve data quality by merging similar entries.

Space efficiency

The space complexity of the Jaro-Winkler distance is because it only requires a constant amount of memory to store the variables , , and . The space complexity of the Jaro distance is also because it only requires a constant amount of memory to store the variables and .