編輯距離，如何計(jì)算大量字符串間的編輯距離

來(lái)源：整理時(shí)間：2023-08-29 16:27:34 編輯：智能門(mén)戶(hù) 手機(jī)版

本文目錄一覽

1，如何計(jì)算大量字符串間的編輯距離
2，字符串編輯距離問(wèn)題
3，編輯距離算法

1，如何計(jì)算大量字符串間的編輯距離

模擬構(gòu)造一個(gè)（m + 1)行，（n+1）列的表格每一次都是在前一次的計(jì)算結(jié)果下，得到當(dāng)前的值首先是三個(gè)特殊情況用srcStr表示源字符串，dstStr 表示目標(biāo)字符串1) 兩個(gè)空字符串的編輯距離D(srcStr, dstStr) = 02) 如果srcStr為空，dstStr不為空，則D(srcStr, dstStr) = dstStr.length(), 即在原空字符串上添加字符，形成dstStr3) 如果dstStr為空，srcStr不為空，則D(srcStr, dstStr) = srcStr.length(), 及在源字符串上刪除其所有字符，直至為空

如何計(jì)算大量字符串間的編輯距離

2，字符串編輯距離問(wèn)題

定義字符串的基本操作為：刪除一個(gè)字符＼插入一個(gè)字符和將一個(gè)字符修改成另外一個(gè)字符這三種操作。將字符串A變成字符串B的最少操作步數(shù)，稱(chēng)為字符串A到字符串B的編輯距離。字符串“ABCDEFG”到字符串“BADECG”的編輯距離為_(kāi)____。正確答案： 3

你的第二步就錯(cuò)了。原來(lái)的字母B去哪了？ABCDEFG-原來(lái)BCDEFG-去掉ABDEFG-去掉CBADEFG-插入ABADECG-替換F為C我這種做法的編輯距離是4。也不是電腦編程問(wèn)題，還是訓(xùn)練思維。

編輯距離為3abcdefg 刪除a 得出 bcdefg (a→) bcdefg 將c替換成a 得出 badefg (c→a) badefg 將f替換成c 得出badecg (f→c)

字符串編輯距離問(wèn)題

3，編輯距離算法

編輯距離是3，樓主看一下這篇博文：http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html也附有代碼，可以試運(yùn)行一下，動(dòng)態(tài)規(guī)劃求解

#include<stdio.h>#include<stdlib.h>#include<string.h>int_min(inta,intb,intc)intmin=a;if(b<min)min=b;if(c<min)min=c;returnmin;}intcomputedistance(chars[],chart[])intn=strlen(s);intm=strlen(t);//intd[][]=newint[n+1,m+1];//matrixint**d=(int**)malloc((n+1)*sizeof(int*));for(inti=0;i<=n;++i)d[i]=(int*)malloc((m+1)*sizeof(int));}//step1if(n==0)returnm;}if(m==0)returnn;}//step2for(inti=0;i<=n;i++)d[i][0]=i;}for(intj=0;j<=m;d[0][j]=j++)d[0][j]=j;}//step3for(inti=1;i<=n;i++)//step4for(intj=1;j<=m;j++)//step5intcost=(t[j-1]==s[i-1])?0:1;//step6d[i][j]=_min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost);}}//step7returnd[n][m];}intmain(intargc,char*argv[])chara[9999];charb[9999];printf("請(qǐng)輸入字符串1\n");scanf("%s",&a);printf("請(qǐng)輸入字符串2\n");scanf("%s",&b);intresult=computedistance(a,b);printf("%d\n",result);system("pause");return0;}////////////////////refrence:dynamicprogrammingalgorithm(dpa)foredit-distance編輯距離關(guān)于兩個(gè)字符串s1,s2的差別，可以通過(guò)計(jì)算他們的最小編輯距離來(lái)決定。所謂的編輯距離:讓s1和s2變成相同字符串需要下面操作的最小次數(shù)。1.把某個(gè)字符ch1變成ch22.刪除某個(gè)字符3.插入某個(gè)字符例如s1=“12433”和s2=”1233”;則可以通過(guò)在s2中間插入4得到12433與s1一致。即d(s1,s2)=1(進(jìn)行了一次插入操作)編輯距離的性質(zhì)計(jì)算兩個(gè)字符串s1+ch1,s2+ch2的編輯距離有這樣的性質(zhì):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));第一個(gè)性質(zhì)是顯然的。第二個(gè)性質(zhì):由于我們定義的三個(gè)操作來(lái)作為編輯距離的一種衡量方法。于是對(duì)ch1,ch2可能的操作只有1.把ch1變成ch22.s1+ch1后刪除ch1d=(1+d(s1,s2+ch2))3.s1+ch1后插入ch2d=(1+d(s1+ch1,s2))對(duì)于2和3的操作可以等價(jià)于:_2.s2+ch2后添加ch1d=(1+d(s1,s2+ch2))_3.s2+ch2后刪除ch2d=(1+d(s1+ch1,s2))因此可以得到計(jì)算編輯距離的性質(zhì)2。復(fù)雜度分析從上面性質(zhì)2可以看出計(jì)算過(guò)程呈現(xiàn)這樣的一種結(jié)構(gòu)(假設(shè)各個(gè)層用當(dāng)前計(jì)算的串長(zhǎng)度標(biāo)記，并假設(shè)兩個(gè)串長(zhǎng)度都為n)可以看到，該問(wèn)題的復(fù)雜度為指數(shù)級(jí)別3的n次方，對(duì)于較長(zhǎng)的串，時(shí)間上是無(wú)法讓人忍受的。分析:在上面的結(jié)構(gòu)中，我們發(fā)現(xiàn)多次出現(xiàn)了(n-1,n-1),(n-1,n-2)……。換句話(huà)說(shuō)該結(jié)構(gòu)具有重疊子問(wèn)題。再加上前面性質(zhì)2所具有的最優(yōu)子結(jié)構(gòu)。符合動(dòng)態(tài)規(guī)劃算法基本要素。因此可以使用動(dòng)態(tài)規(guī)劃算法把復(fù)雜度降低到多項(xiàng)式級(jí)別。動(dòng)態(tài)規(guī)劃求解首先為了避免重復(fù)計(jì)算子問(wèn)題，添加兩個(gè)輔助數(shù)組。一.保存子問(wèn)題結(jié)果。m[|s1|,|s2|],其中m[i,j]表示子串s1(0->i)與s2(0->j)的編輯距離二.保存字符之間的編輯距離.e[|s1|,|s2|],其中e[i,j]=s[i]=s[j]?0:1三.新的計(jì)算表達(dá)式根據(jù)性質(zhì)1得到m[0,0]=0;m[s1i,0]=|s1i|;m[0,s2j]=|s2j|;根據(jù)性質(zhì)2得到m[i,j]=min(m[i-1,j-1]+e[i,j],m[i,j-1],m[i-1,j]);復(fù)雜度從新的計(jì)算式看出，計(jì)算過(guò)程為i=1->|s1|j=1->|s2|m[i][j]=……因此復(fù)雜度為o(|s1|*|s2|)，如果假設(shè)他們的長(zhǎng)度都為n，則復(fù)雜度為o(n^2)

編輯距離算法