Jaro and Jaro | Python3 implementation of above approach ; Function to calculate the Jaro Similarity of two strings ; If the strings are equal ; Length of two strings ; Maximum distance upto which matching is allowed ; Count of matches ; Hash for matches ; Traverse through the first string ; Check if there is any matches ; If there is a match ; If there is no match ; Number of transpositions ; Count number of occurrences where two characters match but there is a third matched character in between the indices ; Find the next matched character in second string ; Return the Jaro Similarity ; Jaro Winkler Similarity ; If the jaro Similarity is above a threshold ; Find the length of common prefix ; If the characters match ; Else break ; Maximum of 4 characters are allowed in prefix ; Calculate jaro winkler Similarity ; Driver code ; Print Jaro - Winkler Similarity of two strings
from math import floor NEW_LINE def jaro_distance ( s1 , s2 ) : NEW_LINE INDENT if ( s1 == s2 ) : NEW_LINE INDENT return 1.0 ; NEW_LINE DEDENT len1 = len ( s1 ) ; NEW_LINE len2 = len ( s2 ) ; NEW_LINE if ( len1 == 0 or len2 == 0 ) : NEW_LINE INDENT return 0.0 ; NEW_LINE DEDENT max_dist = ( max ( len ( s1 ) , len ( s2 ) ) // 2 ) - 1 ; NEW_LINE match = 0 ; NEW_LINE hash_s1 = [ 0 ] * len ( s1 ) ; NEW_LINE hash_s2 = [ 0 ] * len ( s2 ) ; NEW_LINE for i in range ( len1 ) : NEW_LINE INDENT for j in range ( max ( 0 , i - max_dist ) , min ( len2 , i + max_dist + 1 ) ) : NEW_LINE INDENT if ( s1 [ i ] == s2 [ j ] and hash_s2 [ j ] == 0 ) : NEW_LINE INDENT hash_s1 [ i ] = 1 ; NEW_LINE hash_s2 [ j ] = 1 ; NEW_LINE match += 1 ; NEW_LINE break ; NEW_LINE DEDENT DEDENT DEDENT if ( match == 0 ) : NEW_LINE INDENT return 0.0 ; NEW_LINE DEDENT t = 0 ; NEW_LINE point = 0 ; NEW_LINE for i in range ( len1 ) : NEW_LINE INDENT if ( hash_s1 [ i ] ) : NEW_LINE INDENT while ( hash_s2 [ point ] == 0 ) : NEW_LINE INDENT point += 1 ; NEW_LINE DEDENT if ( s1 [ i ] != s2 [ point ] ) : NEW_LINE INDENT point += 1 ; NEW_LINE t += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT point += 1 ; NEW_LINE DEDENT DEDENT t /= 2 ; NEW_LINE DEDENT return ( ( match / len1 + match / len2 + ( match - t ) / match ) / 3.0 ) ; NEW_LINE DEDENT def jaro_Winkler ( s1 , s2 ) : NEW_LINE INDENT jaro_dist = jaro_distance ( s1 , s2 ) ; NEW_LINE if ( jaro_dist > 0.7 ) : NEW_LINE INDENT prefix = 0 ; NEW_LINE for i in range ( min ( len ( s1 ) , len ( s2 ) ) ) : NEW_LINE INDENT if ( s1 [ i ] == s2 [ i ] ) : NEW_LINE INDENT prefix += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT break ; NEW_LINE DEDENT DEDENT prefix = min ( 4 , prefix ) ; NEW_LINE jaro_dist += 0.1 * prefix * ( 1 - jaro_dist ) ; NEW_LINE DEDENT return jaro_dist ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s1 = " TRATE " ; s2 = " TRACE " ; NEW_LINE print ( " Jaro - Winkler ▁ Similarity ▁ = " , jaro_Winkler ( s1 , s2 ) ) ; NEW_LINE DEDENT