文本比較算法Ⅸ—Primal-Dual算法

 

研究文本比較算法有一段時間。看到Primal-Dual算法，作為不同的求LCS算法，介紹如下。

　　原文在《An almost-linear time and linear space algorithm for the longest common subsequence problem》

 

 

 

 

　　比較文本：

　　A=a₁a₂a₃……a_m

　　B=b₁b₂b₃……b_n

 

　　定義集合P={(i,j)|a_i=b_j}

　　則P={p₁,p₂,……,p_l}       p_k表示(i_k,j_k)，1≤k≤l

 

　　定義三個比較運算符

    　　①“∠”

        　　p_x∠p_y        當且僅當      i_x<i_y,j_x<j_y

    　　②“⊿”

           　　p_x⊿p_y        當且僅當      i_x≤i_y,j_x≥j_y

    　　③“≦”

        　　p_x≦p_y        要麼p_x∠p_y, 要麼p_x⊿p_y

 

　　接下來，我們用例子闡述算法

　　　　A：481234781

　　　　B：4411327431

 

　　第一步：先求出集合P

 

　　　　P={P₁=(1,1),P₂=(1,2),P₃=(1,8),P₄=(3,3),P₅=(3,4),P₆=(3,10),P₇=(4,6),P₈=(5,5),

　　　　　　P₉=(5,9),P₁₀=(6,1),P₁₁=(6,2),P₁₂=(6,8),P₁₃=(7,7),P₁₄=(9,3),P₁₅=(9,4),P₁₆=(9,10)}

 

　　第二步：對集合P中的元素按照比較運算符≦排序，得到排序序列

　　　　p₃≦p₂≦p₁≦p₆≦p₅≦p₄≦p₇≦p₉≦p₈≦p₁₂≦p₁₁≦p₁₀≦p₁₃≦p₁₆≦p₁₅≦p₁₄

 

 

　　第三步：對集合P中的元素進行分組

　　　　在排序序列中，從頭開始找出按照比較運算符⊿排序的子序列，可以得到

　　　　　　p₃⊿p₂⊿p₁⊿p₁₀

 

　　　　把這4個元素從隊列中抽出來，組成C₁組。則剩下的序列為

　　　　　　p₆≦p₅≦p₄≦p₇≦p₉≦p₈≦p₁₂≦p₁₁≦p₁₃≦p₁₆≦p₁₅≦p₁₄

 

　　　　再從頭開始找出按照比較運算符⊿排序的子序列，可以得到

　　　　　　P₆⊿p₅⊿p₄⊿p₁₁

 

　　　　把這4個元素從隊列中抽出來，組成C₂組。則剩下的隊列為

　　　　　　p₇≦p₉≦p₈≦p₁₂≦p₁₃≦p₁₆≦p₁₅≦p₁₄

 

　　　　再從頭開始找出按照比較運算符⊿排序的子序列，可以得到

　　　　　　p₇⊿p₈⊿p₁₅⊿p₁₄

 

　　　　把這4個元素從隊列中抽出來，組成C₃組。則剩下的隊列為

　　　　　　p₉≦p₁₂≦p₁₃≦p₁₆

 

　　　　再從頭開始找出按照比較運算符⊿排序的子序列，可以得到

　　　　　　p₉⊿p₁₂⊿p₁₃

 

　　　　把這三個元素從隊列中抽出來，組成C₄組。則剩下的隊列為

　　　　　　p₁₆

 

　　　　最後一個元素p₁₆組成C₅組

 

　　　　將上面的分組組成如下表格

 

C₁

C₂

C₃

C₄

C₅

 

p₃

p₂

p₁

p₁₀

p₆

p₅

p₄

p₁₁

p₇

p₈

p₁₅

p₁₄

p₉

p₁₂

p₁₃

p₁₆

L

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

　　第四步：填充上面表格的L行，填充的依據如下

　　1、 C₁組全部填充0

　　2、 後面組的每個元素都是填充，在排序序列中比自身靠前的，同時又是前一組中最後的元素

　　排序序列：p₃≦p₂≦p₁≦p₆≦p₅≦p₄≦p₇≦p₉≦p₈≦p₁₂≦p₁₁≦p₁₀≦p₁₃≦p₁₆≦p₁₅≦p₁₄

 

　　例如：p₆元素

　　　　在C₁組中排在p₆前的元素有3個，分別是p₃、p₂、p₁。P₁是3個當中最後一個。

　　　　故 p₆下填充p₁ 。

 

　　例如：p₉元素

　　　　在C₃組中排在p₉前的元素只有1個，是p₇。

　　　　故 p₉下填充p₇ 。

 

填充後的表格

 

C₁

C₂

C₃

C₄

C₅

 

p₃

p₂

p₁

p₁₀

p₆

p₅

p₄

p₁₁

p₇

p₈

p₁₅

p₁₄

p₉

p₁₂

p₁₃

p₁₆

L

0

0

0

0

p₁

p₁

p₁

p₁

p₄

p₄

p₁₁

p₁₁

p₇

p₈

p₈

p₁₃

 

 

　　最後一步：回溯LCS字符串

      　　先從C₅中p₁₆找起，p₁₆對應p₁₃，再從p₁₃找尋，p₁₃對應p₈。依次類推

      　　p₁₆→p₁₃→p₈→p₄→p₁

　　　　則(9,10)→(7,7)→(5,5)→(3,3)→(1,1)

　　　　故LCS字符串為

　　　　a₁a₃a₅a₇a₉=b₁b₃b₅b₇b₁₀=41371

 

 

　　 此時最佳匹配為

　　　　A：48123478_1

　　　　B：4411327431　　

 　　

　　算法完成

 

　　這個算法能夠找到至少一個LCS（注意，不一定能找到全部LCS，LCS不一定是唯一的）。但是，這個算法的空間占用為P的元素的個數，但是P的元素個數是O(n²)的。故本算法對於找最佳匹配不是一個好算法。不過對於開拓思路還是有用的，原來還可以這樣算LCS。