當你在處理一份重要文件時，假設你發現自己拼錯了一個單詞。手工查找和糾正這類錯誤是很困難的。現在我們來看看有趣的萊文斯坦距離：它可以測量將一個序列轉換成另一個序列所需的工作量，為序列比較和錯誤修復提供了有效的工具。這種以數學家弗拉基米爾·萊文斯坦命名的測量方法，改變了我們處理 DNA 測序和拼寫檢查等工作的方式。在準確性和精確性至關重要的數字時代，它是必不可少的。

什么是萊文斯坦距離？

俄羅斯科學家弗拉基米爾·萊文斯坦在1965年提出這個概念。

萊文斯坦距離（Levenshtein Distance）量化兩個序列之間的差異程度，是編輯距離的一種。通過計算將一個序列轉換成另一個序列所需的最少操作，它可以量化這種差異。允許進行以下操作：

• 插入：在序列中添加一個字符。
• 刪除：從序列中刪除一個字符。
• 替換：用一個字符替換另一個字符。

它是如何工作的？

我們采用基于矩陣的動態編程方法來確定兩個字符串之間的萊文斯坦距離。下面是詳細步驟：

矩陣初始化

• 創建一個矩陣，其中包含第一個字符串的前 i 個字符。然后第二個字符串的前 j 個字符用單元格 (i, j) 表示。
• 初始化第一行和第一列。單元格 (i, 0) 中的值代表第一個字符串的前 i 個字符與空的第二個字符串（即 i）之間的距離。同樣，(0, j) 表示空的第一字符串與第二字符串的前 j 個字符之間的距離。

填充矩陣

• 對于每個單元格 (i，j)，確定三個操作的成本：

插入：單元格（i，j-1）的值 + 1

刪除：單元格（i-1，j）的值 + 1

替換：單元格（i-1，j-1）中的值加上成本，不同字符的成本為 1，相同字符的成本為 0。

• 從這三個選項中選擇最低值，并將其分配到相應的單元格 (i, j)。

提取結果

• 矩陣右下角單元格中的值代表兩個字符串之間的萊文斯坦距離。

示例

現在計算字符串 kitten 和 sitting 之間的萊文斯坦距離。

初始化矩陣

• 行代表 kitten 字符串中的字符。
• 列代表 sitting 字符串中的字符。
• 第一行和第一列根據索引填充（代表插入或刪除操作）。

填充矩陣

• 比較字符，并根據插入、刪除或替換的最小成本填充每個單元格。

計算距離

• 填入矩陣后，右下角的單元格會顯示距離。

詳細的分步計算

首先，使用 kitten（6 個字符）和 sitting（7 個字符）這兩個字符串的長度創建矩陣。然后，使用插入、刪除和替換方法填充矩陣。

初始化矩陣：初始矩陣的第一行和第一列填入了索引，看起來像這樣：

圖片

填充矩陣：插入、刪除或替換是用于填充每個單元格（i，j）的三種操作。讓我們逐一介紹每個單元格的操作步驟。

比較 “k”（小貓）和 “s”（坐）：

• 插入 “k”：成本 = 2 (1 + 1)
• 刪除 “s”：成本 = 2 (1 + 1)
• 用 “s” 代替 “k”：成本 = 1 (0 + 1)
• 最低成本 = 1（替代）

圖片

繼續以類似方式填寫每對字符的矩陣：

圖片

最終矩陣說明

• 第一行：表示通過刪除將 kitten 轉換為空字符串。
• 第一列：表示通過插入將空字符串轉換為 sitting。
• 矩陣單元格：表示將 kitten 前綴轉換為 sitting 前綴的成本。

右下方的單元格（7，7）表示整個 kitten 和 sitting 之間的列文斯泰因距離為 3。這表明將 kitten 轉換為 sitting 需要進行三次操作（替換和插入）。

結論

通過計算將一個序列轉換成另一個序列所需的修改次數，萊文斯坦距離為評估序列相似性提供了一個有用的指標。它是序列比較和糾錯的重要工具，應用范圍從遺傳研究到拼寫檢查。理解和實施這一思想有助于解決序列轉換和相似性起關鍵作用的實際問題。