Jaro–Winkler distance - Alchetron, The Free Social Encyclopedia

In computer science and statistics, the Jaro–Winkler distance is a string metric for measuring the edit distance between two sequences. It is a variant proposed in 1999 by William E. Winkler of the Jaro distance metric (1989, Matthew A. Jaro). Informally, the Jaro distance between two words is the minimum number of single-character transpositions required to change one word into the other.

Jaro distance

The Jaro distance d j of two given strings s 1 and s 2 is

d j = { 0 if m = 0 1 3 ( m | s 1 | + m | s 2 | + m − t m ) otherwise

Where:

| s i | is the length of the string s i ;

m is the number of matching characters (see below);

t is half the number of transpositions (see below).

Two characters from s 1 and s 2 respectively, are considered matching only if they are the same and not farther than ⌊ max ( | s 1 | , | s 2 | ) 2 ⌋ − 1 .

Each character of s 1 is compared with all its matching characters in s 2 . 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 than 1, i.e., floor(5/2)-1=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 distance

Jaro–Winkler distance uses a prefix scale p which gives more favourable ratings to strings that match from the beginning for a set prefix length ℓ . Given two strings s 1 and s 2 , their Jaro–Winkler distance d w is:

d w = d j + ( ℓ p ( 1 − d j ) )

where:

d j is the Jaro distance for strings s 1 and s 2

ℓ is the length of common prefix at the start of the string up to a maximum of 4 characters

p is a constant scaling factor for how much the score is adjusted upwards for having common prefixes. p should not exceed 0.25, otherwise the distance can become larger than 1. The standard value for this constant in Winkler's work is p = 0.1

Although often referred to as a distance metric, the Jaro–Winkler distance is actually not a metric in the mathematical sense of that term because it does not obey the triangle inequality [1]. In fact the Jaro–Winkler distance also does not satisfy that axiom that states that d ( x , y ) = 0 ↔ x = y .

In some implementations of Jaro-Winkler, the prefix bonus ℓ p ( 1 − d j ) is only added when the compared strings have a Jaro distance above a set "boost threshold" b t . The boost threshold in Winkler's implementation was 0.7.

d w = { d j if d j < b t d j + ( ℓ p ( 1 − d j ) ) otherwise

Example

Note that Winkler's "reference" C code differs in at least two ways from published accounts of the Jaro–Winkler metric. First is his use of a typo table (adjwt) and also some optional additional tolerance for long strings.

Example #1

Given the strings s 1 MARTHA and s 2 MARHTA we find:

m = 6

| s 1 | = 6

| s 2 | = 6

There are mismatched characters T/H and H/T leading to t = 2 2 = 1

We find a Jaro score of:

d j = 1 3 ( 6 6 + 6 6 + 6 − 1 6 ) = 0.944

To find the Jaro–Winkler score using the standard weight p = 0.1 , we continue to find:

ℓ = 3

Thus:

d w = 0.944 + ( 3 ∗ 0.1 ( 1 − 0.944 ) ) = 0.961

Given the strings s 1 DWAYNE and s 2 DUANE we find:

m = 4

| s 1 | = 6

| s 2 | = 5

t = 0

We find a Jaro score of:

d j = 1 3 ( 4 6 + 4 5 + 4 − 0 4 ) = 0.822

To find the Jaro–Winkler score using the standard weight p = 0.1 , we continue to find:

ℓ = 1

Thus:

d w = 0.822 + ( 1 ∗ 0.1 ( 1 − 0.822 ) ) = 0.84

Example #2

Given the strings s 1 DIXON and s 2 DICKSONX we find:

Here, the shaded cells are the match window for each character. A 1 in a cell indicates a match. Note that the two Xs are not considered matches because they are outside the match window of 3.

m = 4

| s 1 | = 5

| s 2 | = 8

t = 0

We find a Jaro score of:

d j = 1 3 ( 4 5 + 4 8 + 4 − 0 4 ) = 0.767

To find the Jaro–Winkler score using the standard weight p = 0.1 , we continue to find:

ℓ = 2

Thus:

d w = 0.767 + ( 2 ∗ 0.1 ( 1 − 0.767 ) ) = 0.814

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,

the Levenshtein distance allows deletion, insertion and substitution;

the Damerau–Levenshtein distance allows insertion, deletion, substitution, and the transposition of two adjacent characters;

the longest common subsequence (LCS) distance allows only insertion and deletion, not substitution;

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

References

Jaro–Winkler distance Wikipedia

(Text) CC BY-SA

Contents

Jaro distance

Jaro-Winkler distance

Example

Example #1

Example #2

Relationship with other edit distance metrics

References