基于雙數(shù)組Trie(Double-Array+Trie)的詞典查詢算法.ppt

1、基于雙數(shù)組樹的字典查詢算法、王消費2004-9-17、概述、字典查詢算法介紹雙數(shù)組樹數(shù)據(jù)結(jié)構(gòu)基于雙數(shù)組樹的字典查詢算法問題和幾個茄子改進、預查詢算法介紹、中文信息處理系統(tǒng)因此，中文詞典的快速查詢對整個系統(tǒng)的效率有著非常重要的影響。大多數(shù)字典結(jié)構(gòu)基于散列方法。牙齒方法的關(guān)鍵技術(shù)在于散列函數(shù)設計，以合理的方式分配數(shù)據(jù)塊曹征，控制分布的均勻性，減少沖突，提高空間利用率。介紹字典查詢算法，目前有幾個茄子典型的字典查詢方法：1。全字二分法2。樹索引樹方法3。逐字二分法，字典查詢算法介紹，全字二分法結(jié)構(gòu)：第一個散列列表，單詞索引表，字典正文優(yōu)點：數(shù)據(jù)結(jié)構(gòu)簡單，占用空間小。缺點：全字匹配，效率相對不高。Ti

2、re索引樹結(jié)構(gòu)：第一個哈希表，Trie索引樹節(jié)點優(yōu)點：分詞不需要估計要查詢的單詞的長度，而是沿著樹鏈逐字匹配。缺點：結(jié)構(gòu)和維護比較復雜，單詞樹枝多，浪費了一定的空間。逐字二分法結(jié)構(gòu)：全詞二分法的優(yōu)點：查詢逐字匹配，提高一定的匹配效率。缺點：由于字典結(jié)構(gòu)沒有變化，效率提高受到限制。雙數(shù)組Trie的數(shù)據(jù)結(jié)構(gòu)，Trie樹：Trie樹是一種搜索樹。、a b c d g t、l u、樹的空間復雜性是O(n)的缺點數(shù)據(jù)結(jié)構(gòu)復雜性、查詢效率下降、樹實用性實現(xiàn)算法空間消耗小的同時，為了確保查詢效率，Aoe、J提出了兩個線性陣列的樹樹表示，即雙陣列樹。Check:與當前狀態(tài)的上一個狀態(tài)相同。對于從狀態(tài)s到狀態(tài)t

3、的轉(zhuǎn)換，必須滿足checkbases c=s bases c=t。其中c是輸入變量。雙數(shù)組Trie的數(shù)據(jù)結(jié)構(gòu)，s，t，c，base，check，s，t，c，基于雙數(shù)組Trie的字典查詢算法，基本思路：根據(jù)6763個常用漢字內(nèi)部代碼授予16763個順序，第一個順序代碼為I的單詞為N個依次估計第三個單詞，第四個單詞k單詞的位置。如果Basei和checki都為零，則位置為空。Basei為負數(shù)表示狀態(tài)是一個詞。雙數(shù)組基于Trie的字典查詢算法，數(shù)組構(gòu)造角漢字，確定相應的base值，以便從數(shù)組中放下以該漢字開頭的所有單詞。也就是說，baseka1、checka1、baseka2、checka2、bas

4、ekan、checkan牙齒都是查找以0、a1、a2an牙齒I開頭的單詞的第二個順序代碼k=basei，這是基于雙數(shù)組樹的字典if checkt=s then next state :=t else fail endif，基于雙數(shù)組Trie的字典查詢算法，雙數(shù)組配置完成后，查詢默認情況下會將要查找的單詞中的每個單詞轉(zhuǎn)換為相應的順序代碼，然后多次相加，即可找到該單詞。祖懷效率很高?；陔p數(shù)組樹的字典查詢算法，在節(jié)點添加詞典添加新詞時，將新節(jié)點添加到樹樹中。如果新插入的變量為c，則basebasei c=0牙齒非空，必須重置basei和以后的相關(guān)鍵。、I、basei c、基于雙數(shù)組樹的字典查詢算法

5、、Procedure Relocate(s : state)；b : base _ index)move base for state s to a new place beginning at b begin for each input character c for the state s I . e . for each c SSS段宜恩ownningcopy data the node bases c is to be moved to b c；Hence，for any I for which checki=bases c，update checki to b c for each

6、 input character d for the node bases c begin checkbase bases c d 33666Bases :=b end，基于雙數(shù)組樹的字典查詢算法，Base，check，b，bases，s，t，t，baset，u，c， 要檢查“阿根廷”，請先根據(jù)“啊”的順序代碼2獲取base9=1，然后根據(jù)“根”的順序代碼4獲取狀態(tài)為“agan”的數(shù)組下標為base24=5，check9=5=。基于雙數(shù)組樹的字典查詢算法、算法時間和空間復雜性根據(jù)以前的分析，牙齒算法查詢避免了字符串比較、copy操作等步驟，直接執(zhí)行數(shù)字計算和數(shù)組讀取，因此時間比其他查詢算法要快。三個茄子查詢算法的比較、基于雙數(shù)組樹的字典查詢算法，以及在空間中具有空間大小5，650，000字節(jié)的主詞典，增加數(shù)組結(jié)構(gòu)大約需要1，440，000字節(jié)，總共需要7，090，000字節(jié)。存在的問題，數(shù)據(jù)結(jié)構(gòu)上不可避免的空間浪費。在配置曹征期間，每個狀態(tài)都取決于不同的狀態(tài)，因此在詞典中插入或刪除單詞時，經(jīng)常需要全局調(diào)整雙數(shù)組結(jié)構(gòu)。靈活性差。不是只有詞匯中的第一個字母按順序代碼放入數(shù)組，而是將6763個常用字符全部放入