Nakatsu 算法是求 LCS 的經典 O(n(m-p+1)) 算法。前文錯誤宣稱「對角線/最左非 V 值即 LCS 下標」，經網友 Sumtec 指正並驗證屬實。本文糾正錯誤、重述正確流程、分析為何執著 Nakatsu、並拋出「最佳匹配」開放問題。
錯誤結論回顧與修正
| 前文錯誤說法 | 正確理解 |
|---|
| 「對角線上的數字就是 LCS 下標」 | 對角線無 V 值僅代表 LCS 長度 ≥ 該對角線號，非直接給出下標 |
| 「每行最左非 V 即 LCS 下標」 | 同理，僅指示長度下界，非具體解 |
Nakatsu 算法核心計算流程 (前文前半部) 是正確的，錯誤在於「線性空間優化」時的過度宣稱。
為何執著 Nakatsu？
目標非單純求 LCS 長度，而是求最佳匹配：
- 匹配 = 相同部分 (LCS) + 相異部分 (插入/刪除/修改)。
- 最佳匹配 = LCS 最長 且 匹配總長最短。
- 例子：A=GGATCGA, B=GAATTCAGTTA → 最佳匹配對齊見文。
相關算法定位
| 算法 | 關注點 | 能否給最佳匹配 |
|---|
| Levenshtein Distance (LD) | 相異部分 (編輯距離) | 否 (僅距離) |
| LCS (Hirschberg 線性空間) | 相同部分 | 否 (單一 LCS 不保證最佳匹配) |
| Nakatsu | 所有 LCS (空間 O(p(m-p))) | 潛力：遍歷所有 LCS 可枚舉匹配 |
錯誤推論：LD + LCS = 最佳匹配長度？
反例：A=11111112, B=23333333
LD=8, LCS=1 → LD+LCS=9
實際最佳匹配長度=15 (雙方錯位對齊)。
正確公式：相似度 = LCS / MATCH，MATCH 為最佳匹配長度。
Nakatsu 空間特性與潛力
- 空間 O(p(m-p))，p=LCS長度，m=短串長度。
- p=m/2 時空間最大 m²/4 (二次)。
- 優勢：能遍歷所有 LCS (未嚴格證明但廣泛相信)，且解直接給出 B 下標，橫座標對應 A 下標，省去二次匹配計算。
開放問題
如何高效計算兩文本的最佳匹配？
思路：枚舉所有 LCS → 各自構造匹配 → 取最短。
求建設性意見：是否有直接求最佳匹配的算法？Nakatsu 能否改造為線性空間遍歷所有 LCS？
結語
承認錯誤是科學態度。Nakatsu 算法本身無誤，關鍵在於正確理解其輸出語意。最佳匹配問題仍待解決，歡迎同道交流。
- 上一篇文章： 文本比較算法Ⅸ：Primal-Dual 算法求最長公共子序列 (LCS)
- 下一篇文章： 文本比較算法Ⅶ：Nakatsu 算法線性空間求 LCS 完整推導與範例演示
Copyright ©
程式碼之家 All Rights Reserved
