You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
35 lines
808 B
Python
35 lines
808 B
Python
# https://en.wikipedia.org/wiki/Levenshtein_distance
|
|
import time
|
|
import random
|
|
|
|
|
|
def levenstein_distance(a, b):
|
|
m = len(a)
|
|
n = len(b)
|
|
dp = [[0] * (n + 1) for i in range(m + 1)]
|
|
for i in range(m + 1):
|
|
dp[i][0] = i
|
|
for j in range(n + 1):
|
|
dp[0][j] = j
|
|
for i in range(m):
|
|
for j in range(n):
|
|
if a[i] == b[j]:
|
|
dp[i + 1][j + 1] = dp[i][j]
|
|
else:
|
|
dp[i + 1][j + 1] = 1 + min(dp[i][j], dp[i + 1][j], dp[i][j + 1])
|
|
return dp[m][n]
|
|
|
|
|
|
def test():
|
|
start = time.time()
|
|
print(levenstein_distance('abc', 'ab'))
|
|
print(levenstein_distance(random_string(1000), random_string(1000)))
|
|
print(time.time() - start)
|
|
|
|
|
|
def random_string(len):
|
|
return ''.join(random.choice('ab') for _ in range(len))
|
|
|
|
|
|
test()
|