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

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

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

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

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