TheAlgorithms-Python

1
"""https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance"""
2

3

4
def jaro_winkler(str1: str, str2: str) -> float:
5
    """
6
    Jaro–Winkler distance is a string metric measuring an edit distance between two
7
    sequences.
8
    Output value is between 0.0 and 1.0.
9

10
    >>> jaro_winkler("martha", "marhta")
11
    0.9611111111111111
12
    >>> jaro_winkler("CRATE", "TRACE")
13
    0.7333333333333334
14
    >>> jaro_winkler("test", "dbdbdbdb")
15
    0.0
16
    >>> jaro_winkler("test", "test")
17
    1.0
18
    >>> jaro_winkler("hello world", "HeLLo W0rlD")
19
    0.6363636363636364
20
    >>> jaro_winkler("test", "")
21
    0.0
22
    >>> jaro_winkler("hello", "world")
23
    0.4666666666666666
24
    >>> jaro_winkler("hell**o", "*world")
25
    0.4365079365079365
26
    """
27

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

38
        return "".join(matched)
39

40
    # matching characters
41
    matching_1 = get_matched_characters(str1, str2)
42
    matching_2 = get_matched_characters(str2, str1)
43
    match_count = len(matching_1)
44

45
    # transposition
46
    transpositions = (
47
        len([(c1, c2) for c1, c2 in zip(matching_1, matching_2) if c1 != c2]) // 2
48
    )
49

50
    if not match_count:
51
        jaro = 0.0
52
    else:
53
        jaro = (
54
            1
55
            / 3
56
            * (
57
                match_count / len(str1)
58
                + match_count / len(str2)
59
                + (match_count - transpositions) / match_count
60
            )
61
        )
62

63
    # common prefix up to 4 characters
64
    prefix_len = 0
65
    for c1, c2 in zip(str1[:4], str2[:4]):
66
        if c1 == c2:
67
            prefix_len += 1
68
        else:
69
            break
70

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

73

74
if __name__ == "__main__":
75
    import doctest
76

77
    doctest.testmod()
78
    print(jaro_winkler("hello", "world"))
79