最長(zhǎng)公共子序列與最小編輯距離-你有更快的算法么

最長(zhǎng)公共子序列與最小編輯距離-你有更快的算法么?阿里巴巴首席工程師經(jīng)驗(yàn)分享，物超所值。前百工作以后很少用到算法，時(shí)間長(zhǎng)了腦袋也不靈活。但是最近，我有幸在工作中又開(kāi)始用到算法，這使我欣喜若狂，這兩個(gè)算法主要用在計(jì)算文本相似度的場(chǎng)景中。小伙伴看標(biāo)題中的“最長(zhǎng)公共子序列”和“最小編輯距離”算法想當(dāng)然都認(rèn)為是爛大街的算法了，有什么好講的。當(dāng)然那種樸素的O(N2)O(N2)的算法本文不去講，而是講更快速的算法，而且還有變種問(wèn)題。最長(zhǎng)公共子序列對(duì)于字符串P和T，求其最長(zhǎng)公共子序列。動(dòng)態(tài)規(guī)劃算法dpf dPi-i,j-i+lif P[i]=tU]max(dpi-i,j,dpi,j-i)ifp[i]!=t[j]dpij={dpi-1,j-1+1ifp[i]=t[j]max(dpi-1,j,dpi,j-1)ifp[i]!=t[j]這個(gè)動(dòng)規(guī)方程不講了，大伙都知道原理。轉(zhuǎn)換成最長(zhǎng)單調(diào)遞增子序列P="abdba"T="dbaaba"步驟1：對(duì)于P中的每個(gè)字符，找到其在T中的位置。pos(a)={3,4,6}pos(b)={2,5}pos(d)={1}步驟2：把P用字母在T中的位置替換，得到新串C，注意位置要由大到小排列。C=[<6,4,3>,<5,2>,<1>,<5,2>,<6,4,3>]步驟3：求C的嚴(yán)格的單調(diào)遞增子序列，子序列長(zhǎng)度即為最長(zhǎng)公共子序列長(zhǎng)度。本例嚴(yán)格最長(zhǎng)單調(diào)遞增序列為:4,5,6=>a,b,a2,5,6=>b,b,a3,5,6=>a,b,a每個(gè)嚴(yán)格最長(zhǎng)單調(diào)遞增序列都對(duì)應(yīng)一個(gè)最長(zhǎng)公共子序列，這個(gè)算法的平均時(shí)間復(fù)雜度為O(nlogn)o(nlogn)。變種最長(zhǎng)公共子序列我在工作中需要解決的問(wèn)題不是這么簡(jiǎn)單的最長(zhǎng)公共子序列問(wèn)題，而是有些變化。重新看這個(gè)問(wèn)題，可以把最長(zhǎng)公共子序列看成是兩個(gè)字符串的匹配，每個(gè)字符如果匹配上則得1分，我們本質(zhì)是求這個(gè)最大匹配。那么如果每個(gè)字符匹配得分不是1分而是任意分將如何做呢？這里描述一下這個(gè)變種問(wèn)題：P：模式串a(chǎn)bcdcd<-這行是字符111223<-這行是權(quán)重T：文本串a(chǎn)cbd<-這行是字符1213<-這行是權(quán)重對(duì)于模式串和文本串的每個(gè)字符，在其下方都標(biāo)有權(quán)重，匹配規(guī)則如下：字符不匹配得0分字符匹配但是權(quán)重不匹配得1分字符與權(quán)重都匹配得權(quán)重分?jǐn)?shù)可以利用動(dòng)態(tài)規(guī)劃算法：dp『max(dpi-i,j,dpi,j-i，dpi-大i+scoreQ,tjDdpij=max(dpi1,j,dpi,j1,dpi1,j1+score(pi,tj))，時(shí)間復(fù)雜度0似2^(^)，求得結(jié)果為6。如何利用最長(zhǎng)公共子序列算法呢？我們發(fā)現(xiàn)如上的轉(zhuǎn)換，只適合匹配權(quán)重為1的情況，如果想適應(yīng)到各種靈活的權(quán)重，需要做一個(gè)拆分和一個(gè)轉(zhuǎn)換。拆分規(guī)則：對(duì)于P中的每個(gè)字符，把其重復(fù)W次，W為其權(quán)重。P：模式串a(chǎn)b c d c d => a b c d d c c d d d11 1 2 2 3 1 1 1 1 1 1 1 1 1 1 <=這行是權(quán)重，拆分后都為101 2 3 4 5 0 1 2 3 4 5 6 7 8 9 <=這行是下標(biāo)序列轉(zhuǎn)換規(guī)則：如果T中字符與P中字符相同但是權(quán)重不同則下標(biāo)重復(fù)1次。如果T中字符與P中字符相同權(quán)重也相同則下標(biāo)重復(fù)W次，W為權(quán)重。轉(zhuǎn)換時(shí)，T從前往后，P從后向前匹配，重復(fù)下標(biāo)為拆分后下標(biāo)。此時(shí)得到的序列是：[<0><6,5><6,5><2><1><9,8,7><9,8,7><9,8,7><4,3>]最長(zhǎng)嚴(yán)格上升子序列為：056789=>acd123<=這行為權(quán)重在權(quán)重較小時(shí)(我遇到的實(shí)際問(wèn)題中， w<=3)，算法的平均時(shí)間復(fù)雜度還是仍然為O(nlogn)o(nlogn)。最小編輯距離算法動(dòng)態(tài)規(guī)劃算法{ifp[i]=t[j]:dp[i][j]=dp[i-1][j-1]ifp[i]!=t[j]:dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1{ifp[i]=t[j]：dp[i][j]=dp[i-1][j-1]ifp[i]!=t[j]：dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1最普通爛大街算法，時(shí)間復(fù)雜度O(mn)O(mn)。列劃分算法參考文獻(xiàn)：《Theoreticalandempiricalcomparisonsofapproximatestringmatchingalgorithms》。InProceedingsofthe3rdAnnualSymposiumonCombinatorialPatternMatching,number664inLectureNotesinComputerScience,pages175?184.Springer-Verlag,1992。Author:WIChang，JLampe，時(shí)間復(fù)雜度為O(mn/b4/r/