Сходство Яро и Яро-Винклера

Опубликовано: 5 Января, 2022

Год сходства

Сходство Джаро - это мера сходства двух струн. Значение расстояния Джаро варьируется от 0 до 1. где 1 означает, что строки равны, а 0 означает отсутствие сходства между двумя строками.

Примеры:

Input: s1 = “CRATE”, s2 = “TRACE”;
Output: Jaro Similarity = 0.733333

Input: s1 = “DwAyNE”, s2 = “DuANE”;
Output: Jaro Similarity = 0.822222

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Алгоритм:
Сходство Джаро рассчитывается по следующей формуле

куда:

  • m - количество совпадающих символов
  • t - половина числа транспозиций
  • где | s1 | и | s2 | длина строки s1 и s2 соответственно

Считается, что символы совпадают, если они одинаковы и символы не дальше, чем

Транспонирование составляет половину количества совпадающих символов в обеих строках, но в другом порядке.

Расчет:

  • Пусть s1 = "arnab", s2 = "raanb", поэтому максимальное расстояние, до которого сопоставляется каждый символ, равно 1.
  • Очевидно, что в обеих строках есть 5 совпадающих символов, но порядок не совпадает, поэтому количество неупорядоченных символов равно 4, поэтому количество транспозиций равно 2.
  • Следовательно, подобие Джаро можно рассчитать следующим образом:
    Джаро Подобий = (1/3) * {(5/5) + (5/5) + (5-2) / 5} = 0,86667

Ниже представлена реализация описанного выше подхода.

CPP

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// Jaro Similarity of two strings
double jaro_distance(string s1, string s2)
{
// If the strings are equal
if (s1 == s2)
return 1.0;
// Length of two strings
int len1 = s1.length(),
len2 = s2.length();
// Maximum distance upto which matching
// is allowed
int max_dist = floor (max(len1, len2) / 2) - 1;
// Count of matches
int match = 0;
// Hash for matches
int hash_s1[s1.length()] = { 0 },
hash_s2[s2.length()] = { 0 };
// Traverse through the first string
for ( int i = 0; i < len1; i++) {
// Check if there is any matches
for ( int j = max(0, i - max_dist);
j < min(len2, i + max_dist + 1); j++)
// If there is a match
if (s1[i] == s2[j] && hash_s2[j] == 0) {
hash_s1[i] = 1;
hash_s2[j] = 1;
match++;
break ;
}
}
// If there is no match
if (match == 0)
return 0.0;
// Number of transpositions
double t = 0;
int point = 0;
// Count number of occurances
// where two characters match but
// there is a third matched character
// in between the indices
for ( int i = 0; i < len1; i++)
if (hash_s1[i]) {
// Find the next matched character
// in second string
while (hash_s2[point] == 0)
point++;
if (s1[i] != s2[point++])
t++;
}
t /= 2;
// Return the Jaro Similarity
return ((( double )match) / (( double )len1)
+ (( double )match) / (( double )len2)
+ (( double )match - t) / (( double )match))
/ 3.0;
}
// Driver code
int main()
{
string s1 = "CRATE" , s2 = "TRACE" ;
// Print jaro Similarity of two strings
cout << jaro_distance(s1, s2) << endl;
return 0;
}

Джава

// Java implementation of above approach
class GFG
{
// Function to calculate the
// Jaro Similarity of two Strings
static double jaro_distance(String s1, String s2)
{
// If the Strings are equal
if (s1 == s2)
return 1.0 ;
// Length of two Strings
int len1 = s1.length(),
len2 = s2.length();
// Maximum distance upto which matching
// is allowed
int max_dist = ( int ) (Math.floor(Math.max(len1, len2) / 2 ) - 1 );
// Count of matches
int match = 0 ;
// Hash for matches
int hash_s1[] = new int [s1.length()];
int hash_s2[] = new int [s2.length()];
// Traverse through the first String
for ( int i = 0 ; i < len1; i++)
{
// Check if there is any matches
for ( int j = Math.max( 0 , i - max_dist);
j < Math.min(len2, i + max_dist + 1 ); j++)
// If there is a match
if (s1.charAt(i) == s2.charAt(j) && hash_s2[j] == 0 )
{
hash_s1[i] = 1 ;
hash_s2[j] = 1 ;
match++;
break ;
}
}
// If there is no match
if (match == 0 )
return 0.0 ;
// Number of transpositions
double t = 0 ;
int point = 0 ;
// Count number of occurances
// where two characters match but
// there is a third matched character
// in between the indices
for ( int i = 0 ; i < len1; i++)
if (hash_s1[i] == 1 )
{
// Find the next matched character
// in second String
while (hash_s2[point] == 0 )
point++;
if (s1.charAt(i) != s2.charAt(point++) )
t++;
}
t /= 2 ;
// Return the Jaro Similarity
return ((( double )match) / (( double )len1)
+ (( double )match) / (( double )len2)
+ (( double )match - t) / (( double )match))
/ 3.0 ;
}
// Driver code
public static void main(String[] args)
{
String s1 = "CRATE" , s2 = "TRACE" ;
// Print jaro Similarity of two Strings
System.out.print(jaro_distance(s1, s2) + " " );
}
}
// This code is contributed by PrinciRaj1992

Python

# Python3 implementation of above approach
from math import floor, ceil
# Function to calculate the
# Jaro Similarity of two s
def jaro_distance(s1, s2):
# If the s are equal
if (s1 = = s2):
return 1.0
# Length of two s
len1 = len (s1)
len2 = len (s2)
# Maximum distance upto which matching
# is allowed
max_dist = floor( max (len1, len2) / 2 ) - 1
# Count of matches
match = 0
# Hash for matches
hash_s1 = [ 0 ] * len (s1)
hash_s2 = [ 0 ] * len (s2)
# Traverse through the first
for i in range (len1):
# Check if there is any matches
for j in range ( max ( 0 , i - max_dist),
min (len2, i + max_dist + 1 )):
# If there is a match
if (s1[i] = = s2[j] and hash_s2[j] = = 0 ):
hash_s1[i] = 1
hash_s2[j] = 1
match + = 1
break
# If there is no match
if (match = = 0 ):
return 0.0
# Number of transpositions
t = 0
point = 0
# Count number of occurances
# where two characters match but
# there is a third matched character
# in between the indices
for i in range (len1):
if (hash_s1[i]):
# Find the next matched character
# in second
while (hash_s2[point] = = 0 ):
point + = 1
if (s1[i] ! = s2[point]):
point + = 1
t + = 1
t = t / / 2
# Return the Jaro Similarity
return (match / len1 + match / len2 +
(match - t + 1 ) / match) / 3.0
# Driver code
s1 = "CRATE"
s2 = "TRACE"
# Prjaro Similarity of two s
print ( round (jaro_distance(s1, s2), 6 ))
# This code is contributed by mohit kumar 29

C #

// C# implementation of above approach
using System;
class GFG
{
// Function to calculate the
// Jaro Similarity of two Strings
static double jaro_distance( string s1, string s2)
{
// If the Strings are equal
if (s1 == s2)
return 1.0;
// Length of two Strings
int len1 = s1.Length ;
int len2 = s2.Length;
// Maximum distance upto which matching
// is allowed
int max_dist = ( int )(Math.Floor(( double )(
(Math.Max(len1, len2) / 2) - 1)));
// Count of matches
int match = 0;
// Hash for matches
int []hash_s1 = new int [s1.Length];
int []hash_s2 = new int [s2.Length];
// Traverse through the first String
for ( int i = 0; i < len1; i++)
{
// Check if there is any matches
for ( int j = Math.Max(0, i - max_dist);
j < Math.Min(len2, i + max_dist + 1); j++)
// If there is a match
if (s1[i] == s2[j] && hash_s2[j] == 0)
{
hash_s1[i] = 1;
hash_s2[j] = 1;
match++;
break ;
}
}
// If there is no match
if (match == 0)
return 0.0;
// Number of transpositions
double t = 0;
int point = 0;
// Count number of occurances
// where two characters match but
// there is a third matched character
// in between the indices
for ( int i = 0; i < len1; i++)
if (hash_s1[i] == 1)
{
// Find the next matched character
// in second String
while (hash_s2[point] == 0)
point++;
if (s1[i] != s2[point++] )
t++;
}
t /= 2;
// Return the Jaro Similarity
return ((( double )match) / (( double )len1)
+ (( double )match) / (( double )len2)
+ (( double )match - t) / (( double )match))
/ 3.0;
}
// Driver code
public static void Main()
{
string s1 = "CRATE" , s2 = "TRACE" ;
// Print jaro Similarity of two Strings
Console.WriteLine(jaro_distance(s1, s2));
}
}
// This code is contributed by AnkitRai01
Выход:
0,733333

Сходство Яро-Винклера

Сходство Яро-Винклера - это строковая метрика, измеряющая расстояние редактирования между двумя строками. Сходство Яро-Винклера очень похоже на Сходство Яро. Оба они различаются, когда префикс из двух строк совпадает. Сходство Яро-Винклера использует шкалу префикса «p», которая дает более точный ответ, когда строки имеют общий префикс до определенной максимальной длины l.

Примеры:

Input: s1 = “DwAyNE”, s2 = “DuANE”;
Output: Jaro-Winkler Similarity =0.84

Input: s1=”TRATE”, s2=”TRACE”;
Output: Jaro-Winkler similarity = 0.906667

Расчет:

  • Сходство Яро Винклера определяется следующим образом
    Sw = Sj + P * L * (1 - Sj)
    куда,
    • Sj, подобие jaro
    • Sw, есть подобие Джароуинклера
    • P - коэффициент масштабирования (по умолчанию 0,1)
    • L - длина совпадающего префикса до максимум 4 символов.
  • Пусть s1 = «арнаб», s2 = «аранб». Сходство Джаро двух струн составляет 0,933333 (из вышеприведенного расчета).
  • Длина префикса соответствия равна 2, и мы принимаем коэффициент масштабирования равным 0,1.
  • Подставляя в формулу;
    Сходство Джаро-Винклера = 0,9333333 + 0,1 * 2 * (1-0,9333333) = 0,946667

Ниже представлена реализация описанного выше подхода.

CPP

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// Jaro Similarity of two strings
double jaro_distance(string s1, string s2)
{
// If the strings are equal
if (s1 == s2)
return 1.0;
// Length of two strings
int len1 = s1.length(),
len2 = s2.length();
if (len1 == 0 || len2 == 0)
return 0.0;
// Maximum distance upto which matching
// is allowed
int max_dist = floor (max(len1, len2) / 2) - 1;
// Count of matches
int match = 0;
// Hash for matches
int hash_s1[s1.length()] = { 0 },
hash_s2[s2.length()] = { 0 };
// Traverse through the first string
for ( int i = 0; i < len1; i++) {
// Check if there is any matches
for ( int j = max(0, i - max_dist);
j < min(len2, i + max_dist + 1); j++)
// If there is a match
if (s1[i] == s2[j] && hash_s2[j] == 0) {
hash_s1[i] = 1;
hash_s2[j] = 1;
match++;
break ;
}
}
// If there is no match

РЕКОМЕНДУЕМЫЕ СТАТЬИ