-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathedit_distance.py
100 lines (75 loc) · 2.84 KB
/
edit_distance.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
def count_memo(string1, string2, p1, p2, cache):
if p1 >= len(string1):
return len(string2) - p2
if p2 >= len(string2):
return len(string1) - p1
if cache[p1][p2] is not None:
return cache[p1][p2]
if string1[p1] == string2[p2]:
# copy
cache[p1][p2] = count_memo(string1, string2, p1 + 1, p2 + 1, cache)
else:
# replace
replace = count_memo(string1, string2, p1 + 1, p2 + 1, cache) + 1
# delete
delete = count_memo(string1, string2, p1, p2 + 1, cache) + 1
# insert
insert = count_memo(string1, string2, p1 + 1, p2, cache) + 1
cache[p1][p2] = min(insert, delete, replace)
return cache[p1][p2]
def count_table(string1, string2):
# create a table
length1 = len(string1)
length2 = len(string2)
table = [[0 for _ in range(length2 + 1)] for _ in range(length1 + 1)]
# fill up first row and first column
for i in range(length1 + 1):
table[i][0] = i
for j in range(length2 + 1):
table[0][j] = j
for i in range(1, length1 + 1):
for j in range(1, length2 + 1):
if string1[i - 1] == string2[j - 1]:
table[i][j] = min(table[i][j - 1] + 1, table[i - 1][j] + 1, table[i - 1][j - 1])
else:
table[i][j] = min(table[i][j - 1] + 1, table[i - 1][j] + 1, table[i - 1][j - 1] + 1)
return table[length1][length2]
def edit_memo(string1, string2):
if len(string1) == 0:
return len(string2)
if len(string2) == 0:
return len(string1)
# construct the table
cache = [[None for _ in range(len(string2) + 1)] for _ in range(len(string1) + 1)]
return count_memo(string1, string2, 0, 0, cache)
def edit_table(string1, string2):
if len(string1) == 0:
return len(string2)
if len(string2) == 0:
return len(string1)
return count_table(string1, string2)
def count_brute_force(string1, string2, p1, p2):
if p1 >= len(string1):
return len(string2) - p2
if p2 >= len(string2):
return len(string1) - p1
if string1[p1] == string2[p2]:
# copy
return count_brute_force(string1, string2, p1 + 1, p2 + 1)
else:
# replace
replace = count_brute_force(string1, string2, p1 + 1, p2 + 1) + 1
# delete
delete = count_brute_force(string1, string2, p1, p2 + 1) + 1
# insert
insert = count_brute_force(string1, string2, p1 + 1, p2) + 1
return min(insert, delete, replace)
def edit_brute_force(string1, string2):
if len(string1) == 0:
return len(string2)
if len(string2) == 0:
return len(string1)
return count_brute_force(string1, string2, 0, 0)
print(f"edit_brute_force: {edit_brute_force('paris', 'arid')}")
print(f"edit_memo: {edit_memo('paris', 'arid')}")
print(f"edit_table: {edit_table('paris', 'arid')}")