https en wikipedia orgwikijaroe28093winklerdistance def jarowinklerstr1 str str2 str float def getmatchedcharactersstr1 str str2 str str matched limit minlenstr1 lenstr2 2 for i l in enumeratestr1 left intmax0 i limit right intmini limit 1 lenstr2 if l in str2left right matched appendl str2 fstr20 str2 indexl str2str2 indexl 1 return joinmatched matching characters matching1 getmatchedcharactersstr1 str2 matching2 getmatchedcharactersstr2 str1 matchcount lenmatching1 transposition transpositions lenc1 c2 for c1 c2 in zipmatching1 matching2 if c1 c2 2 if not matchcount jaro 0 0 else jaro 1 3 matchcount lenstr1 matchcount lenstr2 matchcount transpositions matchcount common prefix up to 4 characters prefixlen 0 for c1 c2 in zipstr1 4 str2 4 if c1 c2 prefixlen 1 else break return jaro 0 1 prefixlen 1 jaro if name main import doctest doctest testmod printjarowinklerhello world jaro winkler distance is a string metric measuring an edit distance between two sequences output value is between 0 0 and 1 0 jaro_winkler martha marhta 0 9611111111111111 jaro_winkler crate trace 0 7333333333333334 jaro_winkler test dbdbdbdb 0 0 jaro_winkler test test 1 0 jaro_winkler hello world hello w0rld 0 6363636363636364 jaro_winkler test 0 0 jaro_winkler hello world 0 4666666666666666 jaro_winkler hell o world 0 4365079365079365 matching characters transposition common prefix up to 4 characters
def jaro_winkler(str1: str, str2: str) -> float:
    

    def get_matched_characters(_str1: str, _str2: str) -> str:
        matched = []
        limit = min(len(_str1), len(_str2)) // 2
        for i, l in enumerate(_str1):
            left = int(max(0, i - limit))
            right = int(min(i + limit + 1, len(_str2)))
            if l in _str2[left:right]:
                matched.append(l)
                _str2 = f"{_str2[0:_str2.index(l)]} {_str2[_str2.index(l) + 1:]}"

        return "".join(matched)

    
    matching_1 = get_matched_characters(str1, str2)
    matching_2 = get_matched_characters(str2, str1)
    match_count = len(matching_1)

    
    transpositions = (
        len([(c1, c2) for c1, c2 in zip(matching_1, matching_2) if c1 != c2]) // 2
    )

    if not match_count:
        jaro = 0.0
    else:
        jaro = (
            1
            / 3
            * (
                match_count / len(str1)
                + match_count / len(str2)
                + (match_count - transpositions) / match_count
            )
        )

    
    prefix_len = 0
    for c1, c2 in zip(str1[:4], str2[:4]):
        if c1 == c2:
            prefix_len += 1
        else:
            break

    return jaro + 0.1 * prefix_len * (1 - jaro)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    print(jaro_winkler("hello", "world"))