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

什么是萊文斯坦距離？

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

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

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

它是如何工作的？

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

矩陣初始化

• 創(chuàng)建一個矩陣，其中包含第一個字符串的前 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)。

提取結果

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

示例

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

初始化矩陣

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

填充矩陣

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

計算距離

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

詳細的分步計算

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

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

圖片

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

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

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

圖片

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

圖片

最終矩陣說明

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

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

結論

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