外存全文索引算法的研究.pdf

1、對(duì)數(shù)據(jù)建立索引并提供檢索功能是人們面對(duì)海量數(shù)據(jù)時(shí)的基本要求，在互聯(lián)網(wǎng)時(shí)代尤為如此。在數(shù)據(jù)庫(kù)中檢索所需要的記錄，在web信息中搜索符合自己要求的網(wǎng)頁(yè)都需要對(duì)數(shù)據(jù)建立索引結(jié)構(gòu)，對(duì)于法律文件，生物信息學(xué)中的DNA數(shù)據(jù)更需要支持全文匹配功能。索引結(jié)構(gòu)包括外存索引和內(nèi)存索引結(jié)構(gòu)。對(duì)于后綴樹和后綴數(shù)組等經(jīng)典數(shù)據(jù)結(jié)構(gòu)來說，雖然匹配速度快，但占用空間很大。壓縮全文索引如CSA與FM-Index不適用于外存結(jié)構(gòu)。
　　本文提出了一種空間和時(shí)間高效的

2、外存壓縮索引mKD-GBWT。理論上，mKD-GBWT壓縮索引所占空間為O(nlogσ)位；可在O(|P|/B+√n/B+occ/B)I/Os內(nèi)支持模式匹配查詢，其中|P|為模式長(zhǎng)度，n為文本規(guī)模，n為字符表大小，B為磁盤塊大小。
　　本文提出了mKD-GBWT中高效外存串B-樹算法、kd-樹的外存存儲(chǔ)結(jié)構(gòu)及其正交范圍查找算法；然后詳細(xì)描述了mKD-GBWT采用多棵kd-樹作為其正交范圍查找結(jié)構(gòu)的原理及其模式匹配算法；分析了mKD

3、-GBWT索引的時(shí)空性能，最后高效地實(shí)現(xiàn)了mKD-GBWT索引；并針對(duì)各類數(shù)據(jù)（如分布均勻數(shù)據(jù)、有偏數(shù)據(jù)、高度重復(fù)數(shù)據(jù)等）進(jìn)行了較為廣泛的實(shí)驗(yàn)，實(shí)驗(yàn)表明，與2015年最新外存壓縮索引GBWT相比，所提算法在實(shí)際中不僅存儲(chǔ)空間高效，而且具有良好的I/O性能。
　　在工程方面，為了降低索引大小，本文提出采用crit-bit樹作為串B-樹中一個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，利用串B-樹存儲(chǔ)靜態(tài)數(shù)據(jù)的特點(diǎn)將串B-樹按照從左至右自底向上的順序存儲(chǔ)，避免了

4、顯式存儲(chǔ)串B-樹每個(gè)內(nèi)部節(jié)點(diǎn)中的孩子指針，同時(shí)改進(jìn)了kd-樹的外存序列化算法提高了存儲(chǔ)kd-樹的磁盤頁(yè)的空間利用率。為了提高查詢效率，本文首先改進(jìn)了串B-樹的后綴范圍查找算法避免了對(duì)搜索過程中重疊路徑上節(jié)點(diǎn)的重復(fù)訪問，然后利用mKD-GBWT模式匹配過程中所需要查詢的正交范圍只會(huì)位于一個(gè)劃分的子區(qū)間內(nèi)的特點(diǎn)，提出采用多棵kd-樹作為mKD-GBWT索引的正交范圍查找結(jié)構(gòu)，每棵kd-樹僅存儲(chǔ)部分點(diǎn)集，這樣在進(jìn)行正交范圍查找時(shí)只需要在其中一