使用開發(fā)搜索引擎-源代碼和課件-16查詞典

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

第十六講查詞典的方法主講人：羅剛

概述單鏈表標(biāo)準(zhǔn)Trie樹三叉Trie樹構(gòu)建平衡的Trie樹燈籠春、節(jié)、快、樂四個燈籠串起來單鏈表把詞看成是字符的序列，也就是字符組成的鏈表中

國/單鏈表publicclassWordLinkedList{//可以從前往后遍歷單詞中所有的字符

internalclassNode{publiccharsplitChar;//每個節(jié)點記錄一個字符

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

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

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

publicWordLinkedList(){head=null;tail=null;}publicvoidPut(charitem){Nodet=tail;tail=newNode(item);if(head==null)head=tail;elset.next=tail;}publicvoidPut(Stringword){//放入詞for(inti=0;i<word.Length;i++){put(word[i]);}}}合并多個鏈表astaatas合并節(jié)點ats選擇分支-從字符到鏈接散列是一種常見的高效查找方法，它根據(jù)數(shù)組下標(biāo)查詢，所以速度快。首先根據(jù)詞表構(gòu)造散列表，具體來說就是用給定的散列函數(shù)構(gòu)造詞典到數(shù)組下標(biāo)的映射，如果存在沖突，則根據(jù)選擇的沖突處理方法解決地址沖突。然后可以在散列表的基礎(chǔ)上執(zhí)行散列查找。

不存在沖突的散列表叫做完美散列(perfecthash)。采用了字散列的方法，鍵是字符，值是鏈接astatasts節(jié)點publicclassNode{protectedcharsplitChar;//分隔字符，這里是英文字符protectedNode[]children;//孩子節(jié)點組成的數(shù)組，類似散列表中的數(shù)組/***構(gòu)造方法**@paramsplitchar分隔字符*/protectedNode(charsplitchar){children=newNode[26];//26個小寫英文字母this.splitChar=splitchar;}}key:charvalue:Node類似Dictionary<char,Node>標(biāo)準(zhǔn)Trie樹

rootabhitsteyensto

asatbebyheinisitto采用了逐字散列的方法，可以看成是一種逐字的完美散列

{as,at,be,by,he,in,is,it,to}單詞組成的標(biāo)準(zhǔn)Trie樹可以結(jié)束的節(jié)點查找標(biāo)準(zhǔn)Trie樹rootabhitsteyensto查找at俄羅斯方塊玩俄羅斯方塊：匹配上一層就消去一層匹配單詞：匹配上一個字符就匹配下一層dreddpkcotlleylll標(biāo)準(zhǔn)Trie樹把單詞中的每個字符逐字散列，整個詞典組織成一個標(biāo)準(zhǔn)Trie樹：除了根節(jié)點外的每個節(jié)點用一個字符標(biāo)記，叫做splitChar類似有限狀態(tài)機特別標(biāo)記可以結(jié)束的狀態(tài)，特別標(biāo)記可以結(jié)束的節(jié)點例子：一個詞典的標(biāo)準(zhǔn)Trie樹S={bear,bell,bid,bull,buy,sell,stock,stop}rlsuaeib使用標(biāo)準(zhǔn)Trie樹切分電話號碼問題：輸入電話號碼，返回區(qū)位編號 例如輸入：返回：河南:鄭州電話區(qū)位號碼文件0701:江西:鷹潭0998:新疆:澤普縣0851:貴州:貴陽0999:新疆:伊犁哈薩克自治州0852:貴州:遵義0853:貴州:安順0994:新疆:奇臺縣0855:貴州:黔東南苗族侗族自治州標(biāo)準(zhǔn)Trie樹類似按字做散列區(qū)號有多長就有多少個節(jié)點對應(yīng)每個節(jié)點對應(yīng)一個TrieNode每個TrieNode包含一個分隔字符splitChar

例如：0371這個區(qū)號有四個節(jié)點對應(yīng)也就是說四個TrieNode對象第一個對象中的splitChar屬性是0第二個對象中的splitChar屬性是3第三個對象中的splitChar屬性是7第四個對象中的splitChar屬性是1每個對象有10個孩子節(jié)點分別對應(yīng)splitChar為0到90children3children7children1children葉節(jié)點存值信息根節(jié)點Trie樹的特點多路樹三叉Trie樹是三路數(shù)字搜索Trie樹是10路壓縮同樣的前綴字符共享同樣的存儲單元，例如：北京、北京市兩個詞。北和京兩個字的存儲單元相同。使用逆Trie樹來讓后綴字符共享同樣的存儲單元，例如：復(fù)印機、打印機、傳真機。共享“機”、“印”的存儲單元。適合存儲靜態(tài)的數(shù)據(jù)詞典不經(jīng)常變化實現(xiàn)標(biāo)準(zhǔn)Trie樹-存儲一位號碼的節(jié)點sealedclassTrieNode{publicTrieNode[]children;//孩子節(jié)點組成的數(shù)組

publiccharsplitChar;//分隔字符

publicStringarea;//電話所屬地區(qū)信息

/***構(gòu)造方法**@paramsplitchar分隔字符*/publicTrieNode(charsplitchar){children=newTrieNode[10];//10個數(shù)字

area=null;this.splitChar=splitchar;}}實現(xiàn)標(biāo)準(zhǔn)Trie樹-生成樹privateTrieNoderoot=newTrieNode('0');//所有的電話號碼都是從0開始privatevoidAddTel(Stringtel,Stringarea){//電話號碼和對應(yīng)地區(qū)TrieNodecurrentNode=root;for(inti=1;i<tel.Length;i++){charc0=tel[i];intind=tel[i]-'0';TrieNodetmpNode=currentNode.children[ind];if(null==tmpNode){tmpNode=newTrieNode(c0);}if(i==tel.Length-1){//到了可以結(jié)束的節(jié)點

tmpNode.area=area;//存儲值

}currentNode.children[ind]=tmpNode;currentNode=tmpNode;}}查找電話號碼的過程//同時遍歷輸入串和樹publicStringSearch(Stringtel){TrieNodetstNode=root;for(inti=1;i<tel.Length;i++){//從前往后一個字符一個字符的匹配

tstNode=tstNode.children[(tel[i]-'0')];if(null!=tstNode.area){returntstNode.area;}}returnnull;//沒找到}二叉搜索樹二叉搜索樹(binarysearchtree簡稱BST)是一個用來查找的二叉樹，有如下的特點：每個節(jié)點有一個字符一個節(jié)點的左子樹僅包含小于這個節(jié)點的字符一個節(jié)點的右子樹僅包含大于這個節(jié)點的字符二叉搜索樹ibahotclassNode{//二叉搜索樹中的節(jié)點publiccharsplitChar;//節(jié)點中的數(shù)據(jù)

publicNodeloNode;//左邊的孩子

publicNodehiNode;//右邊的孩子

publicNode(chari,Nodel,Noder){//構(gòu)造方法

splitChar=i;loNode=l;hiNode=r;}}二叉搜索樹classBinaryTree{publicNoderoot;publicBinaryTree(){//二叉搜索樹的構(gòu)造方法

root=null;//初始化根節(jié)點

}publicvoidInsert(charelement){//往二叉搜索樹插入一個節(jié)點

Nodetmp,parent=null,currentNode=null;Find(element,refparent,refcurrentNode);if(currentNode!=null){//檢查要插入的結(jié)點是否已經(jīng)存在

Console.WriteLine("不允許插入重復(fù)的字符");return;}else{//如果這個節(jié)點不存在

tmp=newNode(element,null,null);//創(chuàng)建一個節(jié)點

if(parent==null)//如果樹是空的

root=tmp;elseif(element<parent.splitChar)parent.loNode=tmp;elseparent.hiNode=tmp;}}//發(fā)現(xiàn)指定元素的當(dāng)前節(jié)點和它的父節(jié)點

publicvoidFind(charelement,refNodeparent,refNodecurrentNode){currentNode=root;parent=null;while((currentNode!=null)&&(currentNode.splitChar!=element)){parent=currentNode;if(element<currentNode.splitChar)currentNode=currentNode.loNode;//找左子樹

elsecurrentNode=currentNode.hiNode;//找右子樹

}}}三叉Trie樹為了節(jié)省內(nèi)存，三叉搜索樹只有三個指針，一個指向左邊的樹，一個指向右邊的樹，還有一個向下，指向單詞的下一個數(shù)據(jù)單元。三叉搜索樹是二叉搜索樹和標(biāo)準(zhǔn)Trie樹的混合體。它有和標(biāo)準(zhǔn)Trie樹差不多的速度但是和二叉搜索樹一樣只需要相對較少的內(nèi)存空間?；蛘甙讶嫠阉鳂淇闯芍挥幸粋€槽位的散列，通過左孩子和右孩子來解決沖突。ibsntasteyhonrftoeasatbebyheinisitofonorto黃色節(jié)點是第一層節(jié)點三叉Trie樹的節(jié)點-TSTNodepublicsealedclassTSTNode{publicStringdata;//存儲值信息

publicTSTNodeloNode;//左邊的兄弟節(jié)點

publicTSTNodeeqNode;//孩子節(jié)點

publicTSTNodehiNode;//右邊的兄弟節(jié)點

publiccharspliter;//分隔字符

publicTSTNode(charkey){this.spliter=key;}publicoverrideStringToString(){returnString.Format("{0},{1}",spliter,data);}}構(gòu)建三叉Trie樹publicTSTNoderootNode;//樹的根節(jié)點publicTSTNodeCreatTSTNode(Stringkey){if(key==null){thrownewException("空指針異常");}if(rootNode==null){//創(chuàng)建根節(jié)點

rootNode=newTSTNode(key[0]);}intcharIndex=0;TSTNodecurrentNode=rootNode;while(true){intcompa=key[charIndex]-currentNode.spliter;//比較詞的當(dāng)前字符與節(jié)點的當(dāng)前字符

if(compa==0){charIndex++;//下一個字符

if(charIndex==key.Length){//已經(jīng)創(chuàng)建完畢

returncurrentNode;}if(currentNode.eqNode==null){//創(chuàng)建孩子節(jié)點

currentNode.eqNode=newTSTNode(key[charIndex]);}currentNode=currentNode.eqNode;//進入下一層子樹

}elseif(compa<0){if(currentNode.loNode==null){//左邊的兄弟節(jié)點

currentNode.loNode=newTSTNode(key[charIndex]);}currentNode=currentNode.loNode;//查找左邊的子樹

}else{if(currentNode.hiNode==null){//右邊的兄弟節(jié)點

currentNode.hiNode=newTSTNode(key[charIndex]);}currentNode=currentNode.hiNode;//查找右邊的子樹

}}}查找三叉Trie樹查找axibsntasteyhonrftoe匹配的過程大中學(xué)活心生心動生活中心當(dāng)前節(jié)點大中當(dāng)前字符中中查找三叉Trie樹-最大長度匹配//輸入查詢詞和偏移量，輸出找到的最長匹配詞publicStringMaxMatch(Stringkey,intoffset){Stringret=null;if(key==null||rootNode==null||"".Equals(key)){returnret;}TSTNodecurrentNode=rootNode;//樹的當(dāng)前節(jié)點的位置intcharIndex=offset;//當(dāng)前要比較的字符在輸入字符串中的位置while(true){if(currentNode==null){//到達(dá)樹的盡頭returnret;}intp=key[charIndex]-currentNode.spliter;if(p==0){charIndex++;if(currentNode.data!=null){ret=currentNode.data;//候選最長匹配詞}if(charIndex==key.Length){returnret;//已經(jīng)匹配完}currentNode=currentNode.eqNode;//進入下一層子樹}elseif(p<0){currentNode=currentNode.loNode;//查找左邊的子樹}else{currentNode=currentNode.hiNode;//查找右邊的子樹}}}測試正向最大長度匹配從前往后匹配待切分的字符串Stringsentence="大學(xué)生活動中心";//輸入字符串intoffset=0;//匹配的開始位置Stringret=dic.MaxMatch(sentence,offset);System.Console.WriteLine(sentence+“匹配上:"+ret);第一次匹配上:大學(xué)生第二次匹配上:活動第三次匹配上:中心配置文件<configuration><appSettings><addkey="seg.dir"value="D:/lietu/dic"/></appSettings></configuration>詞典路徑publicstaticStringdicDir=System.Configuration.ConfigurationManager.AppSettings["seg.dir"];讀入詞典路徑從文本加載詞典StreamReaderinput=newStreamReader(fileName,System.Text.Encoding.GetEncoding("gb2312"));Stringline;while((line=input.ReadLine())!=null){//讀入一行StringTokenizerst=newStringTokenizer(line,"\t");Stringkey=st.NextToken();//詞intcost=Convert.ToInt32(st.NextToken());//詞頻

TSTNodecurrentNode=CreatTSTNode(key);//創(chuàng)建詞相關(guān)的節(jié)點currentNode.data=key;}單件(Singleton)模式每類詞典只保留一個實例publicstaticWordDicInstance(){ returnNested.instance;}classNested{ //延遲初始化

staticNested() { } internalstaticreadonlyWordDicinstance=newWordDic();}HashMapvsTrie樹HashMap和Trie樹都支持contains(key)get(key)Trie樹還支持前綴查找匹配英文連續(xù)出現(xiàn)的英文無論是否在詞表中出現(xiàn)過，都當(dāng)成整個詞處理“ATM柜員機”這個字符串前綴開始的詞集合是“ATM”。這里的“ATM”并不一定存在于當(dāng)前的詞典中。匹配英文//輸入匹配的字符串和開始位置//返回第一個不是英文字符的位置publicstaticintMatchEnglish(Stringkey,intstart){inti=start;while(i<key.Length){charc=key[i];if(c>='a'&&c<='z'||c>='A'&&c<='Z'){++i;}else