SA-IS算法的外存实现技术及其优化

发布时间：2017-05-15 14:25

  本文关键词：SA-IS算法的外存实现技术及其优化，由笔耕文化传播整理发布。

【摘要】：后缀数组是由字符串中所有后缀按照字典顺序排序后组成的数据结构，是构建全文索引的有力工具。相比于后缀树，后缀数组构建的索引结构具有占用空间更小、构建速度更快等特点。这在当前的互联网信息检索和生物信息学等研究领域具有很高的应用价值。 自从1990年U.Manber与G.Myers[1]提出后缀数组的概念后，近年来后缀数组构造算法的研究取得了较大进展。如KSP[2]、KA[3]和SA-IS[4]算法。然而随着当前数据量的增大，传统后缀数组构造算法由于受到内存的限制，因此处理大规模字符串的能力有限。那么对于如何能够在外存上完成后缀数组构建的技术研究就显得十分必要。 本文介绍了种基于SA-IS后缀数组构造算法的外存实现技术，并指出了其实现中导致其外存I/O量过大问题的原因。文中我们通过分析其I/O量过大的原因提出了我们的优化实现。我们在优化实现中针对原实现中外存单桶块处理中存在冗余排序的问题，我们通过利用其SA分块中不同区域数据的特点，优化了其推导排序SA元素的过程；并针对原实现外存块处理中，关联PCI过程利用外存作为辅助排序空间会产生较大I/O的问题，我们优化了其关联PCI的步骤，较大幅度的降低了该过程的I/O量，提高了程序的执行效率。文中我们介绍了优化部分的实现，同时通过实验的方式验证了优化实现在性能上的提升。
【关键词】：后缀数组 外存 线性复杂度 优化
【学位授予单位】：中山大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP333;TP301.6
【目录】：

• 摘要3-4
• Abstract4-6
• 第一章 综述6-12
• 1.1 研究背景与意义6-7
• 1.2 研究现状7-10
• 1.3 论文主要工作10
• 1.4 论文结构10-12
• 第二章 后缀数组构造算法介绍12-25
• 2.1 定义及名词解释12-13
• 2.2 Induced-Sorting 与递归排序13-23
• 2.3 本章小结23-25
• 第三章 SA-IS 算法外存实现技术及优化实现25-55
• 3.1 SA-IS 算法的外存实现技术介绍25-29
• 3.2 外存实现技术的优化29-51
• 3.3 性能分析与对比51-54
• 3.4 本章小结54-55
• 第四章 对比试验及数据分析55-63
• 4.1 实验环境55-56
• 4.2 实验内容56-62
• 4.3 实验总结62-63
• 第五章 总结与展望63-65
• 5.1 论文总结63
• 5.2 研究展望63-65
• 参考文献65-67
• 致谢67

【相似文献】

中国期刊全文数据库 前10条

1 王琢;鲍玉斌;;一种快速生成最小浓缩数据立方的算法[J];小型微型计算机系统;2005年12期

2 罗可;张学茂;;一种高效的频集挖掘算法[J];长沙理工大学学报(自然科学版);2006年03期

3 刘彩云;陈忠;;蚁群算法的研究进展及应用[J];软件导刊;2008年09期

4 张丽芳;;3种聚类算法性能比较分析[J];长江大学学报(自然科学版)理工卷;2009年02期

5 刘晓平;图象开窗算法[J];CT理论与应用研究;1996年04期

6 江少锋,杨素华;一种简单高效的图象缩小算法[J];南昌航空工业学院学报(自然科学版);2003年04期

7 张林;吴振强;;一种高效的随机混淆匿名算法[J];计算机应用研究;2008年05期

8 蔡涛,王润生;分开合并算法的若干讨论和改进[J];国防科技大学学报;2000年04期

9 王子菡,杨恢先,杨穗,陶霞;数控绘图系统中的绘图基本算法[J];微计算机信息;2003年12期

10 严建峰;李伟华;杜北;;基于规模压缩的混合蚁群算法[J];控制与决策;2007年09期

中国重要会议论文全文数据库 前10条

1 尹冀锋;;一种新的图象自适应增强算法[A];四川省通信学会一九九二年学术年会论文集[C];1992年

2 宁春平;田家玮;郭延辉;王影;张英涛;郑桂霞;刘研;;计算机辅助增强、分割算法在鉴别乳腺良、恶性肿块中的应用价值[A];中华医学会第十次全国超声医学学术会议论文汇编[C];2009年

3 谢丽聪;;SVB查询改写算法的改进[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

4 郑存红;;复杂背景下相关跟踪算法研究及DSP实现[A];中国光学学会2010年光学大会论文集[C];2010年

5 杨文杰;吴军;;RFID抗冲突算法研究[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

6 高山;毕笃彦;魏娜;;一种基于UPF的小目标TBD算法[A];第十四届全国图象图形学学术会议论文集[C];2008年

7 周磊;张卫华;王晓奇;张军;;基于流水算法的智能路障机器人设计[A];2011年全国电子信息技术与应用学术会议论文集[C];2011年

8 李伟伟;蔡康颖;郑新;王文成;;3D模型中重复结构的多尺度快速检测算法[A];第六届和谐人机环境联合学术会议（HHME2010)、第19届全国多媒体学术会议（NCMT2010）、第6届全国人机交互学术会议（CHCI2010）、第5届全国普适计算学术会议（PCC2010）论文集[C];2010年

9 潘巍;李战怀;陈群;索博;李卫榜;;面向MapReduce的非对称分片复制连接算法优化技术研究[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

10 杨任尔;陈恳;励金祥;;基于棱边方向检测的运动自适应去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

中国重要报纸全文数据库 前1条

1 国泰君安资产管理部;“算法交易”是道指暴跌罪魁祸首?[N];上海证券报;2010年

中国博士学位论文全文数据库 前10条

1 张冬丽;人工蜂群算法的改进及相关应用研究[D];燕山大学;2014年

2 徐悦竹;机会发现算法及其应用研究[D];哈尔滨工程大学;2010年

3 王征;分布式互斥算法的研究与实现[D];电子科技大学;2007年

4 杨世品;P系统优化算法及应用研究[D];浙江大学;2013年

5 王艳娇;人工蜂群算法的研究与应用[D];哈尔滨工程大学;2013年

6 张毅;群智能算法的改进及其在相关领域中的应用[D];吉林大学;2009年

7 刘丛;基于进化算法的聚类方法研究[D];华东师范大学;2013年

8 孙玉芬;基于网格方法的聚类算法研究[D];华中科技大学;2006年

9 吴俊;视像概念检测中在线学习算法研究[D];清华大学;2008年

10 李天恩;基于混合算法的过程故障可拒绝模式分类方法研究[D];天津大学;2012年

中国硕士学位论文全文数据库 前10条

1 韩文成;基于分解的正向相容算法研究[D];吉林大学;2010年

2 聂坚;一种改进的进化算法及其在带噪声干扰优化中的应用[D];湘潭大学;2011年

3 刘柱;基于蚁群算法的接单与并行机加工调度优化决策问题研究[D];南京理工大学;2014年

4 张婕;聚类算法在网页分类中的应用研究[D];北京化工大学;2013年

5 蒋天弘;基于自然最近邻居的社团检测算法研究[D];重庆大学;2014年

6 白雪;一种基于网格的密度聚类算法研究及应用[D];哈尔滨工程大学;2009年

7 汪彩霞;视频交通分析中背景估计与更新算法研究[D];长安大学;2010年

8 周治军;基于多统计方法的动静态多目标持续跟踪算法研究[D];华北电力大学（北京）;2011年

9 张惠娟;基于贝叶斯滤波的先跟踪后检测算法研究[D];西北工业大学;2006年

10 邱晓蕾;基于网格的密度聚类算法[D];上海师范大学;2006年

  本文关键词：SA-IS算法的外存实现技术及其优化，由笔耕文化传播整理发布。

，

本文编号：368051