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