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 &nbsp; '''0''' &nbsp; equates to no similarities and &nbsp; '''1''' &nbsp; is an exact match.


;;Definition

The Jaro similarity &nbsp; <math>d_j</math> &nbsp; of two given strings &nbsp; <math>s_1</math> &nbsp; and &nbsp; <math>s_2</math> &nbsp; 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> &nbsp; is the number of ''matching characters'';
* <math>t</math> &nbsp; is half the number of ''transpositions''.


Two characters from &nbsp; <math>s_1</math> &nbsp; and &nbsp; <math>s_2</math> &nbsp; respectively, are considered ''matching'' only if they are the same and not farther apart than &nbsp; <math>\left\lfloor\frac{\max(|s_1|,|s_2|)}{2}\right\rfloor-1</math> characters.

Each character of &nbsp; <math>s_1</math> &nbsp; is compared with all its matching characters in &nbsp; <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 &nbsp; <math>s_1</math> &nbsp; ''DWAYNE'' &nbsp; and &nbsp; <math>s_2</math> &nbsp; ''DUANE'' &nbsp; 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>

