最小编辑距离算法作用

A. [高分提问]关于编辑距离算法(也叫Edit Distance算法或者Levenshtein Distance算法)

Levenshtein Distance即编辑距离，就是用来计算从原串（s）转换到目标串(t)所需要的最少的插入，删除和替换
的数目，在NLP中应用比较广泛，如一些评测方法中就用到了（wer,mWer等），同时也常用来计算你对原文本所作的改动数。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。
Levenshtein Distance算法可以看作动态规划。它的思路就是从两个字符串的左边开始比较,记录已经比较过的子串相似度(实际上叫做距离),然后进一步得到下一个字符位置时的相似度。 用下面的例子: GUMBO和GAMBOL。当算到矩阵D[3,3]位置时,也就是当比较到GUM和GAM时,要从已经比较过的3对子串GU-GAM, GUM-GA和GU-GA之中选一个差别最小的来当它的值. 所以要从左上到右下构造矩阵。

B. 编辑距离问题的动态规划算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int _Min(int a,int b,int c)
{
int min=a;
if (b <min)
min=b;
if(c <min)
min=c;
return min;
}

int ComputeDistance(char s[],char t[])
{
int n = strlen(s);

int m = strlen(t);

//int d[][] = new int[n + 1, m + 1]; // matrix
int **d = (int **)malloc((n+1) * sizeof(int *));
for(int i=0; i<=n; ++i)
{
d[i] = (int *)malloc((m+1) * sizeof(int));
}
// Step 1
if (n == 0)
{
return m;
}

if (m == 0)
{
return n;
}

// Step 2
for (int i = 0; i <= n; i++)
{
d[i][0] =i;
}

for (int j = 0; j <= m; d[0][j] = j++)
{
d[0][j] =j;
}

// Step 3
for (int i = 1; i <= n; i++)
{
//Step 4
for (int j = 1; j <= m; j++)
{
// Step 5
int cost = (t[j-1] == s[i-1]) ? 0 : 1;

// Step 6
d[i][j] = _Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+cost);
}
}
// Step 7
return d[n][m];
}

int main(int argc, char *argv[])
{
char a[9999];
char b[9999];
printf("请输入字符串1\n");
scanf("%s",&a);
printf("请输入字符串2\n");
scanf("%s",&b);
int result= ComputeDistance(a,b);
printf("%d\n",result);
system("PAUSE");
return 0;
}

////////////////////
Refrence : Dynamic Programming Algorithm (DPA) for Edit-Distance
编辑距离
关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。
所谓的编辑距离: 让s1和s2变成相同字符串需要下面操作的最小次数。
1. 把某个字符ch1变成ch2
2. 删除某个字符
3. 插入某个字符
例如 s1 = “12433” 和s2=”1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)
编辑距离的性质
计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质:
1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1;
2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 ,
d(s1+ch1,s2),
d(s1,s2+ch2) );
第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法。
于是对ch1,ch2可能的操作只有
1. 把ch1变成ch2
2. s1+ch1后删除ch1 d = (1+d(s1,s2+ch2))
3. s1+ch1后插入ch2 d = (1 + d(s1+ch1,s2))
对于2和3的操作可以等价于:
_2. s2+ch2后添加ch1 d=(1+d(s1,s2+ch2))
_3. s2+ch2后删除ch2 d=(1+d(s1+ch1,s2))
因此可以得到计算编辑距离的性质2。
复杂度分析
从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为 n )
可以看到，该问题的复杂度为指数级别 3 的 n 次方，对于较长的串，时间上是无法让人忍受的。
分析: 在上面的结构中，我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。
动态规划求解
首先为了避免重复计算子问题，添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到
M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;
根据性质2得到
M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] ,
m[i, j-1] ,
m[i-1, j] );
复杂度
从新的计算式看出，计算过程为
i=1 -> |s1|
j=1 -> |s2|
M[i][j] = ……
因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)

C. [高分提问]关于编辑距离算法(也叫Edit Distance算法或者Levenshtein Distance算法)

我们可以把这种相似度理解为：把一个字符串（source）通过“插入、删除和替换”这样的编辑操作变成另外一个字符串（target）所需要的最少编辑次数，也就是两个字符串之间的编辑距离（edit distance）。
就时间复杂度而言，动态规划法的时间复杂度是O(n2)，穷举算法的时间复杂度在最好的情况下是O(n)最差的情况当然是O(3n)。这种时间复杂度是指数型的算法，基本上是不可用的算法，只存在理论上的价值，实际工程中是不会适用这种时间复杂度的算法。
1.最优子结构：对于多阶段决策问题，如果每一个阶段的最优决策序列的子序列也是最优的，且决策序列具有“无后效性”，就可以将此决策方法理解为最优子结构。
2.无后效性：动态规划法的最优解通常是由一系列最优决策组成的决策序列，最优子结构就是这些最优决策序列中的一个子序列，对于每个子序列再做最优决策会产生新的最优决策（子）序列，如果某个决策只受当前最优决策子序列的影响，而不受当前决策可能产生的新的最优决策子序列的影响，则可以理解这个最优决策具有无后效性。

D. 只有增，删两种操作，如何求取最小编辑距离

传统的编辑距离里面有三种操作，即增、删、改，我们现在要讨论的编辑距离只允许两种操作，即增加一个字符、删除一个字符。我们求两个字符串的这种编辑距离，即把一个字符串变成另外一个字符串的最少操作次数。
输入格式：
多组数据，每组数据两行，每行一个字符串。每个字符串长度不超过1000，只有大写英文字母组成。
输出格式：
每组数据输出一行包含一个整数，表示需要最少操作的次数。
如输入：
A
ABC
BC
A
输出：
2
3
-----------------------------------------------------------------------------------------------------------------------
我的代码
#include <iostream>
#include <string>
#include <set>
using namespace std;

int same(string &s1,string &s2)
{
int count = 0;
set <char> st1;
set <char> st2;
for(int i=0;i<s1.length();i++)
{
st1.insert(s1[i]);
}
for(int i=0;i<s2.length();i++)
{
st2.insert(s2[i]);
}
set <char> ::iterator itr1;
set <char> ::iterator itr2;
for(itr1 = st1.begin();itr1!=st1.end();itr1++)
{
char temp = *itr1;
for(itr2 = st2.begin();itr2!=st2.end();itr2++)
{
if(temp==*itr2)
count++;
}
}
return count;
}
int main()
{
string s1,s2;
cin>>s1>>s2;
cout<<s1.length()+s2.length()-2*same(s1,s2)<<endl;
return 0;
}

职责

E. 简单理解 n-gram

N-Gram（有时也称为N元模型）是自然语言处理中一个非常重要的概念，通常在NLP中，人们基于一定的语料库，可以利用N-Gram来预计或者评估一个句子是否合理。另外一方面，N-Gram的另外一个作用是用来评估两个字符串之间的差异程度。这是模糊匹配中常用的一种手段。本文将从此开始，进而向读者展示N-Gram在自然语言处理中的各种powerful的应用。

基于N-Gram模型定义的字符串距离

模糊匹配的关键在于如何衡量两个长得很像的单词（或字符串）之间的“差异”。这种差异通常又称为“距离”。这方面的具体算法有很多，例如基于编辑距离的概念，人们设计出了 Smith-Waterman 算法和Needleman-Wunsch 算法，其中后者还是历史上最早的应用动态规划思想设计的算法之一。现在Smith-Waterman 算法和Needleman-Wunsch 算法在生物信息学领域也有重要应用，研究人员常常用它们来计算两个DNA序列片段之间的“差异”（或称“距离”）。

我们除了可以定义两个字符串之间的编辑距离（通常利用Needleman-Wunsch算法或Smith-Waterman算法）之外，还可以定义它们之间的N-Gram距离。N-Gram（有时也称为N元模型）是自然语言处理中一个非常重要的概念。假设有一个字符串 ，那么该字符串的N-Gram就表示按长度 N 切分原词得到的词段，也就是 中所有长度为 N 的子字符串。设想如果有两个字符串，然后分别求它们的N-Gram，那么就可以从它们的共有子串的数量这个角度去定义两个字符串间的N-Gram距离。但是仅仅是简单地对共有子串进行计数显然也存在不足，这种方案显然忽略了两个字符串长度差异可能导致的问题。比如字符串 girl 和 girlfriend，二者所拥有的公共子串数量显然与 girl 和其自身所拥有的公共子串数量相等，但是我们并不能据此认为 girl 和girlfriend 是两个等同的匹配。

为了解决该问题，有学者便提出以非重复的N-Gram分词为基础来定义 N-Gram距离这一概念，可以用下面的公式来表述：

此处，|GN(s)| 是字符串 s 的 N-Gram集合，N 值一般取2或者3。以 N = 2 为例对字符串Gorbachev和Gorbechyov进行分段，可得如下结果（我们用下画线标出了其中的公共子串）。

结合上面的公式，即可算得两个字符串之间的距离是8 + 9 − 2 × 4 = 9。显然，字符串之间的距离越小，它们就越接近。当两个字符串完全相等的时候，它们之间的距离就是0。

利用N-Gram模型评估语句是否合理

从现在开始，我们所讨论的N-Gram模型跟前面讲过N-Gram模型从外在来看已经大不相同，但是请注意它们内在的联系（或者说本质上它们仍然是统一的概念）。

为了引入N-Gram的这个应用，我们从几个例子开始。
首先，从统计的角度来看，自然语言中的一个句子 s 可以由任何词串构成，不过概率 P(s) 有大有小。例如：

显然，对于中文而言 s1 是一个通顺而有意义的句子，而s2 则不是，所以对于中文来说，P(s1)>P(s2) 。但不同语言来说，这两个概率值的大小可能会反转。

其次，另外一个例子是，如果我们给出了某个句子的一个节选，我们其实可以能够猜测后续的词应该是什么，例如

the large green __ . Possible answer may be “mountain” or “tree” ?
Kate swallowed the large green __ . Possible answer may be “pill” or “broccoli” ?
显然，如果我们知道这个句子片段更多前面的内容的情况下，我们会得到一个更加准确的答案。这就告诉我们，前面的（历史）信息越多，对后面未知信息的约束就越强。

如果我们有一个由 m 个词组成的序列（或者说一个句子），我们希望算得概率 P(w1,w2,⋯,wm) ，根据链式规则，可得
P(w1,w2,⋯,wm)=P(w1)P(w2|w1)P(w3|w1,w2)⋯P(wm|w1,⋯,wm−1)

这个概率显然并不好算，不妨利用马尔科夫链的假设，即当前这个词仅仅跟前面几个有限的词相关，因此也就不必追溯到最开始的那个词，这样便可以大幅缩减上诉算式的长度。即
P(wi|w1,⋯,wi−1)=P(wi|wi−n+1,⋯,wi−1)

特别地，对于 n 取得较小值的情况
当 n=1, 一个一元模型（unigram model)即为

当 n=2, 一个二元模型（bigram model)即为

当 n=3, 一个三元模型（trigram model)即为

接下来的思路就比较明确了，可以利用最大似然法来求出一组参数，使得训练样本的概率取得最大值。

使用N-Gram模型时的数据平滑算法

有研究人员用150万词的训练语料来训练 trigram 模型，然后用同样来源的测试语料来做验证，结果发现23%的 trigram 没有在训练语料中出现过。这其实就意味着上一节我们所计算的那些概率有空为 0，这就导致了数据稀疏的可能性，我们的表3中也确实有些为0的情况。对语言而言，由于数据稀疏的存在，极大似然法不是一种很好的参数估计办法。

这时的解决办法，我们称之为“平滑技术”（Smoothing）或者 “减值” （Discounting）。其主要策略是把在训练样本中出现过的事件的概率适当减小，然后把减小得到的概率密度分配给训练语料中没有出现过的事件。实际中平滑算法有很多种，例如：
▸ Laplacian (add-one) smoothing
▸ Add-k smoothing
▸ Jelinek-Mercer interpolation
▸ Katz backoff
▸ Absolute discounting
▸ Kneser-Ney

对于这些算法的详细介绍，我们将在后续的文章中结合一些实例再来进行讨论。

搜索引擎（Google或者Bai）、或者输入法的猜想或者提示。你在用网络时，输入一个或几个词，搜索框通常会以下拉菜单的形式给出几个像下图一样的备选，这些备选其实是在猜想你想要搜索的那个词串。再者，当你用输入法输入一个汉字的时候，输入法通常可以联系出一个完整的词，例如我输入一个“刘”字，通常输入法会提示我是否要输入的是“刘备”。通过上面的介绍，你应该能够很敏锐的发觉，这其实是以N-Gram模型为基础来实现的，如果你能有这种觉悟或者想法，那我不得不恭喜你，都学会抢答了！

参考： https://blog.csdn.net/mafujinji/article/details/51281816

F. 最小编辑距离算法 怎么得到路径

用dp的方法，并在每一步记录一下是哪一步转移过来的

倒着找回去就可以了

用C++写了一发，有少许注释，供参考

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#defineMAX(a,b)((a)>(b)?(a):(b));
usingnamespacestd;
structPoint{
	intx,y;
	Point(intx=0,inty=0):x(x),y(y){}
};
/**************************************************/
//theoperator
structOperator{
	inttype;
	intto;
	Operator(inttype=0,intto=0):type(type),to(to){}
/*
type0NoOpeartor
		1Insertto
		2Delete
		3Change->to
*/
};
/**************************************************/
//newanddeletefor2Darray
template<classT>
T**new_2D_Array(intn,intm){
	T**res=newT*[n];
	res[0]=newT[n*m];
	for(inti=1;i<n;i++)
	res[i]=res[i-1]+m;
	returnres;
}
template<classT>
voiddelete_2D_Array(T**src){
	delete[]src[0];
	delete[]src;
}
/**************************************************/
intget_eu(chari,charj){
returni==j?0:1;
}
/*dpformineditdistance*/
/**/
/**/
intmin_Edit_Dis(strings1,strings2,string&res,vector<Operator>&resop,vector<int>&respos){
	intret=0,reti=-1,retj=-1,n=s1.size(),m=s2.size();
	int**dp=new_2D_Array<int>(s1.size()+1,s2.size()+1);
	Point**pre=new_2D_Array<Point>(s1.size()+1,s2.size()+1);
	Operator**op=new_2D_Array<Operator>(s1.size()+1,s2.size()+1);
	for(inti=0;i<n;i++){
		for(intj=0;j<m;j++){
			dp[i][j]=0;
			pre[i][j]=Point(-1,-1);
		}
	}
dp[0][0]=0;
op[0][0]=Operator(0,'!');
	for(inti=1;i<=n;i++){
		dp[i][0]=i;
	op[i][0]=Operator(2,64);
	pre[i][0]=Point(i-1,0);
	}
	
	for(inti=1;i<=m;i++){
		dp[0][i]=i;
		op[0][i]=Operator(1,s2[i-1]);
		pre[0][i]=Point(0,i-1);
	}
	pre[0][0]=Point(-1,-1);

	for(inti=1;i<=n;i++){
		for(intj=1;j<=m;j++){
			dp[i][j]=dp[i-1][j]+1;
			pre[i][j]=Point(i-1,j);
			op[i][j]=Operator(2,64);
			if(dp[i][j-1]+1<dp[i][j]){
				dp[i][j]=dp[i][j-1]+1;
				pre[i][j]=Point(i,j-1);
				op[i][j]=Operator(1,s2[j-1]);
			}
			if(dp[i-1][j-1]+get_eu(s1[i-1],s2[j-1])<dp[i][j]){
				dp[i][j]=dp[i-1][j-1]+get_eu(s1[i-1],s2[j-1]);
				pre[i][j]=Point(i-1,j-1);
				if(s1[i-1]==s2[j-1])
					op[i][j]=Operator(0,'!');
				else
					op[i][j]=Operator(3,s2[j-1]);
			}
		}
	}

ret=dp[n][m];
/*printpreopdp
printf("(%d,%d)
",reti,retj);
	printf("");
	for(inti=0;i<=m;i++)
		if(i==0)printf("");
	elseprintf("%5c",s2[i-1]);
	printf("
");
	for(inti=0;i<=n;i++){
		if(i==0)printf("");
		elseprintf("%c",s1[i-1]);
		for(intj=0;j<=m;j++){
			printf("(%2d,%2d)",pre[i][j].x,pre[i][j].y);
		}
		cout<<endl;
	}

	printf("(%d,%d)
",reti,retj);
	printf("");
	for(inti=0;i<=m;i++)
		if(i==0)printf("");
	elseprintf("%5c",s2[i-1]);
	printf("
");
	for(inti=0;i<=n;i++){
		if(i==0)printf("");
		elseprintf("%c",s1[i-1]);
		for(intj=0;j<=m;j++){
			printf("(%2d,%2c)",op[i][j].type,op[i][j].to);
		}
		cout<<endl;
	}

printf("");
	for(inti=0;i<=m;i++)
		if(i==0)printf("");
	elseprintf("%c",s2[i-1]);
	printf("
");
	for(inti=0;i<=n;i++){
		if(i==0)printf("");
		elseprintf("%c",s1[i-1]);
		for(intj=0;j<=m;j++){
			printf("%2d",dp[i][j]);
		}
		cout<<endl;
	}
*/
	resop.clear();
	respos.clear();
	intcuri=n,curj=m;
/*togettheroad(includenullop)*/
	while(curi!=-1){
		resop.push_back(op[curi][curj]);
		respos.push_back(curi-1);
		inttmpi=pre[curi][curj].x;
		curj=pre[curi][curj].y;
		curi=tmpi;
	}
	returnret;
}
/*deletethenullop,andgetthestringofeachstep*/
/*Skill:
ChangeFormRighttoLeft,
*/
voidget_Recoder(stringsrc,vector<Operator>&op,vector<int>&pos,vector<string>&res){
res.clear();
res.push_back(src);
vector<Operator>tmpop;
vector<int>tmppos;
tmpop.clear();
tmppos.clear();
stringcurs=src;
charbuffer[2]={0,0};
	for(inti=0;i<op.size();i++){
		Operatorcurp=op[i];
		intcurpos=pos[i];
		if(curp.type==0)continue;
		elseif(curp.type==1){
			curs=curs.insert(curpos+1,1,curp.to);
			res.push_back(curs);
		}
		elseif(curp.type==2){
			curs=curs.erase(curpos,1);
			res.push_back(curs);
		}
		elseif(curp.type==3){
			curs[curpos]=curp.to;
			res.push_back(curs);
		}
		tmppos.push_back(curpos);
		tmpop.push_back(curp);
	}
	op.clear();
	pos.clear();
	for(inti=0;i<tmppos.size();i++){
		op.push_back(tmpop[i]);
		pos.push_back(tmppos[i]);
	}
}

/*Printtheprocess*/
voidprintRecord(stringsrc,vector<Operator>&op,vector<int>&pos,vector<string>&road){
	charoperatorList[4][15]={"GOAL","INSERT","DELETE","CHANGE"};
	intspacesize=6;
	for(inti=0;i<road.size();i++)
		spacesize=MAX(spacesize,road[i].size());
	for(inti=0;i<spacesize+32;i++)
		printf("_");
/*
Pos:
kitten
0123456
*/
	printf("
|%-*s|pos|operator|form|to|
|",spacesize,"string");
	for(inti=0;i<spacesize;i++)printf("-");
	printf("------------------------------|
");
	printf("|%-*s|/|SOURCE|/|/|
",spacesize,src.c_str());
	
	for(inti=0;i<op.size();i++){
		stringtmps=road[i];
		Operatortop=op[i];
		inttpos=pos[i];
		printf("|%-*s|%4d|%s|%c|%c|
",spacesize,tmps.c_str(),tpos+(top.type==1?1:0),operatorList[top.type],(top.type==3||top.type==2)?src[tpos]:'/',(top.type==3||top.type==1)?top.to:('/'));
	}
	printf("|%-*s|/|TARGET|/|/|
",spacesize,road[road.size()-1].c_str());	
	for(inti=0;i<spacesize+32;i++)printf("-");

	printf("
RoadFinished
");
}

intmain(){
	stringA="kitten";
	stringB="sitting";
	stringC;
	vector<Operator>op;
	vector<int>pos;
	vector<string>road;
	intres=min_Edit_Dis(A,B,C,op,pos);
	printf("Themineditdisis:%d
",res);
	get_Recoder(A,op,pos,road);
	printRecord(A,op,pos,road);
	return0;
}

G. 最大最小距离聚类算法可以做什么

通常，为有监督分类提供若干已标记的模式(预分类过)，需要解决的问题是为一个新遇到的但无标记的模式进行标记。在典型的情况下，先将给定的无标记的模式用来学习〔训练)，反过来再用来标记一个新模式。聚类需要解决的问题是将已给定的若千无标记的模式聚集起来使之成为有意义的聚类。从某种意义上说，标一记也与聚类相关，但这些类型的标记是由数据驱动的，也就是说，只是从数据中得到这些标记。聚类与数据挖掘中的分类不同，在分类模块中，对于目标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来:与此相似但又不同的是，聚类是在预先不知道目标数据库到底有多少类的情况下，希望将所有的记录组成不同的类或者说“聚类”，并且使得在这种分类情况下，以某种度量为标准的相似性，在同一聚类之间最小化，而在不同聚类之间最大化。事实上，聚类算法中很多算法的相似性都是基于距离的，而且由于现实数据库中数据类型的多样性，关于如何度量两个含有非数值型字段的记录之间的距离的讨论有很多，并提出了相应的算法。在很多应用中，聚类分析得到的每一个类中的成员都可以被统一看待。

H. 编辑距离的算法

比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
先创建一个6×8的表（cafe长度为4，coffee长度为6，各加2）
（1）： coffeecafe表1接着，在如下位置填入数字（表2）： coffee0123456c1a2f3e4表2从3,3格开始，开始计算。取以下三个值的最小值： 如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。（对于3,3来说为0） 左方数字+1（对于3,3格来说为2） 上方数字+1（对于3,3格来说为2） 因此为格3,3为0（表3） coffee0123456c10a2f3e4表3循环操作，推出下表 取右下角，得编辑距离为3 动态规划经常被用来作为这个问题的解决手段之一。
整数 Levenshtein距离(字符串 str1[1..m], 字符串 str2[1..n])
//声明变量， d[i , j]用于记录str1[1...i]与str2[1..j]的Levenshtein距离
int d[0..m, 0..n]
//初始化
for i from 0 to m
d[i, 0] := i
for j from 0 to n
d[0, j] := j
//用动态规划方法计算Levenshtein距离
for i from 1 to m
for j from 1 to n
{
//计算替换操作的代价，如果两个字符相同，则替换操作代价为0，否则为1
if str1[i]== str2[j] then cost := 0
else cost := 1
//d[i,j]的Levenshtein距离，可以有
d[i, j] := minimum(
d[i-1, j] + 1, //在str1上i位置删除字符（或者在str2上j-1位置插入字符）
d[i, j-1] + 1, //在str1上i-1位置插入字符（或者在str2上j位置删除字符）
d[i-1, j-1] + cost // 替换操作
)
}
//返回d[m, n]
return d[m, n]
wikisource上有不同的编程语言的版本。

I. k个文本两两进行相似性计算，其时间复杂度是多少

从字面上理解就是比较两个文本之间的相似性。在文本分类和聚类中都会用到文本相似... 那我来讲讲怎么计算。 常用的算法的时间复杂度和空间复杂度 一，求解算法... 最小编辑距离算法是计算两个字符串之间相互转换最少要经过多少次操作

J. 编辑距离算法

编辑距离是3，楼主看一下这篇博文：
http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html
也附有代码，可以试运行一下，动态规划求解