【摘要】：字符串搜索被廣泛應(yīng)用于搜索引擎,網(wǎng)絡(luò)入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等諸多問題中。為了有效進行字符串搜索,需要一個合適的存儲和管理字符串的數(shù)據(jù)結(jié)構(gòu)。Trie是一種有效的字符串處理的經(jīng)典數(shù)據(jù)結(jié)構(gòu),尤其適合字符串查找以及前綴查找。常見的Trie樹存儲方式有矩陣存儲和鏈式存儲兩種,矩陣存儲查詢速度快但存在空間浪費嚴重的問題,鏈式存儲空間利用率高但查詢效率比較低。而雙數(shù)組Trie能有效結(jié)合Trie樹上述兩種表現(xiàn)形式的優(yōu)點,在具有低的存儲空間的同時,具有高的查詢效率。雙數(shù)組Trie雖然結(jié)合了上述Trie樹的兩種表現(xiàn)形式的一些優(yōu)點,但其創(chuàng)建的效率隨著數(shù)據(jù)量的增加而出現(xiàn)急劇下降的情況。針對此問題,本文通過對雙數(shù)組Trie索引創(chuàng)建過程深入分析和研究發(fā)現(xiàn),索引創(chuàng)建效率降低的主要原因在于索引創(chuàng)建的過程產(chǎn)生的沖突及沖突處理的開銷。為此,本文提出了一種分區(qū)雙數(shù)組Trie索引結(jié)構(gòu)來提高索引創(chuàng)建的效率,該結(jié)構(gòu)主要從以下兩個角度提升索引創(chuàng)建的效率:1)開發(fā)字典序即將字符串數(shù)據(jù)集按照字典序進行升序排序,從而可減少索引創(chuàng)建過程中發(fā)生沖突時移動的數(shù)據(jù)量。2)創(chuàng)建首字符分區(qū)的分區(qū)雙數(shù)組結(jié)構(gòu)從而可降低沖突的數(shù)量以及減少解決沖突所產(chǎn)生的開銷。實驗結(jié)果表明,本文提出的分區(qū)雙數(shù)組Trie索引結(jié)構(gòu)可同時降低沖突的數(shù)量及處理沖突的開銷,在大幅提高索引創(chuàng)建的效率的同時,還可進一步提高索引的查詢效率。為了能進一步提高雙數(shù)組Trie索引創(chuàng)建的效率,本文在多核平臺上基于OpenMP進行并行雙數(shù)組結(jié)構(gòu)的的研究。為實現(xiàn)高效的并行,本文進一步提出一種等字符串數(shù)量的高效分區(qū)策略,從而使得線程之間的負載盡量均衡。并通過擴展實驗對比了在不同分區(qū)策略下索引創(chuàng)建和查詢算法的性能,實驗結(jié)果表明,相對于串行的創(chuàng)建索引,并行創(chuàng)建雙數(shù)組Trie索引在性能上有著可觀的提升。
【學位授予單位】：昆明理工大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP391.3
【圖文】：

集合K的Arraytrie

昆明理工大學碩士學位論文樣的實現(xiàn)，空置指針的數(shù)量是非常龐大的。Trie 樹的另一種常見的存儲形式即 List Trie[47]樹，與 array trie 樹相比，更加緊湊。在 Array trie 這種數(shù)據(jù)結(jié)構(gòu)中，每一級的數(shù)組的長度都是不的，所以其存儲空間是非常浪費的。但是，如果每一層數(shù)組的長度是可層結(jié)點的數(shù)量進行動態(tài)的調(diào)整，那么這樣就可以避免大量的空間浪費，節(jié)省空間的目的。如圖 2.3 所示。

【參考文獻】

相關(guān)期刊論文 前3條

1 郜國良;李廣軍;;一種基于Trie的快速IP路由查找算法[J];微電子學與計算機;2011年06期

2 蔣文明;張雪英;李伯秋;;基于條件隨機場的中文地址要素識別方法[J];計算機工程與應(yīng)用;2010年13期

3 王思力;張華平;王斌;;雙數(shù)組Trie樹算法優(yōu)化及其應(yīng)用研究[J];中文信息學報;2006年05期

相關(guān)碩士學位論文 前4條

1 張欣園;多核環(huán)境下的生物信息序列比對并行優(yōu)化方法的研究[D];黑龍江大學;2015年

2 王燕;字符串相似度連接算法研究[D];燕山大學;2013年

3 姜英杰;支持正則表達式的文本匹配優(yōu)化算法[D];東北大學;2012年

4 李建偉;基于多核多線程技術(shù)的通信網(wǎng)仿真算法研究[D];南京郵電大學;2011年

本文編號：2777066