機器學習中的數學——距離定義(十二):編輯距離(Edit Distance,Levenshtein Distance)

von Neumann 2022-01-08 04:20:40 阅读数:550

十二 edit distance levenshtein distance

編輯距離(Edit Distance,Levenshtein Distance)是一個度量兩個字符序列之間差异的字符串度量標准,兩個單詞之間的編輯距離是將一個字符串轉換為另一個字符串所需的單字符編輯(插入、删除或替換)的最小數量。編輯距離由蘇聯數學家Vladimir Levenshtein發明。

對於兩個字符串 x x x y y y,長度分別為 ∣ x ∣ |x| x ∣ y ∣ |y| y,字符串 x x x的前 i i i個字符和字符串 y y y的前 j j j個字符的編輯距離為:
ED x , y ( i , j ) = { max ⁡ ( i , j ) , min ⁡ ( i , j ) = 0 min ⁡ ( ED x , y ( i − 1 , j ) + I ( i , j ) , ED x , y ( i , j − 1 ) + I ( i , j ) , ED x , y ( i , j ) + I ( i , j ) ) , min ⁡ ( i , j ) ≠ 0 \text{ED}_{x, y}(i, j)= \left\{ \begin{aligned} &\max{(i, j)} &, \min{(i, j)}=0\\ &\min{ {(\text{ED}_{x, y}(i-1, j)+I(i, j), \text{ED}_{x, y}(i, j-1)+I(i, j), \text{ED}_{x, y}(i, j)+I(i, j))}} &, \min{(i, j)}\neq0\\ \end{aligned} \right. EDx,y(i,j)={ max(i,j)min(EDx,y(i1,j)+I(i,j),EDx,y(i,j1)+I(i,j),EDx,y(i,j)+I(i,j)),min(i,j)=0,min(i,j)=0
其中,當 x i = y j x_i=y_j xi=yj時, I ( i , j ) = 0 I(i, j)=0 I(i,j)=0,否則 I ( i , j ) = 1 I(i, j)=1 I(i,j)=1

下面我們來看一下編輯距離的Python實現:

def EditDistance(x, y):
dp = np.zeros((len(x) + 1,len(y) + 1))
for i in range(len(x) + 1):
dp[i][0] = i
for j in range(len(y) + 1):
dp[0][j] = j
for i in range(1, len(x) + 1):
for j in range(1, len(y) + 1):
delta = 0 if x[i-1] == y[j-1] else 1
dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))
return int(dp[len(x)][len(y)])
版权声明:本文为[von Neumann]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080420395486.html