對大多數(shù)拼寫糾錯來說，存在兩個基本原則：
- 對于一個拼寫糾錯的查詢，在其中正確的拼寫中荸实，選擇距離最近的一個。
- 當(dāng)兩個正確拼寫查詢臨近度相等時缴淋，選擇更常見的那個准给。
有兩大類拼寫糾錯的方法，一種是詞項獨(dú)立的校正重抖，另一種是上下文敏感的校正露氮。其中，在詞項獨(dú)立的校正中钟沛，不管查詢中包含多少個查詢詞項畔规，每次只對單個查詢詞項進(jìn)行校正。利用這種詞項獨(dú)立的方式恨统，很難檢測到查詢 flew form Heathrow中form這個錯詞叁扫。
方法1：編輯距離
給定兩個字符串s1和s2三妈， 兩者的編輯距離定義為將s1轉(zhuǎn)換為s2的最小編輯操作次數(shù)。編輯操作主要包括：
將一個字符插入字符串莫绣、
將一個字符從字符串中刪除
將一個字符替換為另一個字符
基于這些操作的編輯距離也稱為Levenshtein距離畴蒲，例如：cat和dog的編輯距離是3。
? 可以在O(|s1| * |s2|)的時間復(fù)雜度下計算兩個字符串的編輯距離对室。|si| (i=1,2)表示字符串si的長度模燥。主要解決思路是采用動態(tài)規(guī)劃的思想：
s1和s2以字符數(shù)組的形式存放，整數(shù)矩陣M的行號和列號分別是兩個字符串的長度掩宜，算法在運(yùn)行過程中不斷填充矩陣蔫骂，矩陣的第i行和第j列保存的是s1的前i個字符構(gòu)成的字符串和s2的前j個字符構(gòu)成的字符串的編輯距離。其中求最小值的三個參數(shù)分別對應(yīng)在s1中替換一個字符牺汤、在s1中插入一個字符和在s2中插入一個字符纠吴。
? 兩個字符串的編輯距離計算算法如下：
public int minDistance(String word1,String word2){
int m=word1.length();
int n=word2.length();
int [][]dp=new int [m+1][n+1];
for(int i=0;i<=m;i++){
dp[i][0]=i; //單純的刪除操作
}
for(int i=0;i<=n;i++){
dp[0][i]=i; //單純的插入操作
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(word1.charAt(i)==word2.charAt(j)){
dp[i+1][j+1]=dp[i][j];
}else{
dp[i+1][j+1]=Math.min(dp[i][j+1],Math.min(dp[i+1][j],dp[i][j]))+1;
}
}
}
return dp[m][n];
}
? 拼寫糾錯的問題：
給定字符串集合V（對應(yīng)詞項詞匯表）和查詢詞字符串，從V中尋找和q具有最小編輯距離的字符串慧瘤。最直接的算法是計算q到V中的每個詞項的編輯距離戴已，然后選擇其中編輯距離最小的字符串。很顯然這種窮舉的搜索開銷很大锅减，實際當(dāng)中使用列多種啟發(fā)式方法來提升查詢效率糖儡。最簡單的啟發(fā)式方法是將搜索限制在與查詢詞有相同首字母的字符串上，也就是說我們期望查詢的拼寫錯誤不會出現(xiàn)在第一個字符上怔匣。
方法2：k-gram 索引
? 為了進(jìn)一步限制需要計算編輯距離的詞匯表大小握联，利用k-gram索引來輔助返回與查詢q具有較小編輯距離的詞項，一旦返回這些詞項后每瞒，就能從中找到與q具有最小編輯距離的詞金闽。
? 查詢bord的2-gram索引如下所示，其中包含3個2-gram組成的倒排記錄剿骨，假定我們要返回包含上面3個2-gram的至少2個詞項代芜，對倒排記錄表的單遍掃描會返回滿足該條件的所有詞項。
bo ----> aboard ----> about ----> boardroom ----> border
or ----> border ----> lord ----> morbid ----> sordid
rd ----> aboard ----> ardent ---> boardroom ----> border
? 缺點(diǎn)：
比如boardroom這種不可能是bord的正確拼寫也會返回浓利。
針對上面的問題挤庇，需要計算查詢詞和詞匯表更精細(xì)的重疊度計算方法。比如：Jaccard系數(shù)
Jaccard系數(shù)的計算公式為：
其中贷掖，A嫡秕、B分別是查詢q、詞匯表詞項中的k-gram集合苹威。掃描過程中昆咽，一旦掃描到當(dāng)前的詞項t，就快速計算q和t的Jaccard系數(shù)，然后繼續(xù)掃描下一個詞項掷酗。如果Jaccard系數(shù)超過閾值调违，則將t輸出，否則繼續(xù)下一個掃描汇在。
方法3: 上下文敏感的拼寫校正
? 獨(dú)立的詞項拼寫校正方法在面對諸如flew form Heathrow 中的輸出錯誤時無能為力翰萨，因此這3個單詞獨(dú)立看來拼寫都沒有錯誤脏答。當(dāng)輸入這類查詢時糕殉，搜索引擎可能會發(fā)現(xiàn)返回的文檔非常少，隨后也許提供正確的查詢建議flew form Heathrow殖告。
這種功能的一種簡單的實現(xiàn)方法就是阿蝶，及時每個單詞拼寫都是對的，仍然要對每個單詞找到可能的拼寫正確詞黄绩，然后嘗試對短語中的每個詞進(jìn)行替換羡洁。比如對于上面flew form Heathrow的例子，我們可能會返回如下短語fled from Heathrow 和 flew fore Heathrow爽丹。對每個替換后的短語筑煮，搜索引擎進(jìn)行查找并確定最后的返回數(shù)目。
? 對于單獨(dú)的查詢有多種可能的正確拼寫形式粤蝎，那么上述方法中窮舉過程的開銷會非常大真仲，最后我們就會面對非常多的拼寫組合。有一些啟發(fā)式方法可以減少可能的拼寫結(jié)果空間初澎。
上述例子中秸应，我們對flew及from進(jìn)行擴(kuò)展時，我們只保留文檔集合或者查詢?nèi)罩局械母哳l組合結(jié)果碑宴。比如软啼，我們可能會保存flew from 而不是 fled fore 或 flea form，這是因為fled fore很可能比flew from 出現(xiàn)的次數(shù)少延柠。接下來我們僅僅根據(jù)高頻雙詞（如flew from）來獲得Heathrow的可能的正確拼寫祸挪。計算雙詞頻率的時候可以使用文檔集，也可以使用用戶的查詢?nèi)罩尽?/p>
