C#搜索引擎開發實踐

第十講拼寫檢查主講人：羅剛

概述您是不是要找…編輯距離自動機拼寫檢查您是不是要找…使用拼寫檢查DidYouMeanParserdidYouMeanParser=newCompositeDidYouMeanParser("contents",System.Configuration.ConfigurationSettings.AppSettings["spellCheck.dic"],System.Configuration.ConfigurationSettings.AppSettings["spellCheck.misspell"]);Hitshits=searcher.Search(query);suggestedQueryString=null;//在界面顯示：您是不是要找suggestedQueryStringintminimumHits=10;floatminimumScore=0.7F;//如果搜索返回結果的數量小于一個值或者匹配第一個結果的分值小于最小值就查找提示詞if(hits.Length()<minimumHits||hits.Score(0)<minimumScore){ QuerydidYouMean=didYouMeanParser.Suggest(this.Query);//調用拼寫檢查算法

if(didYouMean!=null){ suggestedQueryString=didYouMean.ToString("contents"); }}拼寫檢查(SpellingCorrection)單個詞的拼寫檢查從詞表中找出錯誤詞對應的最有可能的一個正確詞上下文相關的拼寫檢查用語言模型根據上下文評估多個可能的候選正確詞拼寫檢查根據錯誤詞w找出對應的正確詞correct(w)對于任何c來講，出現w的概率P(w)都是一樣的，從而我們在上式中忽略P(w)，寫成：這里，P(c)是語料庫中詞c出現的概率，對于詞典中有的詞但是訓練語料庫中沒有的出現詞要考慮平滑。P(w|c)是在用戶想鍵入c的情況下敲成w的概率。單詞相似性編輯距離

對于兩個給定的單詞A和B，計算編輯距離D(A,B)

，就是把A轉換成B所需要的最小編輯操作次數。

inf---ormatik- interpol-ation找出候選正確詞對于給定詞w通過編輯距離挑選出相似的候選正確詞c76%的正確詞和錯誤詞的編輯距離是1。所以還需要考慮編輯距離是2的情況。99%的正確詞和錯誤詞的編輯距離在2以內。動態規劃求解編輯距離(Levenshteindistance)動態規劃把對復雜問題的求解分解成簡單的步驟：問題的最優解只取決于其子問題的最優解在計算一個對子問題的答案后，把它存儲到表中。后續的計算檢查這個表，避免重復工作以自底向上的方式計算答案編輯距離給定:

兩個字符串A=a1a2....am

和

B=b1b2...bn想要:

最小花費

D(A,B)對于把A轉換到B所需要的一系列編輯操作編輯操作:

1.使用B中的一個字符替換A中的一個字符2.刪除A中的一個字符3.插入B中的一個字符編輯距離代價模型:對于c，假設三角不等式:

c(a,c)c(a,b)+c(b,c)每個字符最多改變一次計算編輯距離假設Ai=a1...ai

和Bj

=b1....bj

Di,j=D(Ai,Bj)AB計算編輯距離三種結束的可能:1.用bn替換am

:

Dm,n=Dm-1,n-1+c(am,bn)2.刪除am:Dm,n=Dm-1,n

+13.插入bn:Dm,n=Dm,n-1

+1計算編輯距離Di-1,j-1Di-1,jDi,jDi,j-1+d+1+1循環等式(recurrenceequation),ifm,n

1:需要計算所有的Di,j,0im,0jn.編輯距離的循環等式初始條件:

D0,0=D(,)=0

D0,j

=D(,Bj)=j Di,0=D(Ai,)=i循環等式:編輯距離算法Algorithmedit_distance輸入:

兩個字符串A=a1....am

和B=b1...bn

輸出:

矩陣D=(Dij)1D[0,0]:=02for

i:=1to

m

do

D[i,0]=i3for

j:=1to

n

do

D[0,j]=j4fori:=1to

m

do5 for

j:=1to

ndo6 D[i,j]:=min(D[i-1,j]+1,7 D[i,j-1]+1,8 D[i–1,j–1]+c(ai,bj))動態規劃求解編輯距離實現///<paramname="s">輸入源串</param>///<paramname="t">輸入目標串</param>///<returns>源串與目標串的編輯距離</returns>publicstaticintLD(strings,stringt){intn=s.Length;intm=t.Length;int[,]d=newint[n+1,m+1];//Step1if(n==0){returnm;}if(m==0){returnn;}//Step2for(inti=0;i<=n;d[i,0]=i++){}for(intj=0;j<=m;d[0,j]=j++){}//Step3for(inti=1;i<=n;i++){//Step4for(intj=1;j<=m;j++){//Step5intcost=(t[j-1]==s[i-1])?0:1;//Step6d[i,j]=Math.Min(Math.Min(d[i-1,j]+1,d[i,j-1]+1),d[i-1,j-1]+cost);}}//Step7returnd[n,m];}例子abac01234b1a2a3c4編輯操作的追蹤圖0123412341123122322233332B=abacA

=

baac問題如何從一個大的正確詞表中找和輸入詞編輯距離小于k的詞集合？也就是模糊匹配。逐條比較編輯距離太慢。解決方法：生成輸入詞的編輯距離自動機生成詞典的有限狀態機對兩個有限狀態機取交集，在此過程中得到滿足條件的詞。編輯距離自動機構想構建一個有限狀態自動機準確的識別出和目標詞在給定的編輯距離內的字符串集合。然后可以輸入任何詞，然后自動機可以基于是否和目標詞的編輯距離最多不超過給定距離從而接收或拒絕它。而且，由于FSA的內在特性，可以在O(n)時間內實現。這里，n是測試字符串的長度。而標準的動態規劃編輯距離計算方法需要O(mn)時間，這里m和n是兩個輸入單詞的長度。因此編輯距離自動機可以更快的檢查許多單詞和一個目標詞是否在給定的在最大距離內。編輯距離自動機(LevenshteinAutomata)單詞‘food’的編輯距離自動機形成的非確定有限狀態自動機(NFA)，最大編輯距離是2開始狀態在左下，狀態使用ne標記風格命名。這里n是目前為止正確匹配的字符數，e是錯誤數量。垂直轉換表示未修改的字符，水平轉換表示插入，兩類對角線轉換表示替換(用*標記的轉換)和刪除(空轉換)。單詞長度是4，所以有5列允許2次錯誤，所以有3行狀態publicsealedclassState{intn;//目前為止正確匹配的字符數

inte;//錯誤數量

publicState(intn,inte){//構造方法

this.n=n;this.e=e;}publicoverrideBooleanEquals(Objectobj){//判斷兩個對象是否相同

if(obj==null||!(objisState)){returnfalse;}Stateother=(State)obj;return(n==other.n&&e==other.e);}publicoverrideintGetHashCode(){//取得散列碼

inthash=e*n+e;returnhash;}}編輯距離自動機實現代碼publicstaticNFAlevenshteinAutomata(Stringterm,intk){//根據初始狀態構建非確定有限狀態機

NFAnfa=newNFA(newState(0,0),term.Length,k);for(inti=0;i<term.Length;++i){charc=term[i];for(inte=0;e<(k+1);++e){//正確的字符，向右的箭頭

nfa.addTransition(newState(i,e),c,newState(i+1,e));if(e<k){//刪除，也就是刪除當前的輸入字符，向上的箭頭

nfa.addTransition(newState(i,e),NFA.ANY,newState(i,e+1));//插入，曲線斜箭頭

nfa.addTransition(newState(i,e),NFA.EPSILON,newState(i+1,e+1));//替換，直的斜箭頭

nfa.addTransition(newState(i,e),NFA.ANY,newState(i+1,e+1));}}}for(inte=0;e<(k+1);++e){if(e<k)nfa.addTransition(newState(term.Length,e),NFA.ANY,newState(term.Length,e+1));//向上的箭頭

nfa.addFinalState(newState(term.Length,e));//設置結束狀態

}returnnfa;}多個活躍狀態因為下圖的編輯距離自動機是一個NFA，所以有多個活躍狀態。表示字符串處理到目前為止所有可能的解釋。例如，消耗字符‘f’和‘x’后的活躍狀態如下:直接執行一個NFA計算代價高，因為執行過程中存在多個活躍狀態，和空轉換(也就是不需要輸入符號的轉換)，因此需要把NFA轉換成DFA。有幾種可能組成前兩個字符'f'和'x'：一個替換，例如在‘fxod’中00->10->21->31->41一個插入，例如在‘fxood’中00->10->11->21->31->41兩個插入，例如在‘fxfood’中00->01->02->12->11->22->32->42一個替換和一個刪除，例如在‘fxd’中00->10->21->32->42冪集(Powerset)構造算法冪集構造算法是把NFA轉換成DFA的標準算法NFA到相應的DFA的構造的基本思路是：1.DFA的每一個狀態對應NFA的一組狀態。2.DFA使用它的狀態去記錄在NFA讀入一個輸入符號后可能達到的所有狀態。冪集(Powerset)一個集合S的冪集指的是S的所有子集。總是包含空集?和S自身例如P({1,2,3})={{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}28從指定狀態q接受指定輸入事件經過轉換后達到的狀態組成的集合變換函數29變換函數30變換函數考慮這個NFA:這些狀態的冪集是:{?,{q0},{q1},{q2},{q0,q1},{q0,q2},{q1,q2},{q0,q1,q2}}根據這些狀態構造的新的狀態轉換表:01???

{q0}{q0,q1}{q0}{q1}?{q2}*{q2}??{q0,q1}{q0,q1}{q0,q2}*{q0,q2}{q0,q1}{q0}*{q1,q2}?{q2}*{q0,q1,q2}{q0,q1}{q0,q2}冪集構造例子(1)冪集構造例子(2)許多狀態不能從初始狀態達到。從NFA構造等價的DFA的一個好的方法是從初始狀態開始，然后當達到這些冪集狀態時才臨時構建這些新狀態圖形化:01???

{q0}{q0,q1}{q0}{q0,q1}{q0,q1}{q0,q2}*{q0,q2}{q0,q1}{q0}使用冪集算法合并多個活躍狀態下面是DFA的例子根據接收單詞‘food’編輯距離是1的字符串的NFA轉換而成看某個單詞是否相似//根據用戶輸入的單詞構建編輯距離自動機NFAlev=NFA.LevenshteinAutomata("foxd",2);//把非確定有限狀態自動機根據冪集構造轉換成確定有限狀態機DFAdfa=lev.ToDFA();//看單詞food是否能夠被接收System.Console.WriteLine(dfa.Accept("food"));從詞典查找指定編輯距離內的單詞詞典和條件(Levenshteinautomata)都表示成DFA，有可能高效的對兩個DFA取交集(intersect)，從詞典中找到滿足條件的詞。步調一致的遍歷兩個DFA，僅跟蹤兩個DFA都共有的邊，并且記錄走過來的路徑。任何時候兩個DFA都在結束狀態，輸出詞典DFA對應的單詞。ij0k1輸入詞的編輯距離自動機01ijk詞典DFADFA取交集實現publicstaticList<String>Intersect(DFAdfa1,DFAdfa2){List<String>match=newList<String>();//找到的正確單詞集合Stack<StackValue>stack=newStack<StackValue>();stack.Push(newStackValue("",dfa1.startState,dfa2.startState));while(stack.Count>0){StackValuestackValue=stack.Pop();HashSet<char>ret=intersection(dfa1.edges(stackValue.s1),dfa2.edges(stackValue.s2));foreach(charedgeinret){Statestate1=dfa1.next(stackValue.s1,edge);Statestate2=dfa2.next(stackValue.s2,edge);if(state1!=null&&state2!=null){stackValue.s+=edge;stack.Push(newStackValue(stackValue.s,state1,state2));if(dfa1.isFinal(state1)&&df