试论后缀数组诱导排序算法的优化

《试论后缀数组诱导排序算法的优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文后缀数组诱导排序算法的优化姓名：赵明先申请学位级别：硕士专业：计算机软件与理论指导教师：农革20080508中山大学硕士论文后缀数组诱导排序算法的优化专业：计算机软件与理论硕士生：赵明先指导教师：农革副教授摘要后缀数组构造算法是建立大文本全文索引最主要的方法之一，在网络W．eb搜索以及生物信息学(基因数据库)等领域，有极其重要的应用。由于这方面应用处理的数据是数于亿计的字符，高效的后缀数组构造算法对于数据库索引的建立至关重要。本文基于对一种新的诱导排序算法的分析，针对其使用空

2、间过多，分析了诱导过程三个重要性质，在此基础上优化了类型数组的存储并改进了诱导过程，实现了优化后诱导排序过程算法，并从理论上证明了诱导过程的正确性；然后分析了LMS字符的一个重要性质，在此基础上完善了LMS字符信息的存储，接着结合诱导排序构造后数组算法思想实现了后缀数组构造算法。本文中改进的新算法，在不引入额外空间的情况下，找到消去类型数组存储空间的方法且增加的时间消耗甚微。为了验证优化后诱导排序算法的可行性及其运行效率，我们对所实现的诱导排序构造算法与KS、KA和IS算法进行对比实验，在Cal

3、lterbu巧和Manzinj—Ferra西na数据集上进行验证和性能分析。实验结果显示优化后实现的构造后缀数组算法执行时间比KA算法快30．9％，比KS算法快218．2％，实验数据表明优化后诱导排序算法可在节省算法存储空间的同时，有效的保持算法执行效率，显示优化后的诱导排序算法具有较好的时间空间性能。关键字：诱导排序，分治递归，后缀数组，类型数组，算法设计后缀数组诱导排序算法的优化ontheoptim娩ationofanInduced—SortingSu毋6区ArrayConstruction

4、AlgorithmM面or：CompmerSo小ⅣareandTheo巧N锄e：MingxianZhaoSupervisor：GeN0ngAbstractSumxar】rayconsnⅥctionalgoritllHl，aSoneoftllemostiIllpoIrtantmemodsforbig矗JUtextindexing，hassignificantapplicationsinthefieldofintemetsearclling，biologicalinfornlationscience

5、s(genomedatabase)andsoon．Sincet11eprocessingdataisoRenmeasu．redinbiUionsofcharacters，todesignamoretime-spaceemcientalgorithmford撕baseindexingisofgreatimponaIlce．Inthjsthesis，、Ⅳe删yzearecentlypublishedinduced—sortingalgori也m．AimmingatoVercomingitsshort

6、ageofexcessiVeuseofspace，wepresentthreeimpomIntpropertiesofthepfocessofinduction，baSedonthese，weoptimizethestorageoftypearray，improVetheinductionprocess，andthencarryoutitsimplementation．ARerthat，weprovethattheprocessofoptimizedinduced—sortingiscorrec

7、t．Funhemore，weoptimizethestorageofLMScharactersiⅢ’onnationbyrevealinganimportantpropertyofLMScharacters．Combingwiththeideaoftheinduced—sortingconstmctionalgorimmofsumxarray，wealsoimplementouroptimizedalgoritllnl．Theoptimizedalgori伽nproposedinthispape

8、rcanaVoidusingthe咖e卸∞7锄dwithoutintroducingadditionalmemor乳、Vhat’sthemostinterestingis也atitincreasesnmningtimeslightly．Inordertoveri母thefeaLsibilityoftheoptimizedinduced。sortingalgorithm，aseriesofexperimentsarecarriedouttoevaluatetheperfb姗ancesofthese