赞
踩
(本文主要是宗成庆老师的统计自然语言处理笔记,以代码实现为主)
pip install nltk
from nltk.metrics import edit_distance as ed
str1= "Levenshtein"
str2= "lEvensting"
print(ed(str1,str2))
此处可以查看源码:https://www.nltk.org/_modules/nltk/metrics/distance.html#edit_distance
2, 手写代码—python
参考:
https://blog.csdn.net/koibiki/article/details/83031788
https://www.cnblogs.com/sumuncle/p/5632032.html
https://www.cnblogs.com/robert-dlut/p/4077540.html
https://blog.csdn.net/weixin_41665541/article/details/84942196
思想:最小编辑距离相当于有两个字符串str1和str2,现在要将str1(主)改变为str2需要的最小删除,插入和替换的次数,(我括号里面写‘主’是表示对str1操作变成str2,而不是对str2操作变成str1,当然两者是等价的,这里是为了表述简单起见)。从下面式子
Edit(i,j)表示字符串i变成字符串j的最小编辑距离。(注意i是主,即表示对i操作)
递归的思想可以参考C程序设计第四版P184以及189页汉诺塔问题,这里相当于说:要问我一共需要多少步骤可以使得i变成j,那么你如果告诉我第i-1变成j需要多少步骤(或者i变成j-1需要多少步骤,或者i-1变成j-1需要多少步骤)我就能告诉你这个答案。因为你告诉我需要多少步骤之后,我只要对比最后一个字符是不是相等就可以了。
所以你要问我一共需要多少步骤才能将i变成j,你就告诉我前面的k个步骤是多少,即k等于多少,我就立马可以给你答案;而你问我k等于多少,我就只要你告诉我k-1前面是多少步骤,我立马就可以告诉你k个步骤;而要知道k-1就要知道k-2之前的步骤,…一直到第一步(即相当于i=0或j=0的情况)为止。这就是递归的思想。
所以这个问题实际上是个递归的问题。
如上图,相当于你如果告诉了我红框中的2,3,4那三个位置的数(即K),我就可以告诉你最后一个数是多少(即右下角的3那个位置);而我要知道2那个位置,你就得告诉我黄色框的那三个位置(左,左上,上)的数是多少,同样,我要知道红框3那儿的位置需要多少步骤,你就得告诉我蓝色框的步骤要多少;紫色框对应4的那个位置;这样一层层往里面推进一直到第一个即终止条件(这个过程叫做回溯),再从终止条件开始反推就可以得到最右下角的答案(这个过程叫做递推)。所以递归问题就是回溯+递推
(本来写了一堆详细解释的,坑货CSDN莫名其妙就不见了,既然如此,那就不说了,给出代码吧)
python代码
import numpy as np def edit_distance(word1, word2): lens1=len(word1) lens2=len(word2) dp = np.zeros((lens1+1,lens2+1)) # initialization for i in range(lens1+1): dp[i][0] = i for j in range(lens2+1): dp[0][j] = j # find the minimum value of the left, the top and the top left value. for i in range(1,lens1+1): for j in range(1,lens2+1): if word1[i-1]==word2[j-1]: temp = 0 else: temp = 1 dp[i][j] = min(dp[i-1][j-1]+temp, dp[i-1][j]+1, dp[i][j-1]+1) return dp[lens1][lens2] print(edit_distance('hello','how'))
C代码
#define _crt_secure_no_warnings #include<stdio.h> #include<math.h> #include<string.h> using namespace std; int main() { int edit_distance(char word1[], char word2[]); char word1[10] = { "hello" }; char word2[10] = { "how" }; printf("%d\n", edit_distance(word1,word2)); return 0; } int edit_distance(char word1[], char word2[]) { int min(int a, int b); int lens1 = strlen(word1); int lens2 = strlen(word2); int i, j,temp; int str[10][20]; for (i = 0; i < lens1+1; i++) str[i][0] = i; for (j = 0; j < lens2 + 1; j++) str[0][j] = j; for (i = 1; i < lens1 + 1; i++) for (j = 1; j < lens2 + 1; j++) { if (word1[i - 1] == word2[j - 1]) temp = 0; else temp = 1; str[i][j] = min(str[i - 1][j - 1] + temp, min(str[i - 1][j] + 1, str[i][j - 1] + 1)); } return(str[lens1][lens2]); } int min(int a, int b) { return(a > b ? b : a); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。