14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
|
'œ': 'oe', 'æ': 'ae',
})
def cleanWord (sWord):
"word simplication before calculating distance between words"
return sWord.lower().translate(_xTransChars).replace("eau", "o").replace("au", "o")
def distanceDamerauLevenshtein (s1, s2):
"distance of Damerau-Levenshtein between <s1> and <s2>"
# https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
d = {}
nLen1 = len(s1)
nLen2 = len(s2)
for i in range(-1, nLen1+1):
d[i, -1] = i + 1
for j in range(-1, nLen2+1):
d[-1, j] = j + 1
for i in range(nLen1):
for j in range(nLen2):
nCost = 0 if s1[i] == s2[j] else 1
d[i, j] = min(
d[i-1, j] + 1, # Deletion
d[i, j-1] + 1, # Insertion
d[i-1, j-1] + nCost, # Substitution
)
if i and j and s1[i] == s2[j-1] and s1[i-1] == s2[j]:
d[i, j] = min(d[i, j], d[i-2, j-2] + nCost) # Transposition
return d[nLen1-1, nLen2-1]
def showDistance (s1, s2):
s1b = cleanWord(s1);
s2b = cleanWord(s2);
print(f"Distance: {s1} / {s2} = {distanceDamerauLevenshtein(s1, s2)}")
print(f"Distance: {s1b} / {s2b} = {distanceDamerauLevenshtein(s1b, s2b)}")
# Method: Remove Useless Chars
_dVovels = {
'a': '', 'e': '', 'i': '', 'o': '', 'u': '', 'y': '',
'à': '', 'é': '', 'î': '', 'ô': '', 'û': '', 'ÿ': '',
'â': '', 'è': '', 'ï': '', 'ö': '', 'ù': '', 'ŷ': '',
'ä': '', 'ê': '', 'í': '', 'ó': '', 'ü': '', 'ý': '',
'á': '', 'ë': '', 'ì': '', 'ò': '', 'ú': '', 'ỳ': '',
'ā': '', 'ē': '', 'ī': '', 'ō': '', 'ū': '', 'ȳ': '',
'h': '', 'œ': '', 'æ': ''
}
_xTransVovels = str.maketrans(_dVovels)
aVovels = frozenset(_dVovels.keys())
def shrinkWord (sWord):
"remove vovels and h"
return sWord[0:1].replace("h", "") + sWord[1:].translate(_xTransVovels)
|