-
Notifications
You must be signed in to change notification settings - Fork 506
Expand file tree
/
Copy pathedit_distance.py
More file actions
289 lines (221 loc) · 7.71 KB
/
edit_distance.py
File metadata and controls
289 lines (221 loc) · 7.71 KB
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
"""
Author: ADWAITA JADHAV
Created On: 4th October 2025
Edit Distance (Levenshtein Distance) Algorithm
Time Complexity: O(m * n) where m and n are lengths of the two strings
Space Complexity: O(m * n) or O(min(m, n)) with space optimization
The edit distance between two strings is the minimum number of single-character
edits (insertions, deletions, or substitutions) required to change one string
into another.
"""
import inspect
def edit_distance(str1, str2):
"""
Calculate the edit distance between two strings using dynamic programming
:param str1: first string
:param str2: second string
:return: minimum edit distance
"""
m, n = len(str1), len(str2)
# Create DP table
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize base cases
for i in range(m + 1):
dp[i][0] = i # Delete all characters from str1
for j in range(n + 1):
dp[0][j] = j # Insert all characters to get str2
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # No operation needed
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # Delete
dp[i][j - 1], # Insert
dp[i - 1][j - 1] # Replace
)
return dp[m][n]
def edit_distance_optimized(str1, str2):
"""
Calculate edit distance with space optimization (O(min(m, n)) space)
:param str1: first string
:param str2: second string
:return: minimum edit distance
"""
# Make str1 the shorter string for space optimization
if len(str1) > len(str2):
str1, str2 = str2, str1
m, n = len(str1), len(str2)
# Use only two rows instead of full matrix
prev = list(range(m + 1))
curr = [0] * (m + 1)
for j in range(1, n + 1):
curr[0] = j
for i in range(1, m + 1):
if str1[i - 1] == str2[j - 1]:
curr[i] = prev[i - 1]
else:
curr[i] = 1 + min(prev[i], curr[i - 1], prev[i - 1])
prev, curr = curr, prev
return prev[m]
def edit_distance_with_operations(str1, str2):
"""
Calculate edit distance and return the sequence of operations
:param str1: first string
:param str2: second string
:return: tuple (distance, operations) where operations is list of (operation, char, position)
"""
m, n = len(str1), len(str2)
# Create DP table
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize base cases
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # Delete
dp[i][j - 1], # Insert
dp[i - 1][j - 1] # Replace
)
# Backtrack to find operations
operations = []
i, j = m, n
while i > 0 or j > 0:
if i > 0 and j > 0 and str1[i - 1] == str2[j - 1]:
i -= 1
j -= 1
elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
operations.append(('replace', str2[j - 1], i - 1))
i -= 1
j -= 1
elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
operations.append(('delete', str1[i - 1], i - 1))
i -= 1
elif j > 0 and dp[i][j] == dp[i][j - 1] + 1:
operations.append(('insert', str2[j - 1], i))
j -= 1
operations.reverse()
return dp[m][n], operations
def similarity_ratio(str1, str2):
"""
Calculate similarity ratio between two strings (0.0 to 1.0)
:param str1: first string
:param str2: second string
:return: similarity ratio (1.0 means identical, 0.0 means completely different)
"""
if not str1 and not str2:
return 1.0
max_len = max(len(str1), len(str2))
if max_len == 0:
return 1.0
distance = edit_distance(str1, str2)
return 1.0 - (distance / max_len)
def is_one_edit_away(str1, str2):
"""
Check if two strings are one edit away from each other
:param str1: first string
:param str2: second string
:return: True if one edit away, False otherwise
"""
m, n = len(str1), len(str2)
# If length difference is more than 1, they can't be one edit away
if abs(m - n) > 1:
return False
# Make str1 the shorter or equal length string
if m > n:
str1, str2 = str2, str1
m, n = n, m
i = j = 0
found_difference = False
while i < m and j < n:
if str1[i] != str2[j]:
if found_difference:
return False
found_difference = True
if m == n:
i += 1 # Replace operation
# For insertion, only increment j
else:
i += 1
j += 1
return True
def longest_common_subsequence_length(str1, str2):
"""
Calculate the length of longest common subsequence
:param str1: first string
:param str2: second string
:return: length of LCS
"""
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
def apply_operations(str1, operations):
"""
Apply a sequence of edit operations to transform str1
:param str1: original string
:param operations: list of operations from edit_distance_with_operations
:return: transformed string
"""
result = list(str1)
for operation, char, pos in operations:
if operation == 'insert':
result.insert(pos, char)
elif operation == 'delete':
if pos < len(result):
result.pop(pos)
elif operation == 'replace':
if pos < len(result):
result[pos] = char
return ''.join(result)
def hamming_distance(str1, str2):
"""
Calculate Hamming distance between two strings of equal length
:param str1: first string
:param str2: second string
:return: Hamming distance or -1 if strings have different lengths
"""
if len(str1) != len(str2):
return -1
return sum(c1 != c2 for c1, c2 in zip(str1, str2))
def find_closest_strings(target, candidates, max_distance=None):
"""
Find strings from candidates that are closest to target
:param target: target string
:param candidates: list of candidate strings
:param max_distance: maximum allowed edit distance (None for no limit)
:return: list of (string, distance) tuples sorted by distance
"""
if not candidates:
return []
distances = []
for candidate in candidates:
distance = edit_distance(target, candidate)
if max_distance is None or distance <= max_distance:
distances.append((candidate, distance))
return sorted(distances, key=lambda x: x[1])
def time_complexities():
"""
Return information on time complexity
:return: string
"""
return "Best Case: O(m * n), Average Case: O(m * n), Worst Case: O(m * n)"
def get_code():
"""
Easily retrieve the source code of the edit_distance function
:return: source code
"""
return inspect.getsource(edit_distance)