Trie樹查詢
基于三數(shù)組Trie索引樹原理的漢語詞典查詢機(jī)制,并用遞歸算法實(shí)現(xiàn)構(gòu)詞狀態(tài)表的自動(dòng)構(gòu)建.
Trie樹是搜索樹的一種，來自英文單詞"Retrieval"的簡寫，可以建立有效的數(shù)據(jù)檢索組織結(jié)構(gòu)，是中文匹配分詞算法中詞典的一種常見實(shí)現(xiàn)。它本質(zhì)上是一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)(DFA)，每個(gè)節(jié)點(diǎn)代表自動(dòng)機(jī)的一個(gè)狀態(tài)。在詞典中這此狀態(tài)包括"詞前綴"，"已成詞"等。Trie樹就是字典樹，其核心思想就是空間換時(shí)間.字典樹有如下簡單的性質(zhì)：
(1) 根節(jié)點(diǎn)不包含字符信息;
(2) 一棵m度的Trie或者為空，或者由m棵m度的Trie組成。
搜索字典項(xiàng)目的方法為：
(1) 從根結(jié)點(diǎn)開始一次搜索;
(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹，轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索;
(3) 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個(gè)字母，并進(jìn)一步選擇對(duì)應(yīng)的子樹進(jìn)行檢索。
(4) 迭代過程……
(5) 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。
雙數(shù)組Trie(Double-Array Trie)是trie樹的一個(gè)簡單而有效的實(shí)現(xiàn)，由兩個(gè)整數(shù)數(shù)組構(gòu)成，一個(gè)是base[]，另一個(gè)是check[]。設(shè)數(shù)組下標(biāo)為i ,如果base,check均為0,表示該位置為空。如果base為負(fù)值，表示該狀態(tài)為詞語。Check表示該狀態(tài)的前一狀態(tài)，t=base+a, check[t]=i 。
相關(guān)文章推薦：
往年廣本筆試題分享
最新中國平安筆試題分享
建筑學(xué)筆試題分享
中國人壽保險(xiǎn)的筆試分享
德勤consulting筆試過程
光大期貨筆試真題
河北新聞網(wǎng)兩學(xué)一做知識(shí)競賽(試題+答案完整版)
河北新聞網(wǎng)兩學(xué)一做知識(shí)競賽活動(dòng)試題答案
兩學(xué)一做學(xué)習(xí)教育知識(shí)競賽活動(dòng)10篇
開展兩學(xué)一做學(xué)習(xí)教育知識(shí)競賽活動(dòng)真題答案
