編輯距離演算法
㈠ 編輯距離的演算法
比如要計算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上有不同的編程語言的版本。
㈡ 如何計算大量字元串間的編輯距離
模擬構造一個（m + 1)行，（n+1）列的表格
每一次都是在前一次的計算結果下，得到當前的值
首先是三個特殊情況 用srcStr表示源字元串，dstStr 表示目標字元串
1) 兩個空字元串的編輯距離D(srcStr, dstStr) = 0
2) 如果srcStr為空，dstStr不為空，則D(srcStr, dstStr) = dstStr.length(), 即在原空字元串上添加字元，形成dstStr
3) 如果dstStr為空，srcStr不為空，則D(srcStr, dstStr) = srcStr.length(), 及在源字元串上刪除其所有字元，直至為空
㈢ [高分提問]關於編輯距離演算法(也叫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之中選一個差別最小的來當它的值. 所以要從左上到右下構造矩陣。
㈣ 最小編輯距離演算法 怎麼得到路徑
用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;
}
㈤ c語言 編輯距離演算法 程序運行沒問題 就是字元串長了會溢出 求修改
方法1:把要刪除的字元後面的字元依次前移一位覆蓋前面的字元即可.
方法2:建立另一個字元數組,將要刪除的字元之後的字元復制到這個新數組,然後再將新數組中的字元復制到原數組中從要刪除的字元開始的位置即可.
㈥ levenshtein — 計算兩個字元串之間的編輯距離
總結後的知識希望能幫到你！
函數名：levenshtein
(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)
levenshtein — 計算兩個字元串之間的編輯距離
說明
levenshtein ( string $str1 , string $str2 ) : int
levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del ) : int
編輯距離，是指兩個字串之間，通過替換、插入、刪除等操作將字元串str1轉換成str2所需要操作的最少字元數量。 該演算法的復雜度是 O(m*n)，其中 n 和 m 分別是str1 和str2的長度 （當和演算法復雜度為O(max(n,m)**3)的similar_text()相比時，此函數還是相當不錯的，盡管仍然很耗時。）。
在最簡單的形式中，該函數只以兩個字元串作為參數，並計算通過插入、替換和刪除等操作將str1轉換成str2所需要的操作次數。
第二種變體將採用三個額外的參數來定義插入、替換和刪除操作的次數。此變體比第一種更加通用和適應，但效率不高。
參數
str1
求編輯距離中的其中一個字元串
str2
求編輯距離中的另一個字元串
cost_ins
定義插入次數
cost_rep
定義替換次數
cost_del
定義刪除次數
返回值
此函數返回兩個字元串參數之間的編輯距離，如果其中一個字元串參數長度大於限制的255個字元時，返回-1。
㈦ 編輯距離問題的動態規劃演算法
#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)
㈧ 編輯距離演算法
編輯距離是3，樓主看一下這篇博文：
http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html
也附有代碼，可以試運行一下，動態規劃求解
㈨ 編輯距離的應用
最小編輯距離通常作為一種相似度計算函數被用於多種實際應用中，詳細如下： （特別的，對於中文自然語言處理，一般以詞為基本處理單元） DNA分析：基因學的一個主要主題就是比較 DNA 序列並嘗試找出兩個序列的公共部分。如果兩個 DNA 序列有類似的公共子序列，那麼這些兩個序列很可能是同源的。在比對兩個序列時，不僅要考慮完全匹配的字元，還要考慮一個序列中的空格或間隙（或者，相反地，要考慮另一個序列中的插入部分）和不匹配，這兩個方面都可能意味著突變（mutation）。在序列比對中，需要找到最優的比對（最優比對大致是指要將匹配的數量最大化，將空格和不匹配的數量最小化）。如果要更正式些，可以確定一個分數，為匹配的字元添加分數、為空格和不匹配的字元減去分數。 全局序列比對嘗試找到兩個完整的序列 S1和 S2之間的最佳比對。以下面兩個 DNA 序列為例：
S1= GCCCTAGCG
S2= GCGCAATG
如果為每個匹配字元一分，一個空格扣兩分，一個不匹配字元扣一分，那麼下面的比對就是全局最優比對：
S1'= GCCCTAGCG
S2'= GCGC-AATG
連字元（-）代表空格。在 S2'中有五個匹配字元，一個空格（或者反過來說，在 S1'中有一個插入項），有三個不匹配字元。這樣得到的分數是 (5 * 1) + (1 * -2) + (3 * -1) = 0，這是能夠實現的最佳結果。
使用局部序列比對，不必對兩個完整的序列進行比對，可以在每個序列中使用某些部分來獲得最大得分。使用同樣的序列 S1和 S2，以及同樣的得分方案，可以得到以下局部最優比對 S1''和 S2''：
S1 = GCCCTAGCG
S1''= GCG
S2''= GCG
S2 = GCGCAATG
這個局部比對的得分是 (3 * 1) + (0 * -2) + (0 * -1) = 3。 拼寫糾錯（Spell Correction）：又拼寫檢查（Spell Checker），將每個詞與詞典中的詞條比較，英文單詞往往需要做詞干提取等規范化處理，如果一個詞在詞典中不存在，就被認為是一個錯誤，然後試圖提示N個最可能要輸入的詞——拼寫建議。常用的提示單詞的演算法就是列出詞典中與原詞具有最小編輯距離的詞條。 這里肯定有人有疑問：對每個不在詞典中的詞（假如長度為len）都與詞典中的詞條計算最小編輯距離，時間復雜度是不是太高了？的確，所以一般需要加一些剪枝策略，如： 因為一般拼寫檢查應用只需要給出Top-N的糾正建議即可（N一般取10），那麼我們可以從詞典中按照長度依次為len、len-1、len+1、len-2、len-3、...的詞條比較； 限定拼寫建議詞條與當前詞條的最小編輯距離不能大於某個閾值； 如果最小編輯距離為1的候選詞條超過N後，終止處理； 緩存常見的拼寫錯誤和建議，提高性能。 命名實體抽取（Named Entity Extraction）：由於實體的命名往往沒有規律，如品牌名，且可能存在多種變形、拼寫形式，如「IBM」和「IBM Inc.」，這樣導致基於詞典完全匹配的命名實體識別方法召回率較低，為此，我們可以使用編輯距離由完全匹配泛化到模糊匹配，先抽取實體名候選詞。 具體的，可以將候選文本串與詞典中的每個實體名進行編輯距離計算，當發現文本中的某一字元串的編輯距離值小於給定閾值時，將其作為實體名候選詞；獲取實體名候選詞後，根據所處上下文使用啟發式規則或者分類的方法判定候選詞是否的確為實體名。 實體共指（Entity Coreference）：通過計算任意兩個實體名之間的最小編輯距離判定是否存在共指關系？如「IBM」和「IBM Inc.」, "Stanford President John Hennessy "和"Stanford University President John Hennessy"。 機器翻譯（Machine Translation）： 識別平行網頁對：由於平行網頁通常有相同或類似的界面結構，因此平行網頁在HTML結構上應該有很大近似度。首先將網頁的HTML標簽抽取出來，連接成一個字元串，然後用最小編輯距離考察兩個字元串的近似度。實際中，此策略一般與文檔長度比例、句對齊翻譯模型等方法結合使用，以識別最終的平行網頁對。 自動評測：首先存儲機器翻譯原文和不同質量級別的多個參考譯文，評測時把自動翻譯的譯文對應到與其編輯距離最小的參考譯文上，間接估算自動譯文的質量，如下圖所示： 字元串核函數（String Kernel）：最小編輯距離作為字元串之間的相似度計算函數，用作核函數，集成在SVM中使用。
㈩ 相似度演算法 稱編輯距離演算法 如何解決比較 1333333333和133 的問題
你應該再仔細看看別人的原代碼哦，在選擇最小值的時候，你的三選一的三的內容是錯誤的，按你的代碼應該是：
diverdiff[col+1][row+1]=divermin(diverdiff[col][row]+diff,diverdiff[col][row+1]+1,diverdiff[col+1][row]+1);