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

什么是萊文斯坦距離？

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

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

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

它是如何工作的？

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

矩陣初始化

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

填充矩陣

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

插入：?jiǎn)卧瘢╥，j-1）的值 + 1

刪除：?jiǎn)卧瘢╥-1，j）的值 + 1

替換：?jiǎn)卧瘢╥-1，j-1）中的值加上成本，不同字符的成本為 1，相同字符的成本為 0。

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

提取結(jié)果

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

示例

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

初始化矩陣

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

填充矩陣

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

計(jì)算距離

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

詳細(xì)的分步計(jì)算

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

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

圖片

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

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

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

圖片

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

圖片

最終矩陣說明

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

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

結(jié)論

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