發(fā)布時(shí)間：2017-05-15 14:25

  本文關(guān)鍵詞：SA-IS算法的外存實(shí)現(xiàn)技術(shù)及其優(yōu)化，由筆耕文化傳播整理發(fā)布。

【摘要】：后綴數(shù)組是由字符串中所有后綴按照字典順序排序后組成的數(shù)據(jù)結(jié)構(gòu)，是構(gòu)建全文索引的有力工具。相比于后綴樹，后綴數(shù)組構(gòu)建的索引結(jié)構(gòu)具有占用空間更小、構(gòu)建速度更快等特點(diǎn)。這在當(dāng)前的互聯(lián)網(wǎng)信息檢索和生物信息學(xué)等研究領(lǐng)域具有很高的應(yīng)用價(jià)值。 自從1990年U.Manber與G.Myers[1]提出后綴數(shù)組的概念后，近年來(lái)后綴數(shù)組構(gòu)造算法的研究取得了較大進(jìn)展。如KSP[2]、KA[3]和SA-IS[4]算法。然而隨著當(dāng)前數(shù)據(jù)量的增大，傳統(tǒng)后綴數(shù)組構(gòu)造算法由于受到內(nèi)存的限制，因此處理大規(guī)模字符串的能力有限。那么對(duì)于如何能夠在外存上完成后綴數(shù)組構(gòu)建的技術(shù)研究就顯得十分必要。 本文介紹了種基于SA-IS后綴數(shù)組構(gòu)造算法的外存實(shí)現(xiàn)技術(shù)，并指出了其實(shí)現(xiàn)中導(dǎo)致其外存I/O量過大問題的原因。文中我們通過分析其I/O量過大的原因提出了我們的優(yōu)化實(shí)現(xiàn)。我們?cè)趦?yōu)化實(shí)現(xiàn)中針對(duì)原實(shí)現(xiàn)中外存單桶塊處理中存在冗余排序的問題，我們通過利用其SA分塊中不同區(qū)域數(shù)據(jù)的特點(diǎn)，優(yōu)化了其推導(dǎo)排序SA元素的過程；并針對(duì)原實(shí)現(xiàn)外存塊處理中，關(guān)聯(lián)PCI過程利用外存作為輔助排序空間會(huì)產(chǎn)生較大I/O的問題，我們優(yōu)化了其關(guān)聯(lián)PCI的步驟，較大幅度的降低了該過程的I/O量，提高了程序的執(zhí)行效率。文中我們介紹了優(yōu)化部分的實(shí)現(xiàn)，同時(shí)通過實(shí)驗(yàn)的方式驗(yàn)證了優(yōu)化實(shí)現(xiàn)在性能上的提升。
【關(guān)鍵詞】：后綴數(shù)組 外存 線性復(fù)雜度 優(yōu)化
【學(xué)位授予單位】：中山大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP333;TP301.6
【目錄】：

• 摘要3-4
• Abstract4-6
• 第一章 綜述6-12
• 1.1 研究背景與意義6-7
• 1.2 研究現(xiàn)狀7-10
• 1.3 論文主要工作10
• 1.4 論文結(jié)構(gòu)10-12
• 第二章 后綴數(shù)組構(gòu)造算法介紹12-25
• 2.1 定義及名詞解釋12-13
• 2.2 Induced-Sorting 與遞歸排序13-23
• 2.3 本章小結(jié)23-25
• 第三章 SA-IS 算法外存實(shí)現(xiàn)技術(shù)及優(yōu)化實(shí)現(xiàn)25-55
• 3.1 SA-IS 算法的外存實(shí)現(xiàn)技術(shù)介紹25-29
• 3.2 外存實(shí)現(xiàn)技術(shù)的優(yōu)化29-51
• 3.3 性能分析與對(duì)比51-54
• 3.4 本章小結(jié)54-55
• 第四章 對(duì)比試驗(yàn)及數(shù)據(jù)分析55-63
• 4.1 實(shí)驗(yàn)環(huán)境55-56
• 4.2 實(shí)驗(yàn)內(nèi)容56-62
• 4.3 實(shí)驗(yàn)總結(jié)62-63
• 第五章 總結(jié)與展望63-65
• 5.1 論文總結(jié)63
• 5.2 研究展望63-65
• 參考文獻(xiàn)65-67
• 致謝67

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 王琢;鮑玉斌;;一種快速生成最小濃縮數(shù)據(jù)立方的算法[J];小型微型計(jì)算機(jī)系統(tǒng);2005年12期

2 羅可;張學(xué)茂;;一種高效的頻集挖掘算法[J];長(zhǎng)沙理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

3 劉彩云;陳忠;;蟻群算法的研究進(jìn)展及應(yīng)用[J];軟件導(dǎo)刊;2008年09期

4 張麗芳;;3種聚類算法性能比較分析[J];長(zhǎng)江大學(xué)學(xué)報(bào)(自然科學(xué)版)理工卷;2009年02期

5 劉曉平;圖象開窗算法[J];CT理論與應(yīng)用研究;1996年04期

6 江少鋒,楊素華;一種簡(jiǎn)單高效的圖象縮小算法[J];南昌航空工業(yè)學(xué)院學(xué)報(bào)(自然科學(xué)版);2003年04期

7 張林;吳振強(qiáng);;一種高效的隨機(jī)混淆匿名算法[J];計(jì)算機(jī)應(yīng)用研究;2008年05期

8 蔡濤,王潤(rùn)生;分開合并算法的若干討論和改進(jìn)[J];國(guó)防科技大學(xué)學(xué)報(bào);2000年04期

9 王子菡,楊恢先,楊穗,陶霞;數(shù)控繪圖系統(tǒng)中的繪圖基本算法[J];微計(jì)算機(jī)信息;2003年12期

10 嚴(yán)建峰;李偉華;杜北;;基于規(guī)模壓縮的混合蟻群算法[J];控制與決策;2007年09期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前10條

1 尹冀鋒;;一種新的圖象自適應(yīng)增強(qiáng)算法[A];四川省通信學(xué)會(huì)一九九二年學(xué)術(shù)年會(huì)論文集[C];1992年

2 寧春平;田家瑋;郭延輝;王影;張英濤;鄭桂霞;劉研;;計(jì)算機(jī)輔助增強(qiáng)、分割算法在鑒別乳腺良、惡性腫塊中的應(yīng)用價(jià)值[A];中華醫(yī)學(xué)會(huì)第十次全國(guó)超聲醫(yī)學(xué)學(xué)術(shù)會(huì)議論文匯編[C];2009年

3 謝麗聰;;SVB查詢改寫算法的改進(jìn)[A];第二十一屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2004年

4 鄭存紅;;復(fù)雜背景下相關(guān)跟蹤算法研究及DSP實(shí)現(xiàn)[A];中國(guó)光學(xué)學(xué)會(huì)2010年光學(xué)大會(huì)論文集[C];2010年

5 楊文杰;吳軍;;RFID抗沖突算法研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（上）[C];2008年

6 高山;畢篤彥;魏娜;;一種基于UPF的小目標(biāo)TBD算法[A];第十四屆全國(guó)圖象圖形學(xué)學(xué)術(shù)會(huì)議論文集[C];2008年

7 周磊;張衛(wèi)華;王曉奇;張軍;;基于流水算法的智能路障機(jī)器人設(shè)計(jì)[A];2011年全國(guó)電子信息技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2011年

8 李偉偉;蔡康穎;鄭新;王文成;;3D模型中重復(fù)結(jié)構(gòu)的多尺度快速檢測(cè)算法[A];第六屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會(huì)議（HHME2010)、第19屆全國(guó)多媒體學(xué)術(shù)會(huì)議（NCMT2010）、第6屆全國(guó)人機(jī)交互學(xué)術(shù)會(huì)議（CHCI2010）、第5屆全國(guó)普適計(jì)算學(xué)術(shù)會(huì)議（PCC2010）論文集[C];2010年

9 潘巍;李戰(zhàn)懷;陳群;索博;李衛(wèi)榜;;面向MapReduce的非對(duì)稱分片復(fù)制連接算法優(yōu)化技術(shù)研究[A];第29屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

10 楊任爾;陳懇;勵(lì)金祥;;基于棱邊方向檢測(cè)的運(yùn)動(dòng)自適應(yīng)去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

1 國(guó)泰君安資產(chǎn)管理部;“算法交易”是道指暴跌罪魁禍?zhǔn)?[N];上海證券報(bào);2010年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 張冬麗;人工蜂群算法的改進(jìn)及相關(guān)應(yīng)用研究[D];燕山大學(xué);2014年

2 徐悅竹;機(jī)會(huì)發(fā)現(xiàn)算法及其應(yīng)用研究[D];哈爾濱工程大學(xué);2010年

3 王征;分布式互斥算法的研究與實(shí)現(xiàn)[D];電子科技大學(xué);2007年

4 楊世品;P系統(tǒng)優(yōu)化算法及應(yīng)用研究[D];浙江大學(xué);2013年

5 王艷嬌;人工蜂群算法的研究與應(yīng)用[D];哈爾濱工程大學(xué);2013年

6 張毅;群智能算法的改進(jìn)及其在相關(guān)領(lǐng)域中的應(yīng)用[D];吉林大學(xué);2009年

7 劉叢;基于進(jìn)化算法的聚類方法研究[D];華東師范大學(xué);2013年

8 孫玉芬;基于網(wǎng)格方法的聚類算法研究[D];華中科技大學(xué);2006年

9 吳俊;視像概念檢測(cè)中在線學(xué)習(xí)算法研究[D];清華大學(xué);2008年

10 李天恩;基于混合算法的過程故障可拒絕模式分類方法研究[D];天津大學(xué);2012年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 韓文成;基于分解的正向相容算法研究[D];吉林大學(xué);2010年

2 聶堅(jiān);一種改進(jìn)的進(jìn)化算法及其在帶噪聲干擾優(yōu)化中的應(yīng)用[D];湘潭大學(xué);2011年

3 劉柱;基于蟻群算法的接單與并行機(jī)加工調(diào)度優(yōu)化決策問題研究[D];南京理工大學(xué);2014年

4 張婕;聚類算法在網(wǎng)頁(yè)分類中的應(yīng)用研究[D];北京化工大學(xué);2013年

5 蔣天弘;基于自然最近鄰居的社團(tuán)檢測(cè)算法研究[D];重慶大學(xué);2014年

6 白雪;一種基于網(wǎng)格的密度聚類算法研究及應(yīng)用[D];哈爾濱工程大學(xué);2009年

7 汪彩霞;視頻交通分析中背景估計(jì)與更新算法研究[D];長(zhǎng)安大學(xué);2010年

8 周治軍;基于多統(tǒng)計(jì)方法的動(dòng)靜態(tài)多目標(biāo)持續(xù)跟蹤算法研究[D];華北電力大學(xué)（北京）;2011年

9 張惠娟;基于貝葉斯濾波的先跟蹤后檢測(cè)算法研究[D];西北工業(yè)大學(xué);2006年

10 邱曉蕾;基于網(wǎng)格的密度聚類算法[D];上海師范大學(xué);2006年

  本文關(guān)鍵詞：SA-IS算法的外存實(shí)現(xiàn)技術(shù)及其優(yōu)化，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：368051