持续更新中…
(本文主要是宗成庆老师的统计自然语言处理笔记，以代码实现为主)
NLP目录
持续更新中... 第三章：形式语言与自动机1.自动机在自然语言处理中的应用1.1编辑距离第三章：形式语言与自动机
1.自动机在自然语言处理中的应用
1.1编辑距离
The edit distance is the number of characters that need to be substituted, inserted, or deleted, to transform s1 into s2.实现编辑距离的计算
1，调用函数包----这是最简单的方法（入门不建议调用包，先自己手动写）
（没有natural language toolkit）先
pip install nltk
from nltk.metrics import edit_distance as edstr1= "Levenshtein"str2= "lEvensting"print(ed(str1,str2))
此处可以查看源码：/_modules/nltk/metrics/distance.html#edit_distance
2, 手写代码—python
参考：
/koibiki/article/details/83031788
/sumuncle/p/5632032.html
/robert-dlut/p/4077540.html
/weixin_41665541/article/details/84942196
思想：最小编辑距离相当于有两个字符串str1和str2，现在要将str1(主)改变为str2需要的最小删除，插入和替换的次数，（我括号里面写‘主’是表示对str1操作变成str2，而不是对str2操作变成str1，当然两者是等价的，这里是为了表述简单起见）。从下面式子
Edit(i,j)表示字符串i变成字符串j的最小编辑距离。（注意i是主，即表示对i操作）
当j=0表示j是空串，这个时候i只要删除i个字符就可以得到j，所以需要i个步骤；当i=0表示i是空串，这个时候i只要增加j个字符等可以得到j，所以需要j个步骤；当两者都没有空串时，此时需要用到了递归的思想。
递归的思想可以参考C程序设计第四版P184以及189页汉诺塔问题，这里相当于说：要问我一共需要多少步骤可以使得i变成j，那么你如果告诉我第i-1变成j需要多少步骤（或者i变成j-1需要多少步骤，或者i-1变成j-1需要多少步骤）我就能告诉你这个答案。因为你告诉我需要多少步骤之后，我只要对比最后一个字符是不是相等就可以了。
如果是i-1变成j需要k步骤，那么我就将i删除掉，就变成了j，一共k+1步如果是i变成j-1需要k步骤，那么我就在i后面插入一个字符，就变成了j，一共k+1步如果是i-1变成j-1需要k步骤，那么我就看i是不是等于j，如果是k步骤不变，如果不是就将i替换成j，步骤变成k+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 npdef edit_distance(word1, word2):lens1=len(word1)lens2=len(word2)dp = np.zeros((lens1+1,lens2+1))# initializationfor i in range(lens1+1):dp[i][0] = ifor 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 = 0else: temp = 1dp[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);}
