數據與智能，本公眾號關註大數據與人工智能技術。由一批具備多年實戰經驗的技術極客參與運營管理，持續輸出大數據、數據分析、推薦系統、機器學習、人工智能等方向的原創文章，每周至少輸出10篇精品原創。同時，我們會關註和分享大數據與人工智能行業動態。歡迎關註。
作者：Jerry
編輯距離介紹
在NLP任務中經常會碰到比較兩個字符串的相似度，比如拼寫糾錯和指代判斷。用戶很可能在搜索時輸入錯別字，比如“微信”輸成瞭“為信”，但是搜索引擎返回的結果糾正為“微信”的搜索結果，如圖1-1。另外比如“北京大學校長”和“北大校長”，“北京故宮博物院”和“北京故宮”都是指的同一個人或事物。
上述問題，可以利用兩個詞或短語的編輯距離大小來解決。
圖1-1 搜索詞“為信”的百度結果
編輯距離介紹
利用編輯距離可以判斷兩個字符串的相似程度，即從一個字符串到另一個字符串所需要的編輯次數，包括插入字符，刪除字符及替換字符這三種操作。最小編輯距離即從一個字符串到另一個字符串所需要的最小編輯次數。
圖2-1所示將兩個字符串進行排列比對，上面的字符串INTENTION進行一系列操作可以變為下面的字符串EXECUTION, d代表刪除字符操作，s代表替換字符操作，i代表插入字符操作。
圖2-1 編輯距離計算
可以給不同的操作賦予不同代價值，萊溫斯坦（Levenshtein）定義該編輯距離最簡單的方式是給每種操作賦予相同的代價值1，這樣上述兩個字符串的編輯距離為5。萊溫斯坦另外一種定義隻允許插入和刪除操作，不允許替換操作。這樣相當於替換用插入和刪除兩種操作實現，替換的代價值相當於變成2，上述兩個字符串的編輯距離為8。
最小編輯距離算法
那麼如何找到最小編輯距離呢？可以看作是一種操作路徑的搜索，從一個字符串轉變為另一個字符串的最短搜索路徑。圖3-1描述瞭intention字符串經過三種不同的操作路徑，轉變為三個不同的字符串。
圖3-1 將編輯距離看成搜索問題
從一個字符串轉到另一個字符串的可能路徑是非常多的，所有不同的操作路徑，最終都會到達一種狀態。采用動態規劃的方法，每一種狀態都記錄下來最短的路徑，然後從最終狀態進行回溯。動態規劃把一個大的問題轉換成很多的子問題來處理，intention和execution的最短編輯距離的操作步驟如圖3-2所示。
圖3-2 intention到execution的最小操作
最小編輯距離同時被多個人獨立發現，由Wagner和Fischer在1974年命名。讓我們先定義兩個字符串間的最小編輯距離。有兩個字符串X和Y，X長度為n，Y長度為m。D[i, j] 為X[1..i]到Y[1.. j]的最小編輯距離。X[1..i]表示X的前i個字符，Y[1.. j]表示Y的前j個字符，D[n,m]為X和Y的最小編輯距離。
采用動態規劃方法計算D[n,m], D[i,j]從小到大采用圖3-3計算，del-cost表示刪除操作的代價值，ins-cost表示插入操作的代價值，sub-cost表示替換操作的代價值，source表示原字符串，target表示轉換的目標字符串。如果定義插入和刪除的代價值為1，替換的代價值為2，計算方法如圖3-4所示。
圖3-3 最小編輯距離計算
圖3-4 明確代價值的最小編輯距離計算
最小編輯距離算法總結如圖3-5，圖3-6列出瞭intention和execution字符串跟根據圖3-5計算方法，算法的詳細計算結果。
圖3-6 intention和execution字符串最小編輯距離計算示例
編輯距離除瞭被大傢所熟知的應用如拼寫糾錯，編輯距離在另外的方面還有重要作用，如兩個字符串比對的最小代價計算。字符串比對在語音識別和語言處理領域有著廣泛的應用，在語音識別領域最小編輯距離比對通常用來計算錯詞率。比對在機器翻譯領域也扮演瞭重要的角色，在一個句子中每個詞在兩種語言中會有不同的詞來表示，它們需要相互比對。
為瞭使編輯距離算法能夠處理字符串比對，我們通過編輯距離矩陣標出一個比對路徑，圖3-7采用粗體藍色單元格表示出這樣一條路徑。每個單元格代表兩個字符串中的一對字符的比對結果，如果粗體單元格出現在同一行的相鄰位置，那麼從原字符串到目標字符串發生瞭一次插入操作；粗體單元格出現在同一列的相鄰位置，那麼從原字符串到目標字符串發生瞭一次刪除操作。
圖3-7
圖3-7同時也提供瞭一種計算比對路徑的思路，第一步采用最小編輯距離算法對每個單元格計算並存儲一個回溯指針，即到達這個單元格的前一單元格的位置。圖3-7有些單元格有多個回溯指針，代表有多種路徑到達該單元格。第二步開始回溯，從最後一個單元格開始（即最大行和最大列的單元格），跟隨回溯指針的方向回溯該矩陣，從最後單元格開始到第一個單元格的每一條完整路徑都代表一個最小比對距離。
小結
本文是對編輯距離及最小編輯距離算法及其應用的簡單介紹，主要內容參考《Speech and Language Processing (3rd ed. draft)》第二章部分章節進行翻譯，大部分圖片均來源於該書，疏漏和錯誤之處，望批評指正。