文本比較算法Ⅶ：Nakatsu 算法線性空間求 LCS 完整推導與範例演示

Nakatsu 算法 (1982) 以 O(n(m-p+1)) 時間、O(p(m-p)) 空間求 LCS，p 為 LCS 長度。本文完整推導 L 矩陣定義、四大定理、統一遞歸公式、初始化與對角線計算流程，並以 A=481234781, B=4411327431 為例逐步演示前 5 條對角線計算。

核心定義

• M = |A|, N = |B|, M ≤ N
• A = a₁...aₘ, B = b₁...bₙ
• LCS(i,j) = LCS(a₁..aᵢ, b₁..bⱼ)
• L(k,i)：與 a₁..aᵢ 有長度 k 的 LCS 的所有 b₁..bⱼ 中 j 的最小值。
  即 L(k,i) = min{j | LCS(i,j) = k}。

四大定理 (證明略)

1. L(1,i) < L(2,i) < L(3,i) ... (同行嚴格遞增)
2. L(k,i+1) ≤ L(k,i) (同列非遞增)
3. L(k,i) < L(k+1,i+1) (對角線嚴格遞增)
4. 遞歸公式：
   L(k,i+1) = min{ min{j | aᵢ₊₁=bⱼ ∧ j > L(k-1,i)}, L(k,i) }

統一遞歸公式 (引入輔助邊界)

• L(0,i) = 0
• L(k,0) = MaxValue = N+1
• 統一公式：
  L(k,i) = min{ min{j | aᵢ=bⱼ ∧ j > L(k-1,i-1)}, L(k,i-1) }
  條件：1 ≤ i ≤ M, 1 ≤ k ≤ M；i < k ⇒ L(k,i) = MaxValue。

標記簡化版 (⑤)

L(k,i) = min{j | aᵢ=bⱼ ∧ L(k-1,i-1) < j < L(k,i-1)}  (存在時)
L(k,i) = L(k,i-1)                                     (不存在時)

目的：① 縮小搜尋區間 ② 標記滿足嚴格不等式的單元格，為回溯做準備。

範例逐步演示 (A=481234781, B=4411327431, M=9, N=10)

初始化 L 矩陣 (k=0..9, i=0..9)

k\i  0 1 2 3 4 5 6 7 8 9
0    0 0 0 0 0 0 0 0 0 0
1    V 1
2    V V V
3    V V V V
4    V V V V V
5    V V V V V V
6    V V V V V V V
7    V V V V V V V V
8    V V V V V V V V V
9    V V V V V V V V V V
V = MaxValue = 11

對角線 1 (k=i=1)

L(1,1) = min{j | a₁=4=bⱼ ∧ j>0} = 1
標記 (1,1)

對角線 2 (k=1,i=2; k=2,i=3)

L(1,2): a₂=8 無匹配 → L(1,1)=1
L(2,3): a₃=1, 條件 j>L(1,2)=1 ∧ j

對角線 3 (k=1..3, i=3..5)
L(1,3)=1, L(2,4)=3, L(3,5)=6
標記 (3,5)


對角線 4 (k=1..4, i=4..6)
L(1,4)=1, L(2,5)=3, L(3,6)=5, L(4,7)=9
標記 (4,7)


對角線 5 (k=1..5, i=5..7)
L(1,5)=1, L(2,6)=3, L(3,7)=5, L(4,8)=7, L(5,9)=10
對角線無 V 值 → LCS 長度 = 5


後續步驟 (文中截斷)

繼續計算至對角線無 V 為止，最大 k 即 LCS 長度。
利用標記單元格回溯構造 LCS (可得多組解)。
空間優化：僅保留當前/前一對角線，達 O(p(m-p))。


結語
Nakatsu 算法以 L 矩陣將 LCS 問題轉化為「尋找最小 j 滿足約束」的動態規劃，對角線計算順序天然適合空間優化。雖前文線性空間結論有誤，但核心計算框架扎實，是理解 LCS 算法設計的重要里程碑。