首頁 > 廠商 > 知識 > 編輯距離，如何計算大量字符串間的編輯距離

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

來源：整理時間：2023-08-29 16:27:34 編輯：智能門戶手機版

本文目錄一覽

1，如何計算大量字符串間的編輯距離
2，字符串編輯距離問題
3，編輯距離算法

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

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

如何計算大量字符串間的編輯距離

2，字符串編輯距離問題

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

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

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

字符串編輯距離問題

3，編輯距離算法

編輯距離是3，樓主看一下這篇博文：http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html也附有代碼，可以試運行一下，動態(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("請輸入字符串1\n");scanf("%s",&a);printf("請輸入字符串2\n");scanf("%s",&b);intresult=computedistance(a,b);printf("%d\n",result);system("pause");return0;}////////////////////refrence:dynamicprogrammingalgorithm(dpa)foredit-distance編輯距離關(guān)于兩個字符串s1,s2的差別，可以通過計算他們的最小編輯距離來決定。所謂的編輯距離:讓s1和s2變成相同字符串需要下面操作的最小次數(shù)。1.把某個字符ch1變成ch22.刪除某個字符3.插入某個字符例如s1=“12433”和s2=”1233”;則可以通過在s2中間插入4得到12433與s1一致。即d(s1,s2)=1(進行了一次插入操作)編輯距離的性質(zhì)計算兩個字符串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));第一個性質(zhì)是顯然的。第二個性質(zhì):由于我們定義的三個操作來作為編輯距離的一種衡量方法。于是對ch1,ch2可能的操作只有1.把ch1變成ch22.s1+ch1后刪除ch1d=(1+d(s1,s2+ch2))3.s1+ch1后插入ch2d=(1+d(s1+ch1,s2))對于2和3的操作可以等價于:_2.s2+ch2后添加ch1d=(1+d(s1,s2+ch2))_3.s2+ch2后刪除ch2d=(1+d(s1+ch1,s2))因此可以得到計算編輯距離的性質(zhì)2。復(fù)雜度分析從上面性質(zhì)2可以看出計算過程呈現(xiàn)這樣的一種結(jié)構(gòu)(假設(shè)各個層用當(dāng)前計算的串長度標(biāo)記，并假設(shè)兩個串長度都為n)可以看到，該問題的復(fù)雜度為指數(shù)級別3的n次方，對于較長的串，時間上是無法讓人忍受的。分析:在上面的結(jié)構(gòu)中，我們發(fā)現(xiàn)多次出現(xiàn)了(n-1,n-1),(n-1,n-2)……。換句話說該結(jié)構(gòu)具有重疊子問題。再加上前面性質(zhì)2所具有的最優(yōu)子結(jié)構(gòu)。符合動態(tài)規(guī)劃算法基本要素。因此可以使用動態(tài)規(guī)劃算法把復(fù)雜度降低到多項式級別。動態(tài)規(guī)劃求解首先為了避免重復(fù)計算子問題，添加兩個輔助數(shù)組。一.保存子問題結(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三.新的計算表達(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ù)雜度從新的計算式看出，計算過程為i=1->|s1|j=1->|s2|m[i][j]=……因此復(fù)雜度為o(|s1|*|s2|)，如果假設(shè)他們的長度都為n，則復(fù)雜度為o(n^2)