使用開發(fā)搜索引擎-源代碼和課件19切分詞圖

C#搜索引擎開發(fā)實踐

第十九講中文分詞中的切分詞圖主講人：羅剛

概述切分詞圖表示切分詞圖形成切分詞圖切分詞圖根據(jù)基本詞庫對句子進行全切分，找出所有可能的詞，形成切分詞圖。邊代表詞，邊的權(quán)重是詞的概率。從切分詞圖中尋找概率最大的詞序列，對應于從有向無環(huán)帶正權(quán)重的圖中找最長路徑。其中：沒有考慮未登錄詞日期、數(shù)字串等可以用規(guī)則匹配，不需要考慮它內(nèi)部的概率。例如2010年3月23日這樣的日期切分詞圖中的點012345有意見分歧如果待切分的字符串有m個字符，考慮每個字符左邊和右邊的位置，則有m+1個點對應，點的編號從0到m。切分詞圖第5頁“有意見分歧”生成的切分詞圖意見分歧有意分見意有012345路徑1：0－1－3－5對應切分方案:有/意見/分歧/路徑2：0－2－3－5對應切分方案:有意/見/分歧/計算最大概率等于求切分詞圖的最長路徑表示切分詞圖切分詞圖的特點：邊比較少，所以是一個稀疏圖(SparseGraph)。稀疏圖一般用鄰接表表示。需要找一個節(jié)點的前驅(qū)詞集合，所以用逆鄰接表表示。逆鄰接表(Inverseadjacencylist)意見分歧有意分見意有0123450/01/1234513/3/切分詞圖逆鄰接表2/切分詞圖中的邊切分詞圖中的邊都是詞典中的詞，邊的起點和終點分別是詞的開始和結(jié)束位置publicclassCnToken{publicStringtermText;//詞

publicintstart;//開始位置

publicintend;//結(jié)束位置

publicdoublelogProb;//邊的權(quán)重

publicCnToken(intvertexFrom,intvertexTo,doublelogP,Stringword){start=vertexFrom;end=vertexTo;termText=word;logProb=logP;}}單向鏈表保存所有以同一個頂點結(jié)束的邊12/意見見123頂點3結(jié)束的邊頂點3結(jié)束的邊單向鏈表publicclassCnTokenLinkedList:IEnumerable<CnToken>{//可以遍歷單向鏈表中所有的詞

internalclassNode{publicCnTokenitem;publicNodenext;//每一個節(jié)點里記錄下一個節(jié)點對象

publicNode(CnTokenitem){this.item=item;next=null;}}privateNodehead;//記錄第一個節(jié)點

privateNodeheadtail;//記錄最后一個節(jié)點

publicCnTokenLinkedList(){//構(gòu)造方法

head=null;tail=null;}publicvoidPut(CnTokenitem){Nodet=tail;tail=newNode(item);if(head==null)head=tail;elset.next=tail;}#regionEnumeratorspublicIEnumerator<CnToken>GetEnumerator(){Nodecurrent=head;while(current!=null){yieldreturncurrent.item;current=current.next;}}IEnumeratorIEnumerable.GetEnumerator(){returnthis.GetEnumerator();}#endregion}類似設置斷點，下次從這個位置繼續(xù)執(zhí)行鄰接表表示的切分詞圖publicclassAdjList{privateCnTokenLinkedList[]list;//AdjList的圖的結(jié)構(gòu)

publicintverticesNum;//頂點數(shù)量

/***構(gòu)造方法：分配空間*/publicAdjList(intverticesNum){this.verticesNum=verticesNum;list=newCnTokenLinkedList[verticesNum];//初始化數(shù)組中所有的鏈表

for(intindex=0;index<verticesNum;index++){list[index]=newCnTokenLinkedList();}}/***增加一個邊到圖中*/publicvoidAddEdge(CnTokennewEdge){list[newEdge.end].put(newEdge);}/***返回一個詞的列表，包含以指定點結(jié)尾的所有的詞*/publicCnTokenLinkedListGetPrev(intvertex){CnTokenLinkedListll=list[vertex];if(ll==null)returnnull;returnll;}}用三叉樹實現(xiàn)全切分大中學活心生心動生活大學生活動中心下次匹配點對于英文或數(shù)字等特殊按規(guī)則匹配出來的詞，下次匹配點在這些詞之后對于普通的詞，下次匹配點是當前匹配點加1找出指定位置開始的所有詞//如果匹配上則返回true，否則返回falsepublicBooleanGetMatch(Stringsentence,intoffset,outintnext,outvalues){next=offset+1;if(sentence==null||rootNode==null||"".Equals(sentence)){returnfalse;}

values=newList<WordType>();//匹配結(jié)果TSTNodecurrentNode=rootNode;//樹的當前節(jié)點intcharIndex=offset;//字符串的開始位置while(true){if(currentNode==null){//到達樹的盡頭if(values.Count>0){returntrue;}returnfalse;}intp=sentence[charIndex]-currentNode.splitChar;//比較樹上當前節(jié)點中的字符和字符串中的當前字符if(p==0){charIndex++;if(currentNode.data!=null){//可以結(jié)束的節(jié)點values.Add(currentNode.data);offset=charIndex;}if(charIndex==sentence.Length){//已經(jīng)匹配完字符串if(values.Count>0){returntrue;}returnfalse;}currentNode=currentNode.eqNode;//進入下一層子樹}elseif(p<0){currentNode=currentNode.loNode;//查找左邊的子樹}else{currentNode=currentNode.hiNode;//查找右邊的子樹}}}查詞典形成切分詞圖List<WordType>values=newList<WordType>();intj;intnext;//下次匹配點for(inti=0;i<len;){//遍歷整個句子長度

Booleanmatch=dict.GetMatch(sentence,i,outnext,outvalues);//到詞典中查詢

if(match){//已經(jīng)匹配上

foreach(WordTypewordinwordMatch.values){ j=i+word.word.Length; doublelogProb=Math.Log(word.freq)-Math.Log(dict.n); g.AddEdge(newCnToken(i,j,logProb,word