最小編輯距離演算法作用

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
也附有代碼，可以試運行一下，動態規劃求解