字符串相似度算法Python实现
#!/usr/bin/env pythondef levenshtein(a,b):
"Calculates the Levenshtein distance between a and b."
n, m = len(a), len(b)
if n > m:
# Make sure n <= m, to use O(min(n,m)) space
a,b = b,a
n,m = m,n
current = range(n+1)
for i in range(1,m+1):
previous, current = current, +*n
for j in range(1,n+1):
add, delete = previous+1, current+1
change = previous
if a != b:
change = change + 1
current = min(add, delete, change)
return current
def levenshtein_distance(first, second):
"""Find the Levenshtein distance between two strings."""
if len(first) > len(second):
first, second = second, first
if len(second) == 0:
return len(first)
first_length = len(first) + 1
second_length = len(second) + 1
distance_matrix =
for i in range(1, first_length):
for j in range(1, second_length):
deletion = distance_matrix + 1
insertion = distance_matrix + 1
substitution = distance_matrix
if first != second:
substitution += 1
distance_matrix = min(insertion, deletion, substitution)
return distance_matrix
if __name__=="__main__":
#from sys import argv
first = "abcabcaa"
second = "cbsaaecaa"
print levenshtein(first,second)
print levenshtein_distance(first,second)
页:
[1]