本文關(guān)鍵詞：一種外存后綴數(shù)組構(gòu)造算法的工程實(shí)現(xiàn)及性能評估，由筆耕文化傳播整理發(fā)布。

【摘要】：后綴數(shù)組最初是作為后綴樹的一種替代被提出的，與后綴樹相比，存儲后綴數(shù)組所需的空間更少，應(yīng)用范圍更廣。在后綴數(shù)組被提出后，后綴數(shù)組作為一種重要的索引數(shù)據(jù)結(jié)構(gòu)，被廣泛的應(yīng)用于生物信息學(xué)、全文索引、字符串匹配、頻繁字符串挖掘以及順序分析和聚類分析等領(lǐng)域。到目前為止，國內(nèi)外關(guān)于后綴數(shù)組構(gòu)造算法的研究已經(jīng)取得了豐碩的成果。但隨著信息技術(shù)的發(fā)展，在許多領(lǐng)域，需要處理的數(shù)據(jù)集日益增長。當(dāng)利用原有后綴數(shù)組內(nèi)存構(gòu)造算法為一個非常大的數(shù)據(jù)集構(gòu)建后綴數(shù)組時，所需的內(nèi)存空間遠(yuǎn)遠(yuǎn)超出了一般商用電腦的內(nèi)存限制。這時，后綴數(shù)組內(nèi)存構(gòu)造算法不再適用，極大的限制了后綴數(shù)組的應(yīng)用范圍。 在本文中，我們探討了一種基于SA-IS算法的后綴數(shù)組外存構(gòu)造算法，對算法的主要思想進(jìn)行了深入分析，從理論上驗(yàn)證了算法的正確性和可行性。在深入理解算法的基礎(chǔ)上，我們采用面向過程的程序設(shè)計(jì)方法對算法加以實(shí)現(xiàn)。在具體實(shí)現(xiàn)過程中，我們對原算法中的PCI和name兩種中間輔助數(shù)據(jù)結(jié)構(gòu)進(jìn)行精簡，通過采用分塊的策略將原算法中所需的外存排序過程轉(zhuǎn)化為多次的內(nèi)存基數(shù)排序過程，保證了算法的執(zhí)行效率和I/O性能。同時，通過實(shí)驗(yàn)對比分析，對算法的性能進(jìn)行評估，最終的實(shí)驗(yàn)結(jié)果顯示，，該算法是線性的并且具有與EM-SA-DS算法相近的性能。
【關(guān)鍵詞】：后綴數(shù)組 外存 構(gòu)造 SA-IS
【學(xué)位授予單位】：中山大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP333
【目錄】：

• 摘要3-4
• Abstract4-7
• 第一章 緒論7-12
• 1.1 研究背景與意義7-8
• 1.2 后綴數(shù)組構(gòu)造算法的研究現(xiàn)狀8-10
• 1.3 研究目標(biāo)與主要工作10-11
• 1.4 論文結(jié)構(gòu)11-12
• 第二章 幾種主流后綴數(shù)組構(gòu)造算法介紹12-24
• 2.1 相關(guān)名詞及符號介紹12-13
• 2.2 SA-IS 算法13-17
• 2.3 EM-SA-DS 算法17-24
• 第三章 一種基于 SA-IS 的后綴數(shù)組外存構(gòu)造算法24-36
• 3.1 相關(guān)符號、概念及定理24-25
• 3.2 算法原理分析25-29
• 3.3 實(shí)例驗(yàn)證29-34
• 3.4 復(fù)雜度分析34-36
• 第四章 算法工程實(shí)現(xiàn)36-59
• 4.1 算法實(shí)現(xiàn)總體框架36-37
• 4.2 數(shù)據(jù)設(shè)計(jì)37-40
• 4.3 流程設(shè)計(jì)40-45
• 4.4 主要函數(shù)具體實(shí)現(xiàn)45-59
• 第五章 實(shí)驗(yàn)設(shè)計(jì)與分析59-66
• 5.1 實(shí)驗(yàn)方案設(shè)計(jì)59-60
• 5.2 實(shí)驗(yàn)數(shù)據(jù)收集與分析60-66
• 第六章 總結(jié)與展望66-68
• 6.1 論文總結(jié)66-67
• 6.2 前景與展望67-68
• 參考文獻(xiàn)68-70
• 致謝70

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

1 王紅;內(nèi)存抖動問題分析及解決對策[J];濰坊高等�？茖W(xué)校學(xué)報(bào);2000年01期

  本文關(guān)鍵詞：一種外存后綴數(shù)組構(gòu)造算法的工程實(shí)現(xiàn)及性能評估，由筆耕文化傳播整理發(fā)布。

本文編號：415594