動(dòng)態(tài)后繼樹(shù)索引壓縮技術(shù)研究.pdf

1、隨著社會(huì)信息化的不斷推進(jìn)，如何對(duì)海量的信息進(jìn)行有效地組織和管理并進(jìn)行快速地查找，是全文檢索技術(shù)面臨的一大挑戰(zhàn)。全文檢索技術(shù)給海量文本信息的管理和查找?guī)?lái)了方便，但是也面臨著存儲(chǔ)空間增加，查詢效率降低的缺點(diǎn)。針對(duì)涉密文本的密文全文檢索技術(shù)，除了存在著時(shí)空效率較低的缺點(diǎn)，還存在著安全性等風(fēng)險(xiǎn)。索引是全文檢索技術(shù)的核心，對(duì)適合海量化，涉密信息的索引結(jié)構(gòu)進(jìn)行研究，并對(duì)索引進(jìn)行壓縮是一項(xiàng)迫切的任務(wù)。
　　 動(dòng)態(tài)后繼樹(shù)(Streamline

2、 Dynamic Successive-Trees，SDST)是最近提出的一種新型索引結(jié)構(gòu)，它具有索引創(chuàng)建速度快、查詢效率高的特點(diǎn)，并且支持索引的動(dòng)態(tài)更新，但是針對(duì)海量及涉密信息，該索引結(jié)構(gòu)的空間效率較低。為實(shí)現(xiàn)海量數(shù)據(jù)存儲(chǔ)空間壓縮，本文對(duì)動(dòng)態(tài)后繼樹(shù)索引結(jié)構(gòu)進(jìn)行改進(jìn)，得到一種新的索引結(jié)構(gòu)：改進(jìn)的動(dòng)態(tài)后繼樹(shù)(Improved Streamline Dynamic Successive-Trees，ISDST)索引結(jié)構(gòu)，并給出其索引創(chuàng)建算法

3、。ISDST索引結(jié)構(gòu)具有與SDST索引結(jié)構(gòu)相同的創(chuàng)建效率。
　　 針對(duì)ISDST索引結(jié)構(gòu)，提出一種索引壓縮策略——樹(shù)葉信息表壓縮（Compressing Leaf Information List, CLIL），給出CLIL算法的描述；根據(jù)查詢?cè)~數(shù)量，分3種情況給出在壓縮的ISDST索引上進(jìn)行查詢和解壓的算法：CLILSR算法、CLILDR算法、CLILMR算法；對(duì)壓縮的ISDST索引結(jié)構(gòu)在空間效率和時(shí)間效率兩個(gè)方面進(jìn)行理論分析

4、，并與倒排文件進(jìn)行實(shí)驗(yàn)對(duì)比。結(jié)果表明，ISDST索引在壓縮效率，查詢效率上均優(yōu)于倒排文件。
　　 為保證索引中涉密信息的安全及空間利用率，本文在密文動(dòng)態(tài)后繼樹(shù)(Streamline Dynamic Successive-Trees of Ciphertext，SDSTC)索引結(jié)構(gòu)的基礎(chǔ)上提出改進(jìn)的密文動(dòng)態(tài)后繼樹(shù)(Improved Streamline Dynamic Successive-Trees of Ciphertext，

5、ISDSTC)索引結(jié)構(gòu)，并給出了其索引創(chuàng)建算法；將ISDST索引的壓縮策略推廣到密文索引，得到改進(jìn)的具有壓縮特性的密文動(dòng)態(tài)后繼樹(shù)(Improved and Compressed Streamline Dynamic Successive-Trees of Ciphertext，ICSDSTC)索引結(jié)構(gòu)，并給出其創(chuàng)建算法；根據(jù)查詢?cè)~的數(shù)量，分3種情況給出ICSDSTC結(jié)構(gòu)上的查詢算法：ICSDSTC_ SR算法、ICSDSTC_DR算法、