How to resolve the algorithm Jaro similarity step by step in the Ada programming language

Published on 12 May 2024 09:40 PM
#Ada

How to resolve the algorithm Jaro similarity step by step in the Ada programming language

Table of Contents

Problem Statement

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.

The Jaro similarity

d

j

{\displaystyle d_{j}}

of two given strings

s

1

{\displaystyle s_{1}}

and

s

2

{\displaystyle s_{2}}

is Where:

Two characters from

s

1

{\displaystyle s_{1}}

and

s

2

{\displaystyle s_{2}}

respectively, are considered matching only if they are the same and not farther apart than

⌊

max (

|

s

1

|

,

|

s

2

|

)

2

⌋

− 1

{\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1}

characters. Each character of

s

1

{\displaystyle s_{1}}

is compared with all its matching characters in

s

2

{\displaystyle s_{2}}

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

Given the strings

s

1

{\displaystyle s_{1}}

DWAYNE   and

s

2

{\displaystyle s_{2}}

DUANE   we find:

We find a Jaro score of:

Implement the Jaro algorithm and show the similarity scores for each of the following pairs:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Jaro similarity step by step in the Ada programming language

Source code in the ada programming language

with Ada.Text_IO;

procedure Jaro_Distances is

   type Jaro_Measure is new Float;

   function Jaro_Distance (Left, Right : in String) return Jaro_Measure
   is
      Left_Matches   : array (Left'Range)  of Boolean := (others => False);
      Right_Matches  : array (Right'Range) of Boolean := (others => False);
      Matches        : Natural := 0;
      Transpositions : Natural := 0;
   begin
      if Left'Length = 0 and Right'Length = 0 then
         return 1.000;
      end if;

      declare
         Match_Distance : constant Natural := Natural'Max (Left'Length, Right'Length) / 2 - 1;
      begin
         for L in Left'Range loop
            declare
               First : constant Natural := Natural'Max (Right'First, Right'First + L - Left'First - Match_Distance);
               Last  : constant Natural := Natural'Min (L - Left'First + Match_Distance + Right'First, Right'Last);
            begin
               for R in First .. Last loop
                  if
                    not Right_Matches (R) and
                    Left (L) = Right (R)
                  then
                     Left_Matches (L)  := True;
                     Right_Matches (R) := True;
                     Matches := Matches + 1;
                     exit;
                  end if;
               end loop;
            end;
         end loop;
      end;

      if Matches = 0 then
         return 0.000;
      end if;

      declare
         R : Natural := Right'First;
      begin
         for L in Left'Range loop
            if Left_Matches (L) then
               while not Right_Matches (R) loop
                  R := R + 1;
               end loop;
               if Left (L) /= Right (R) then
                  Transpositions := Transpositions + 1;
               end if;
               R := R + 1;
            end if;
         end loop;
      end;

      declare
         Match  : constant Float := Float (Matches);
         Term_1 : constant Float := Match / Float (Left'Length);
         Term_2 : constant Float := Match / Float (Right'Length);
         Term_3 : constant Float := (Match - Float (Transpositions) / 2.0) / Match;
      begin
         return Jaro_Measure ((Term_1 + Term_2 + Term_3) / 3.0);
      end;
   end Jaro_Distance;

   procedure Show_Jaro (Left, Right :  in String)
   is
      package Jaro_IO is
         new Ada.Text_IO.Float_IO (Jaro_Measure);
      use Ada.Text_IO;

      Distance : constant Jaro_Measure := Jaro_Distance (Left, Right);
   begin
      Jaro_IO.Put (Distance, Fore => 1, Aft => 5, Exp => 0);
      Set_Col (10);  Put (Left);
      Set_Col (22);  Put (Right);
      New_Line;
   end Show_Jaro;

   S1 : constant String := "  MARTHA VS MARHTA  ";
begin
   Show_Jaro ("DWAYNE",    "DUANE");
   Show_Jaro ("DIXON",     "DICKSONX");
   Show_Jaro ("JELLYFISH", "SMELLYFISH");
   Show_Jaro (S1 (3 .. 8), S1 (13 .. 18));
end Jaro_Distances;

You may also check:How to resolve the algorithm RCRPG step by step in the Ruby programming language
You may also check:How to resolve the algorithm Handle a signal step by step in the Perl programming language
You may also check:How to resolve the algorithm Abstract type step by step in the Red programming language
You may also check:How to resolve the algorithm Numbers which are not the sum of distinct squares step by step in the Modula-2 programming language
You may also check:How to resolve the algorithm Rot-13 step by step in the ZX Spectrum Basic programming language