編輯距離的應用

最小編輯距離通常在很多實際應用中作為相似度計算函數，具體如下:(特別是對於中文自然語言處理，壹般以詞為基本處理單位)DNA分析:遺傳學的主要課題之壹是比較DNA序列，試圖找出兩個序列的共同部分。如果兩個DNA序列具有相似的公共子序列，那麽這兩個序列很可能是同源的。在比較兩個序列時，不僅要考慮完全匹配的字符，還要考慮壹個序列中的空格或缺口(或者相反，另壹個序列中的插入部分)和錯配，這兩種情況都可能意味著突變。在序列比對中，需要找到最優比對(最優比對大致意思是最大化匹配數，最小化空格和錯配數)。如果想更正式，可以確定壹個分數，匹配字符加壹個分數，空格和不匹配字符減壹個分數。全局序列比對試圖找到兩個完整序列S1和S2之間的最佳比對。以下面兩個DNA序列為例:

S1= GCCCTAGCG

S2= GCGCAATG

如果對每個匹配字符給壹分，對壹個空格扣兩分，對壹個不匹配字符扣壹分，那麽下面的比較是全局最優比較:

S1'= GCCCTAGCG

S2 = GCGC-AATG

連字符(-)代表壹個空格。在S2中，有五個匹配的字符，壹個空格(或者相反，在S1中有壹個插入)和三個不匹配的字符。這樣得到的分數是(5 * 1)+(1 *-2)+(3 *-1)= 0，這是能達到的最好結果。

使用局部序列比對，不需要比較兩個完整的序列，可以在每個序列中使用壹些部分來獲得最大分數。使用相同的序列S1和S2以及相同的評分方案，可以獲得以下局部最優比較S1”和S2”:

S1 = GCCCTAGCG

S1''= GCG

S2''= GCG

S2 = GCGCAATG

這個局部比較的分數是(3 * 1)+(0 *-2)+(0 *-1)= 3。拼寫糾正:拼寫檢查，將每個單詞與字典中的條目進行比較。英語單詞往往需要規範化，比如詞幹提取。如果壹個單詞在字典裏不存在，就認為是錯誤，然後嘗試提示N個最有可能的單詞——拼寫建議。常用的提示詞算法是列出詞典中與原詞編輯距離最小的詞條。這裏肯定有疑問:計算每個不在詞典中的詞(如果長度為len)與詞典中詞條之間的最小編輯距離是否太耗時？的確如此，所以壹般需要添加壹些剪枝策略。舉個例子，因為壹般的拼寫檢查應用只需要給出Top-N的改正建議(N壹般取10)，那麽我們就可以將字典中的詞條與len的長度進行比較，len-1，len+1，len-2，len-3，...受限拼寫建議條目和當前條目之間的最小編輯距離不能大於某個閾值；如果具有最小編輯距離1的候選條目超過n，則處理終止；緩存常見拼寫錯誤和提高性能的建議。命名實體提取:由於實體的命名往往是不規則的，比如品牌名稱，而且可能有很多變體和拼寫形式，比如“IBM”、“IBM Inc”，所以基於詞典完美匹配的命名實體識別方法召回率較低。所以可以用編輯距離從完美匹配推廣到模糊匹配，先提取實體名稱候選。具體地，可以計算候選文本串與詞典中每個實體名稱之間的編輯距離，當發現文本中某個字符串的編輯距離值小於給定閾值時，可以將其視為實體名稱候選詞；在獲得實體名稱的候選詞後，根據上下文使用啟發式規則或分類方法來確定候選詞是否確實是實體名稱。實體共指:通過計算任意兩個實體名稱之間的最小編輯距離來確定是否存在* * *引用關系。如“IBM”、“IBM公司”、“斯坦福大學校長約翰·漢尼斯”、“斯坦福大學校長約翰·漢尼斯”。機器翻譯:識別平行網頁對:因為平行網頁通常具有相同或相似的界面結構，所以在HTML結構上應該具有很大的相似性。首先提取網頁的HTML標簽並連接成壹個字符串，然後用最小編輯距離考察兩個字符串之間的相似性。在實踐中，這種策略壹般結合文檔長度比、句子對齊翻譯模型等方法來識別最終的平行頁面對。自動評測:首先存儲機器翻譯的原文和多個不同質量等級的參考譯文。評測時，將自動翻譯的譯文與編輯距離最小的參考譯文相對應，間接估計自動翻譯的質量，如下圖:字符串核:將最小編輯距離作為字符串間的相似度計算函數，作為核函數，集成到SVM中。