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

Опубликовано: 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
                            
                    
                                            Technical Scripter
                                            Алгоритмы
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКоличество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023

    


        
                    < PROGLER >

                

                    Общее
Контакты
Политика конфиденциальности

                    Обучение
Блог

                

                © progler.ru 2025. Все права защищены.
            

    