一、問題描述
定義
字符串編輯距離（Edit Distance），是俄羅斯科學家 Vladimir Levenshtein 在 1965 年提出的概念，又稱 Levenshtein 距離，是指兩個字符串之間，由一個轉變成另一個所需的最少編輯操作次數。許可的編輯操作包括：

將一個字符替換成另一個字符
插入一個字符
刪除一個字符
應用
1. DNA分析：
基因學的一個主要主題就是比較DNA序列并嘗試找出這兩個序列的公共部分。如果兩個DNA序列有類似的公共子序列，那么這兩個序列很可能是同源的，在比對兩個序列時，不僅要考慮完全匹配的字符，還要考慮一個序列中的空格或間隙和不匹配，這兩方面都可能意味著突變（mutation）。在序列比對時，需要找到最優的比對（最優比對大致是指要將匹配的數量最大化，將空格和不匹配的數量最小化）。如果要更正式些，可以確定一個分數，為匹配的字符添加分數，為空格和不匹配的字符減去分數。
2. 拼寫糾錯（Spell Correction）&拼寫檢查（Spell Checker）：
將每個詞與詞典中的詞條比較，英文單詞往往需要做詞干提取等規范化處理，如果一個詞在詞典中不存在，就被認為是一個錯誤，然后提出 N 個最可能是要輸入的詞——拼寫建議。常用的提示單詞的算法就是列出詞典中與原詞具有最小編輯距離的詞條。
3. 命名實體抽取（Named Entity Extraction）&實體共指（Entity Coreference）：
由于實體的命名往往是沒有規律的，如品牌名，且可能存在多種變形，拼寫形式，如“IBM”和“IBM Inc”，這樣導致基于詞典完全匹配的命名實體識別方法召回率較低，為此，我們可以使用編輯距離由完全匹配泛化到模糊匹配。
4. 字符串核函數（String Kernel）：
最小編輯距離作為字符串之間的相似度計算函數，用于SVM等機器學習算法中。

二、字符串編輯的分析

代碼如下：

// 算法的關鍵是求解 dp 矩陣，該矩陣即為生物信息學中所提到過的打分矩陣
// dp 矩陣的維度為 (srclength+1) * (targetLength+1)，
// 推演時可以將 ‘0’+pSource 分別排在每一行開頭，‘0’+pTarget 分別排在每一列上頭
int editDistance(char *pSource, char *pTarget)
{
int srcLength = strlen(pSource);
int targetLength = strlen(pTarget);
int dp[srcLength + 1][targetLength + 1];
for (int i = 0; i <= srcLength; ++i){
dp[i][0] = i; // 這一步表示由一個空串變成pSource的編輯距離
}
for (int j = 0; j <= targetLength; ++j){
dp[0][j] = j;
}
for (int i = 1; i <= srcLength; ++i){
for (int j = 1; j <= targetLength; ++j){
if (pSource[i - 1] == pTarget[j - 1]){
dp[i][j] = dp[i - 1][j - 1]; // 表示當前兩個字符串最后的兩個元素相等的情況
}
else{
// 表示當前兩個字符串最后兩個元素不相等的情況，
// 編輯距離為上述三種編輯距離中最小值加1
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[srcLength][targetLength]; // dp 矩陣的最后一個元素即為最終求出的編輯距離
}
---------------------
作者：xhj_enen
來源：CSDN
原文：https://blog.csdn.net/xhj_enen/article/details/88398444
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

總結

以上是生活随笔為你收集整理的字符串编辑距离（Edit Distance）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。