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

C#搜索引擎開(kāi)發(fā)實(shí)踐

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

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

publicintstart;//開(kāi)始位置

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

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

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

internalclassNode{publicCnTokenitem;publicNodenext;//每一個(gè)節(jié)點(diǎn)里記錄下一個(gè)節(jié)點(diǎn)對(duì)象

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

privateNodeheadtail;//記錄最后一個(gè)節(jié)點(diǎn)

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}類似設(shè)置斷點(diǎn)，下次從這個(gè)位置繼續(xù)執(zhí)行鄰接表表示的切分詞圖publicclassAdjList{privateCnTokenLinkedList[]list;//AdjList的圖的結(jié)構(gòu)

publicintverticesNum;//頂點(diǎn)數(shù)量

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

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

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

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