52 lines
2 KiB
Text
52 lines
2 KiB
Text
The Jaro distance is a measure of edit distance between two strings; its inverse, called the ''Jaro similarity'', is a measure of two strings' similarity: the higher the value, the more similar the strings are. The score is normalized such that '''0''' equates to no similarities and '''1''' is an exact match.
|
||
|
||
|
||
;;Definition
|
||
|
||
The Jaro similarity <math>d_j</math> of two given strings <math>s_1</math> and <math>s_2</math> is
|
||
|
||
: <math>d_j = \left\{
|
||
|
||
\begin{array}{l l}
|
||
0 & \text{if }m = 0\\
|
||
\frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m}\right) & \text{otherwise} \end{array} \right.</math>
|
||
|
||
Where:
|
||
|
||
* <math>m</math> is the number of ''matching characters'';
|
||
* <math>t</math> is half the number of ''transpositions''.
|
||
|
||
|
||
Two characters from <math>s_1</math> and <math>s_2</math> respectively, are considered ''matching'' only if they are the same and not farther apart than <math>\left\lfloor\frac{\max(|s_1|,|s_2|)}{2}\right\rfloor-1</math> characters.
|
||
|
||
Each character of <math>s_1</math> is compared with all its matching characters in <math>s_2</math>. Each difference in position is half a ''transposition''; that is, the number of transpositions is half the number of characters which are common to the two strings but occupy different positions in each one.
|
||
|
||
|
||
;;Example
|
||
|
||
Given the strings <math>s_1</math> ''DWAYNE'' and <math>s_2</math> ''DUANE'' we find:
|
||
|
||
* <math>m = 4</math>
|
||
* <math>|s_1| = 6</math>
|
||
* <math>|s_2| = 5</math>
|
||
* <math>t = 0</math>
|
||
|
||
|
||
We find a Jaro score of:
|
||
|
||
: <math>d_j = \frac{1}{3}\left(\frac{4}{6} + \frac{4}{5} + \frac{4-0}{4}\right) = 0.822</math>
|
||
|
||
|
||
;Task
|
||
|
||
Implement the Jaro algorithm and show the similarity scores for each of the following pairs:
|
||
|
||
* ("MARTHA", "MARHTA")
|
||
* ("DIXON", "DICKSONX")
|
||
* ("JELLYFISH", "SMELLYFISH")
|
||
|
||
|
||
; See also
|
||
* [[wp:Jaro-Winkler_distance|Jaro–Winkler distance]] on Wikipedia.
|
||
<br><br>
|
||
|