快速轻量级后缀数组

《快速轻量级后缀数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、摘要摘要近几年来随着大数据的热门，后缀树和后缀数组在字符串和序列的通用索引方面得到了很多的应用。尤其是对于后缀数组这种数据结构，因其简单性和高效的空间利用率促使各个学者和程序员争先使用。[[]J.L.BentleyandM.D.McIlroy.Engineeringasortfunction[R].Software–PracticeandExperience,23(11):1249–1265,1993.701]通常构造索引的方法有：1.全文索引；2.关键字索引。后缀数组作为一种大文本索引结构，因为它简单的结构和非常好的空间效率，已经成为全文索引构建算法的基本数据结

2、构。但是它也有一个明显的缺陷：如果构建后缀数组算法使用不当，将会导致非常大的空间消耗。现在我们根据前人研究的基础，提出一种快速轻量级后缀数组的构建方法，使后缀数组在运行时间和空间消耗上都得到一个很好的情况。本文提出一种“快速轻量级”构建后缀数组的算法，这就是Manizi-Ferragina提出来的后缀数组构造算法，以下简称MF算法。[]张喜娟.基于后缀数组的近似字符串匹配[D]．西安电子科技大学出版.2012MF算法在Seward算法基础上，在排列2-前缀后缀顺序的时候使用一个更为复杂的排序技术：首先定义一个整数L：通过标准的方法排列后缀数组的最长lcp。当2-前

3、缀后缀的顺序排好后，用[]D.Gusfield.AlgorithmsonStrings,Trees,andSequences:ComputerScienceandComputationalBiology[D].CambridgeUniversityPress,1997.698Bently-Sedgewick多元快速排序算法递归排序直到深度L，如果还未完全排序，此时lcp(i1,i2,...,im)>L，当mn/Q时，我们使用一种新的排列方式进行排序。在接下来的论文里我们将会详细介绍这种快

4、速轻量级构造后缀数组的算法。关键词：后缀数组倍增算法诱导算法递归算法快速轻量级摘要ABSTRACTWearenotstrangertosuffixarrayandsuffixtreethatbigdatainrecentyearsasapopularsuffixarraysandsuffixtreesinthegeneralindexofthestringandthesequencehasbeengreatlyattention.Especiallyforsuchasuffixarraydatastructure,duetoitssimplicityandeffi

5、ciencyofspaceutilizationpromptedvariousscholarsandprogrammerspriority.Typicallyconstructedindexmethodsare:1full-textindex;2keywordindex..Suffixarrayasalargetextindexingstructure,becauseitissimplestructureandaverygoodspaceefficiency,hasbecomeafull-textindexingalgorithmtobuildabasicdata

6、structure.Butitalsohasanobviousflaw:Ifyoubuildsuffixarrayalgorithmimproperusewillresultinaverylargespaceconsumption.Nowweareinaccordancewiththebasisofpreviousstudies,afastlightweightconstructionmethodproposedsuffixarray,sothesuffixarrayonrunningtimeandspaceconsumptionhavebeenagoodsitu

7、ation.Thispaperproposesa"fastlightweight"buildsuffixarrayalgorithm,whichisManizi-Ferraginaproposedbythesuffixarrayconstructionalgorithm,hereinafterreferredtoasMFalgorithm.MFalgorithmbasedonthealgorithminSeward,Inthearrangement-prefixesandsuffixeswhenusingamorecomplexsequenceofsortingt

8、echni