前言
在我們?nèi)粘?yīng)用中，應(yīng)該遇到不少類似的狀況：
寫文檔時，單詞拼寫錯誤后，工具自動推薦一個相似且正確的拼寫形式；
使用搜狗輸入法時，敲錯某個字的拼音照樣能夠打出我們想要的漢字；
利用搜索引擎進(jìn)行搜索時，下拉框中自動列出與輸入相近的詞語。
等等，不一一列舉。
這種功能是如何實(shí)現(xiàn)的呢？里面用到了哪些算法呢？本文就來介紹一個能夠完成這個任務(wù)的算法。
問題描述
其實(shí)，這幾個問題都能夠轉(zhuǎn)換成同一個問題：即對于給定的輸入字符串T，在預(yù)先準(zhǔn)備好的模式串集合Q中找到與輸入串相似的模式串子集。
那么如何得到準(zhǔn)備好的這些模式串集合呢？我們可以通過數(shù)據(jù)挖掘等一些機(jī)制來得到。
那么接下來的問題就是如何快速的從這個集合中找到與輸入串相似的字符串？通常我們用最小編輯距離來表示兩個字符串的相似程度。
例如，對于輸入串T，我們限制錯誤數(shù)小于等于2，即在預(yù)先準(zhǔn)備好的模式集合中找所有與輸入串編輯距離小于等于2的字符串。
有什么算法能夠快速完成這個任務(wù)呢？
暴力算法
遍歷集合Q中的每個模式串P，分別計(jì)算其與輸入串T的最小編輯距離，如果編輯距離小于指定的錯誤容忍度x，則輸出這個模式串。
時間復(fù)雜度：O(|Q| * n * m)，當(dāng)|Q|很大時，速度將會很慢。
那么這個算法可以優(yōu)化么？可以！
比如，第一個字很少有人輸入錯，所以我們可以在模式串集合Q中只對第一個字與輸入串第一個字相同的那些字符串進(jìn)行相似度計(jì)算，這樣就能夠減少相當(dāng)多的算量，是一個可行方法。
但是這也有問題，假若少部分人確實(shí)第一個字輸入錯了，那么這個算法找到的所有串也是錯的，不能達(dá)到糾錯的效果。
所以，針對首字符過濾的優(yōu)化算法有一定的局限性。
步步優(yōu)化
我們仔細(xì)思考這個問題，由于模式串Q是一個集合，那么其中必定有大量的模式串有共同的前綴。能否利用這個前綴進(jìn)行優(yōu)化呢？
優(yōu)化1： 利用兩個詞的相同前綴進(jìn)行優(yōu)化
比如：字符串 explore和explain，他們有公共的前綴，這就意味著他們與字符串explode的編輯矩陣的前幾列值是相同的，不用重復(fù)計(jì)算，如下圖紅色部分所示。
explore與explain無論與任何字符串計(jì)算編輯距離，編輯矩陣的前4列肯定一模一樣。所以，如果我們已經(jīng)計(jì)算過explore與某個串的編輯距離后，那么當(dāng)計(jì)算該串與explain的編輯距離時，前4列可以復(fù)用，直接從第五列開始計(jì)算。
到此，我們得到一個新的算法計(jì)算多模式的編輯距離：把模式串集合建立成一棵字典樹，深度優(yōu)先遍歷這棵樹，在遍歷的過程中，不斷更新編輯矩陣的某一個列，如果到達(dá)的節(jié)點(diǎn)是一個終結(jié)符，并且T與P（路徑上的字符形成的字符串）的編輯距離小于指定的容忍度，則找到一個符合條件的串。
優(yōu)化2：剪枝
雖然我們利用詞前綴優(yōu)化了算法，能夠避免擁有相同前綴模式串的編輯矩陣的重復(fù)計(jì)算，但是必須要遍歷所有節(jié)點(diǎn)。有沒有什么辦法能夠在計(jì)算到某一深度后，根據(jù)一些限制條件能夠剪去該子樹其它剩余節(jié)點(diǎn)的計(jì)算呢？在搜索算法中，這種優(yōu)化叫做剪枝。接下來我們討論一下該如何設(shè)計(jì)一個剪枝函數(shù)。
重新審視我們的編輯距離定義，其實(shí)可以看成是把字符串P和T分別拆分成兩段，然后計(jì)算對應(yīng)的段的編輯距離之和，如下圖所示。
字符串P和T分別拆分成兩段，紅色和綠色。紅色部分之間的編輯距離與綠色部分之間的編輯距離之和即為字符串P和T的編輯距離。
舉個例子，更形象：
例子1
1 | ed("explore", "express") = ed("explo", "exp") + ed("re", "ress") |
例子2
1 | ed("explore", "express") = ed("exp", "exp") + ed("lore", "ress") |
例子3
但是，并不是每種劃分都是正確的，比如下面圖所示：
1 | ed("ex","exp") + ed("plore", "ress") = 1 + 4 = 5 |
所以，最小編輯距離問題又相當(dāng)于一個最優(yōu)拆分，即對于字符串P中位置為i的字符，找到在T中的一個最優(yōu)位置j，使得
1 | ed(P.prefix(i), T.prefix(j)) + ed(P.suffix(i+1), T.suffix(j+1)) |
最小。
回到我們這個問題中來，如果我們限制P和T的最小編輯距離小于等于x，
我們讓 p[i]分別匹配t[i-x],t[i-x+1],……,t[i],t[i+1],……t[i+x]，并找到其中前半段匹配的最小的編輯距離ed1=ed(p[1~i],t[1~j])，如果ed1大于x，我們則能推斷出ed(p,t)也終將大于x（ed=ed1+ed2>x）。
為什么p[i]不匹配t[i-x-1]以及之前的位置呢？那是因?yàn)閑d(p.prefix(i), t.prefix(i-x-1)) > x，因?yàn)楸仨氈辽僭趖.prefix(i-x-1)中插入x+1個字符才能保證字符串長度相等；同理p[i]也不能匹配t[i+x+1]及其之后的位置。所以，根據(jù)分段原則，最優(yōu)匹配肯定出現(xiàn)在t[i-x] ~ t[i+x]之間，如果這個區(qū)間的最小編輯距離都大于x，那么我們無需對p[i+1]及其之后的字符進(jìn)行匹配計(jì)算。
例如：當(dāng)遍歷到藍(lán)色節(jié)點(diǎn)l時，路徑形成的字符串expl與T=exist滿足剪枝條件，則后序節(jié)點(diǎn)不需要遍歷，因?yàn)楹竺娌豢赡苡腥魏我粋€字符串滿足與T的編輯距離小于2。
至此，我們得到了剪枝優(yōu)化：深度遍歷到達(dá)字典樹的某個節(jié)點(diǎn)，其路徑上的字符組成字符串P，計(jì)算其與T.prefix(i-x), T.prefix(i-x+1),……T.prefix(i+x)的最小編輯距離，如果其中的最小值大于x，則停止遍歷這棵子樹上的后面的節(jié)點(diǎn)。
其實(shí)，這個最終版本的優(yōu)化算法出自論文：《Error-tolerant finite-state recognition with applications to morphological analysis and spelling correction》.K Oflazer:1996
代碼實(shí)現(xiàn)與效果對比
代碼實(shí)現(xiàn)需需要很強(qiáng)的技巧性，因?yàn)闊o論是剪枝函數(shù)還是進(jìn)行最終確認(rèn)函數(shù)都可以復(fù)用同一個編輯矩陣，貼一個很丑陋的代碼：https://github.com/haolujun/Algorithm/tree/master/muti-edit-distance
這個算法在錯誤容忍度非常小的情況下效率非常高，我隨機(jī)生成了10萬個長度5~10的模式串，再隨機(jī)生成100個輸入串T（長度5 ~ 10），字符集大小為10，x最小編輯距離限制，計(jì)算多模式編輯距離，處理總時間如下，單位ms：
| 算法 | x = 1 | x = 2 | x = 3 | x = 4 | x = 5 | x = 6 |
|---|---|---|---|---|---|---|
| 暴力算法 | 21990 | 21990 | 21990 | 21990 | 21990 | 21990 |
| 優(yōu)化算法 | 97 | 922 | 4248 | 11361 | 20097 | 28000 |
當(dāng)容忍度很小時，優(yōu)化算法完勝暴力算法，并且實(shí)際應(yīng)用中x一般取值都非常小，正好適合優(yōu)化算法。
當(dāng)x值增大，優(yōu)化算法效率逐漸下降，并且最后慢于暴力算法，這是因?yàn)閮?yōu)化算法實(shí)現(xiàn)復(fù)雜導(dǎo)致（遞歸+更復(fù)雜的判斷）。
下載文檔
