文本比較算法Ⅸ：Primal-Dual 算法求最長公共子序列 (LCS)

Primal-Dual 算法為求解 LCS 提供了一種基於對偶理論的幾何視角。本文整理其核心定義、排序分組流程、L 矩陣填充與回溯還原步驟，並附完整範例演示。

問題定義

文本 A = a₁a₂...aₘ、B = b₁b₂...bₙ。
定義匹配點集合 P = {(i,j) | aᵢ = bⱼ}，共 l 個點 pₖ = (iₖ, jₖ)。

三大比較運算符

算法四步驟

範例：A=481234781, B=4411327431

步驟 1：構建 P 集合 (16 個匹配點)

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)

步驟 2：按 ≦ 排序

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

步驟 3：按 ⊿ 分組 (貪心提取 ⊿-鏈)

步驟 4：填充 L 行 (回溯指針)

• C₁ 全填 0。
• 後續組每元素填：排序序列中位於其前、且屬前一組的最後一個元素。

C₁: p₃ p₂ p₁ p₁₀  → L: 0  0  0  0
C₂: p₆ p₅ p₄ p₁₁  → L: p₁ p₁ p₁ p₁
C₃: p₇ p₈ p₁₅ p₁₄ → L: p₄ p₄ p₁₁ p₁₁
C₄: p₉ p₁₂ p₁₃    → L: p₇ p₈ p₈
C₅: p₁₆           → L: p₁₃

步驟 5：回溯 LCS

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: 4 8 1 2 3 4 7 8 _ 1
B: 4 4 1 1 3 2 7 4 3 1

複雜度與評價

• 空間：O(|P|) = O(mn) 最壞情況 (全匹配)。
• 時間：排序 O(|P| log |P|) + 分組/填充 O(|P|)。
• 缺點：空間非線性，無法保證找到所有 LCS (僅一個)。
• 價值：提供「對偶視角 + 分組回溯」新思路，拓寬算法設計視野。

結語

Primal-Dual 將 LCS 轉化為幾何偏序集上的鏈分解問題，雖非工程首選 (Hirschberg 線性空間、Myers O(ND) 更優)，但其數學結構優美，適合理論研究與教學展示「演算法設計的多元視角」。