最後更新：2026-07-01

萊文斯坦距離

萊文斯坦距離又稱編輯距離，藉由計算將一個字串改成另一個所需的單字元編輯最少次數，來衡量兩個字串的差異程度。允許的編輯有插入、刪除與替換三種，每種成本均為一。本計算器接收兩個字串，回傳該距離與相似度百分比，適用於拼字檢查、模糊比對，以及 DNA 等序列的比較。

三種編輯操作

兩個字串之間的任何轉換，都可表示為三種基本動作的序列。插入增加一個字元，刪除移除一個字元，替換則以另一個字元取代某個字元。萊文斯坦距離尋找這些動作中成本最低的序列，每個動作的成本為一。由於替換是單一步驟，而非先刪除再插入，因此更動一個字母永遠算作一次編輯，而非兩次。

此度量以弗拉基米爾·萊文斯坦命名，他於 1965 年提出，並推廣了更早的漢明距離計算機：漢明距離只允許替換，且僅適用於長度相同的字串，而萊文斯坦距離還允許插入與刪除，因此能處理長度不同的字串。

動態規劃表格

距離透過填寫表格 $D$ 計算，表格中第一個字串的每個字元對應一列（前面加一個空白列），第二個字串的每個字元對應一行（前面加一個空白行）。格子 $D[i][j]$ 代表字串 A 的前 $i$ 個字元與字串 B 的前 $j$ 個字元之間的編輯距離。

第一列與第一行計算的是相對於空字串的編輯次數，因此 $D[i][0] = i$、$D[0][j] = j$。其餘每個格子都是三個候選值的最小值：

其中替換成本 $c$ 在字元相同時為 0，相異時為 1。答案位於右下角的格子。填滿表格所需的時間與兩字串長度的乘積 $m \times n$ 成正比。

計算範例

以經典的「kitten」與「sitting」為例。沿著表格的最佳路徑可得到三次編輯：

不存在更短的序列，因此距離為 3。較長的字串有 7 個字元，所以相似度為 $1 - 3/7 \approx 0.571$，即約 57%。

相似度及其限制

本計算器透過下式將原始距離正規化為相似度分數：

$S = 1 - \dfrac{d_L}{\max(m, n)}$

除以較長字串的長度，可將結果維持在完全不同字串的 0% 到完全相同字串的 100% 之間；兩個空字串視為相同。這是常見的正規化方式之一——其他工具可能改以兩者長度之和相除，或採用以比值為基礎的度量——因此來源不同的相似度數值無法直接相比較。

應用場景

拼字檢查器依照與拼錯單字之間的編輯距離，為候選修正排序。搜尋與資料庫系統用它做模糊比對，在查詢姓名或地址時容許打字錯誤。在生物資訊學中，編輯距離是比較 DNA、RNA 與蛋白質之序列比對的基礎，其中插入與刪除對應於突變。單純的萊文斯坦成本模型將所有編輯一視同仁；若應用需要對不同操作給予不同的懲罰，或必須有效率地比對極長的序列，則會以加權成本或專用的比對演算法加以擴充。