-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlevenshtein_damerau_threshold.py
117 lines (94 loc) · 3.58 KB
/
levenshtein_damerau_threshold.py
1
2
3
4
5
6
7
8
9
10
11
12
13
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import numpy as np
def dp_levenshtein_backwards(x, y, threshold = 4):
if(abs(len(x) - len(y)) > threshold):
return threshold + 1
D = np.zeros((len(x) + 1, len(y) + 1))
for i in range(1, len(x) + 1):
D[i, 0] = D[i - 1, 0] + 1
for j in range(1, len(y) + 1):
D[0, j] = D[0, j - 1] + 1
for i in range(1, len(x) + 1):
D[i, j] = min(
D[i - 1, j] + 1,
D[i, j - 1] + 1,
D[i - 1, j - 1] + (x[i-1] != y[j-1])
)
if(min(D[:, j]) > threshold):
return threshold + 1
return D[len(x), len(y)]
def dp_restricted_damerau_backwards(x, y, threshold = 4):
if(abs(len(x) - len(y)) > threshold):
return threshold + 1
D = np.zeros((len(x) + 1, len(y) + 1))
for i in range(1, len(x) + 1):
D[i, 0] = D[i - 1, 0] + 1
for j in range(1, len(y) + 1):
D[0, j] = D[0, j - 1] + 1
for i in range(1, len(x) + 1):
D[i, j] = min(
D[i - 1, j] + 1,
D[i, j - 1] + 1,
D[i - 1, j - 1] + (x[i-1] != y[j-1])
)
if i > 1 and j > 1 and x[i - 2] == y[j - 1] and x[i - 1] == y[j-2]:
D[i, j] = min(
D[i, j],
D[i - 2, j - 2] + 1
)
if(min(D[:, j]) > threshold):
return threshold + 1
return D[len(x), len(y)]
def dp_intermediate_damerau_backwards(x, y, threshold = 4):
if(abs(len(x) - len(y)) > threshold):
return threshold + 1
D = np.zeros((len(x) + 1, len(y) + 1))
for i in range(1, len(x) + 1):
D[i, 0] = D[i - 1, 0] + 1
for j in range(1, len(y) + 1):
D[0, j] = D[0, j - 1] + 1
for i in range(1, len(x) + 1):
D[i, j] = min(
D[i - 1, j] + 1,
D[i, j - 1] + 1,
D[i - 1, j - 1] + (x[i-1] != y[j-1])
)
if i > 1 and j > 1 and x[i - 2] == y[j - 1] and x[i - 1] == y[j-2]:
D[i, j] = min(
D[i, j],
D[i - 2, j - 2] + 1
)
if(i > 2 and j > 1 and x[i - 3] == y[j - 1] and x[i - 1] == y[j - 2]):
D[i, j] = min(
D[i, j],
D[i - 2, j - 2] + 1
)
if(i > 1 and j > 2 and x[i - 1] == y[j - 3] and x[i - 2] == y[j - 1]):
D[i, j] = min(
D[i, j],
D[i - 2, j - 2] + 1
)
if(min(D[:, j]) > threshold):
return threshold + 1
return D[len(x), len(y)]
# test = [("cazador","caazdor"),
# ("algoritmo","algortximo"),
# ("algoritmo","lagortimo"),
# ("algoritmo","agaloritom"),
# ("algoritmo","algormio"),
# ("acb","ba")]
# for x,y in test:
# print(f"{x:12} {y:12}",end="")
# for dist,name in ((dp_levenshtein_backwards,"levenshtein"),
# (dp_restricted_damerau_backwards,"restricted"),
# (dp_intermediate_damerau_backwards,"intermediate")):
# print(f" {name} {dist(x,y):2}",end="")
# print()
"""
Salida del programa:
algoritmo algortimo levenshtein 2 restricted 1 intermediate 1
algoritmo algortximo levenshtein 3 restricted 3 intermediate 2
algoritmo lagortimo levenshtein 4 restricted 2 intermediate 2
algoritmo agaloritom levenshtein 5 restricted 4 intermediate 3
algoritmo algormio levenshtein 3 restricted 3 intermediate 2
acb ba levenshtein 3 restricted 3 intermediate 2
"""