Edit Distance Python源碼及支援包的實作
-
- 編輯距離
編輯距離
又稱Levenshtein距離(萊文斯坦距離也叫做Edit Distance)指兩個字串之間,由一個轉成另一個所需的最少編輯操作次數,如果它們的距離越大,說明它們越是不同。許可的編輯操作包括将一個字元替換成另一個字元,插入一個字元,删除一個字元。它可以用來做DNA分析,拼寫檢查,抄襲識别等。編輯操作隻有三種插入、删除、替換三種操作。
python
代碼片段如下:
import numpy as np
import editdistance
import math
"""
author: zhenyu wu
time: 2019/12/03 15:41
function: 編輯距離計算函數
params:
str1: 字元串1
str2:字元串2
return:
兩個字元串的相似度計算結果
"""
def edit_distance(str1, str2):
m, n = len(str1), len(str2)
if m==0 and n!=0:
return n, 1-n/max(m, n)
elif m!=0 and n==0:
return m, 1-m/max(m, n)
elif m==0 and n==0:
try:
1-0/0
except ZeroDivisionError as z:
print("兩個字元串不能同時為空")
return math.nan, math.nan
else:
d = np.zeros((n+1, m+1))
d[0] = np.arange(m+1)
d[:, 0] = np.arange(n+1)
for i in range(1, n+1):
for j in range(1, m+1):
if str1[j-1]==str2[i-1]:
temp = 0
else:
temp = 1
d[i, j] = min(d[i-1, j]+1, d[i, j-1]+1, d[i-1, j-1]+temp)
return d[n, m], 1-d[n, m]/max(m, n)
if __name__ == '__main__':
str1 = '1010101010000101000010011001010101101'
str2 = '101010111010101010111101010'
dist, result = edit_distance(str1, str2)
print('My Algorithm - Edit Distance: %.0f, Similarity: %f' % (dist, result))
dist = editdistance.distance(str1, str2)
print('Python Package - Edit Distance: %.0f, Similarity: %f' % (dist, 1-dist/max(len(str1), len(str2))))
運作結果
如下:
My Algorithm - Edit Distance: 12, Similarity: 0.675676
Python Package - Edit Distance: 12, Similarity: 0.675676
https://github.com/wzy6642/EditDistance.