导读:本文包含了后缀数组算法论文开题报告文献综述及选题提纲参考文献，主要关键词:乐纹,压缩后缀数组,索引压缩,游程编码
后缀数组算法论文文献综述
刘学政,史有群,罗辛,陶然[1]（2015）在《一个基于压缩后缀数组的乐纹索引算法》一文中研究指出在基于乐纹的音乐检索系统中,提取的乐纹的多少决定了检索结果的匹配度,这就造成了数据库大小与检索匹配度不能兼顾的矛盾。提出使用压缩后缀数组来压缩乐纹索引的方法,解决全文索引时索引空间过大的问题。主要利用有序乐纹数据中较高位特征出现重复的概率大的特点,使用游程编码对乐纹序列进行无损压缩。实验结果表明,该方法在包含2000首歌曲的数据库中仅需要使用原来80%的乐纹数据空间,在包含12000首歌曲的数据库中只需要使用原来30%的乐纹数据空间。与传统的后缀数组索引方法相比,该方法需要的索引存储空间仅为原来的60%。(本文来源于《计算机科学》期刊2015年S1期）
焦雅[2]（2015）在《基于后缀树与后缀数组混合结构的基因序列比对算法研究》一文中研究指出随着基因测序技术的迅猛发展,基因数据库中序列公共数据量呈指数形式增长。对于基因数据最基础但最重要的分析方法为序列比对。本文通过对现今常用的分析算法和分析软件在序列的类型、特点和功能等方面研究和比较,发现序列比对算法的重点是对基因数据结构进行有效组织。目前这些数据结构有哈希表和后缀树、后缀数组,本文在此研究基础上提出了新的算法BWL。BWL算法的特点：(1)采用了新的数据结构,即后缀树与后缀数组混合的新的数据结构,这种数据结构不仅占用内存空间比较小,解决了基因数据文件因内存受限的问题,而且能减少与外存频繁交互,提高比对运算速度。(2)BWL算法在序列比对过程中引进空位种子模型,提高算法敏感度。对于没有完全匹配的序列,采用加入空位的方法,相对于精确的动态规划法或对模型逐位循环进行增、删、改再比对的试探方法在运算速度方面有了进一步提升,算法有效性明显提高。最后本文做了序列比对仿真实验,并对实验结果进行了详细的分析分析结果表明,本文提出的后缀树与后缀数组混合的数据结构占用内存不会随着基因数据的大小而改变,索引构建速度也较其他算法更快。另外,序列比对上提出的引入空位种子模型的方法在实验比较中得出本文提出的改进具有有效性并且实际性能的提升很显着。(本文来源于《内蒙古农业大学》期刊2015-06-01）
胥永康,杨光露,路松峰[3]（2015）在《基于压缩后缀数组的近似字符串匹配算法》一文中研究指出近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。(本文来源于《计算机工程与应用》期刊2015年23期）
李双江[4]（2014）在《基于压缩后缀数组的空间高效短读比对算法》一文中研究指出新一代基因测序技术(NGS)的出现使得测序成本飞速下降,随之而来的是大量的短读序列需要更快速准确的比对程序来处理。第一代基于散列表技术的序列比对算法如Bowtie等能够快速准确的完成比对工作,但其不支持gap比对的特性使得在短读序列(short reads)过长导致indel出现频繁时,比对的精度也随之下降。另一方面,近年来压缩索引(BWT,CSA,FM-index)领域的相关研究使得在较小内存中索引人类基因组这样的大规模序列成为可能。这导致近年来出现了很多基于压缩索引的短读比对算法,如BWA,Bowtie等。本文提出了一种基于压缩后缀数组和后向搜索实现近似匹配的算法来实现短读比对,在比对时间和空间以及比对精度上都取得了很好的效果。基于压缩后缀数组的短读比对算法(CSAA),采用了压缩后缀数组来构建参考序列的索引,并使用后向搜索来做匹配。通过引入搜索树,CSAA实现了近似匹配算法,从而支持完全的gap比对。此外CSAA在搜索树上使用了一种类似堆的优先堆数据结构,大大减小了搜索空间。而且每一次的搜索方向都能保证是最优的。最后结合罚分机制以及difference距离,定义seed等方法,进一步降低搜索空间,提高了CSAA的比对速度和精度。CSAA的高效体现在叁个方面。一是空间高效的索引方法;二是基于后向搜索的高效的近似匹配方法;叁是seed策略和多线程比对技术的利用。本文采用了增量法进行压缩后缀数组索引的构建,从而跳过后缀数组的构建,降低了对内存的需求。而在比对时,seed的引入使得在比对短读的前几十个核苷酸就可以放弃大部分无效的搜索方向。多个短读比对的相互独立使得并行化成为可能,使得CSAA使用多线程时可以获得数倍的加速优势,从而可以根据计算机的cpu核数指定多个线程,以取得最优的比对速度。CSAA支持单端和双端序列比对,以Fastq格式输入,输出为标准的SAM(Sequence Alignment Map)格式。(本文来源于《西安电子科技大学》期刊2014-11-01）
陈月妥[5]（2014）在《一种新型后缀数组构造外存算法的性能优化技术》一文中研究指出后缀数组是指一个字符串的所有后缀按字典顺序升序（或降序）排列的数组。当前，在基因组分析、文本压缩、字符检索等应用领域，后缀数组都表现出了极大的潜力。然而，许多后缀数组构造算法是完全在内存中运行的。但在实际应用中，经常要为很长的一串字符串构造后缀数组，那么完全在内存中完成构造过程就是不可能的了。而依靠操作系统调用虚拟内存来存放运行过程中的数据，会产生大量的内、外存之间的随机I/O，这种情况所造成的时间效率恶化是不可接受的。针对该问题，我们需要一个高效的外存版本的后缀数组构造算法，它在很大程度上不会受到内存大小限制而可以为较大文本构造后缀数组。本文首先分析了几个比较有代表性的后缀数组构造内存算法，并重点分析了IS算法。该算法融合了分治与递归和归纳排序两种思想，有很高的时间效率，而它的空间效率更是遥遥领先于其它算法。但是因为它需要随机读取数组的操作，所以当内存无法完整存放运行过程中产生的数组时，该算法就不适用了。本文在该算法的基础上，进行一些合适的改造，主要包括以下几方面：1）把字符串中连续相同的一串字符用一个结构体来表示，以便减少所需的存储空间；2）对字符串生成的每个结构体附加前继字符信息并分桶存放且桶内按索引顺序排列，再把此结果用于和在归纳排序时对后缀根据索引顺序排列后的结果对应上，从而顺序获取前继信息，规避随机读取操作；3）在归纳排序的过程中，只求后缀数组的一部分来缩短构造时间；4）在归纳排序的过程中，同时进行命名后缀的操作，这样能够利用已经得到的比较结果，从而避免归纳排序后单独对后缀命名所导致的重复比较操作。本文通过这些修改，让IS算法能够结合内、外存以较高的效率进行后缀数组的构造，并把改进后的算法称为DIS算法。(本文来源于《中山大学》期刊2014-05-01）
李卓衡[6]（2014）在《一种外存后缀数组构造算法的工程实现及性能评估》一文中研究指出后缀数组最初是作为后缀树的一种替代被提出的，与后缀树相比，存储后缀数组所需的空间更少，应用范围更广。在后缀数组被提出后，后缀数组作为一种重要的索引数据结构，被广泛的应用于生物信息学、全文索引、字符串匹配、频繁字符串挖掘以及顺序分析和聚类分析等领域。到目前为止，国内外关于后缀数组构造算法的研究已经取得了丰硕的成果。但随着信息技术的发展，在许多领域，需要处理的数据集日益增长。当利用原有后缀数组内存构造算法为一个非常大的数据集构建后缀数组时，所需的内存空间远远超出了一般商用电脑的内存限制。这时，后缀数组内存构造算法不再适用，极大的限制了后缀数组的应用范围。在本文中，我们探讨了一种基于SA-IS算法的后缀数组外存构造算法，对算法的主要思想进行了深入分析，从理论上验证了算法的正确性和可行性。在深入理解算法的基础上，我们采用面向过程的程序设计方法对算法加以实现。在具体实现过程中，我们对原算法中的PCI和name两种中间辅助数据结构进行精简，通过采用分块的策略将原算法中所需的外存排序过程转化为多次的内存基数排序过程，保证了算法的执行效率和I/O性能。同时，通过实验对比分析，对算法的性能进行评估，最终的实验结果显示，该算法是线性的并且具有与EM-SA-DS算法相近的性能。(本文来源于《中山大学》期刊2014-05-01）
李龙[7]（2014）在《基于小波树的后缀数组压缩算法》一文中研究指出后缀数组是一种简单的、功能强大的数据结构，在全文索引设计、数据压缩算法、生物信息学等领域中都有着广泛的应用。但是，后缀数组需要庞大的空间进行存储，因此研究后缀数组的压缩算法有着重大的意义。本文提出基于小波树的后缀数组压缩算法，对后缀数组的占有空间进行了有效的压缩。在研究压缩后缀数组(CSA)的基础上，分析CSA的建立过程，对CSA进行了局部优化。结合后缀数组上的后向搜索算法以及CSA数据结构特点，探究后缀数组的压缩算法应具备的特性，据此特性提出问题转化，并验证了利用小波树压缩后缀数组的可行性。详细设计了基于小波树的后缀数组压缩算法，降低了后缀数组所需的存储空间。在两种不同树形的小波树编码方式上，分析算法能获得的压缩比。进一步提出利用二进制压缩编码对小波树进行压缩，使算法达到更高的压缩比。经过理论及实验分析得出，采用Huffman形的小波树对后缀数组进行压缩编码，进一步采用Run-Length编码对小波树进压缩，能够在合理的时间内完成后缀数组的压缩编码过程，并取得较好的压缩比。(本文来源于《西安电子科技大学》期刊2014-01-01）
王坚[8]（2012）在《基于后缀数组的滑动窗口匹配压缩改进算法研究》一文中研究指出LZ77算法，又被称为“滑动窗口压缩”，它依赖两个滑动窗口来进行压缩，一个窗口包含已输入数据流，称为字典窗口DW(dictionary window)；另一个窗口包含待压缩编码的字符串，即待编码窗口CW(code window)。LZ77通过查找在DW中与CW相同的字符数据并将匹配成功的数据编码成叁元组写入压缩文件，从而实现数据压缩功能。后缀数组(Suffix Array，简称SA)作为一种常用的文本索引机制，由于其结构简单及空间效率较好的特点，现已经结合到LZ算法中。但这种结合方法，每次都需重建SA，时间复杂度较高，效率不高。首先分析字符串匹配等算法并进行对比，在对已提出各种LZ77改进算法的研究分析的基础上，进一步对后缀数组与最长公共前缀((Longest Common Prefix,简称LCP)等相关理论进行研究分析，阐述叁种后缀数组的构建算法并对比。然后分析现有结合算法的思想及其不足，通过对SA的特点分析，提出完全后缀这一新术语，利用LCP数组把SA分为完全后缀(Complete Suffix Array，简称CSA)和非完全后缀(Uncompleted SuffixArray，简称UCSA)，由于窗口滑动后UCSA保持了原有的偏序关系，且占SA比例高，采用二分插入法把CSA插入到UCSA中构建新的SA，可以更高效地重建SA。从而在保证压缩效率不降低的同时，提高整个算法的压缩效率。最后通过实验，对多种不同大小的文件进行测试，对比现有结合算法和改进算法的效率，表明改进算法的实践优越性。同时实验中的最长公共字符串平均长度和完全后缀数组的平均大小，也表明了改进算法的优越性。(本文来源于《华中科技大学》期刊2012-01-01）
赵友桥,王坚,路松峰,胥永康[9]（2012）在《一种后缀数组与滑动窗口结合的压缩算法》一文中研究指出现有的基于后缀数组的滑动窗口压缩算法,在每次窗口滑动后都需要重新构建后缀数组,影响了算法的效率。在分析了滑动窗口下后缀数组的特点后,提出一种构建后缀数组的新方法,使得在压缩算法执行过程中只需要部分构建后缀数组,在不损失压缩效率的情况下,使得整个压缩算法的效率得到提高。实验验证了提出算法的有效性。(本文来源于《计算机工程与应用》期刊2012年15期）
孙伟东,马宗民[10]（2011）在《一种适合于GPU计算的并行后缀数组构造算法》一文中研究指出后缀数组广泛应用于序列分析、字符串匹配和文本压缩,近年来,有关后缀数组构造和应用算法的不断探索构成了计算机科学中一个非常活跃的研究领域.在对现有串行算法进行了分析和对比之后,提出了一种新的、简洁的适合于GPU计算的并行后缀数组倍增构造算法,以排序方法替代传统的分组策略,不但能独立完成后缀数组的并行构造,还可与现存的串行倍增算法结合使用,以达到最高的执行效率.实验结果表明该算法在解决实际应用问题时,具有易于实现、执行速度快和可扩展性强等优点,尤其在处理小字符集的数据时效率更高.(本文来源于《小型微型计算机系统》期刊2011年05期）
后缀数组算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
随着基因测序技术的迅猛发展,基因数据库中序列公共数据量呈指数形式增长。对于基因数据最基础但最重要的分析方法为序列比对。本文通过对现今常用的分析算法和分析软件在序列的类型、特点和功能等方面研究和比较,发现序列比对算法的重点是对基因数据结构进行有效组织。目前这些数据结构有哈希表和后缀树、后缀数组,本文在此研究基础上提出了新的算法BWL。BWL算法的特点：(1)采用了新的数据结构,即后缀树与后缀数组混合的新的数据结构,这种数据结构不仅占用内存空间比较小,解决了基因数据文件因内存受限的问题,而且能减少与外存频繁交互,提高比对运算速度。(2)BWL算法在序列比对过程中引进空位种子模型,提高算法敏感度。对于没有完全匹配的序列,采用加入空位的方法,相对于精确的动态规划法或对模型逐位循环进行增、删、改再比对的试探方法在运算速度方面有了进一步提升,算法有效性明显提高。最后本文做了序列比对仿真实验,并对实验结果进行了详细的分析分析结果表明,本文提出的后缀树与后缀数组混合的数据结构占用内存不会随着基因数据的大小而改变,索引构建速度也较其他算法更快。另外,序列比对上提出的引入空位种子模型的方法在实验比较中得出本文提出的改进具有有效性并且实际性能的提升很显着。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
后缀数组算法论文参考文献
[1].刘学政,史有群,罗辛,陶然.一个基于压缩后缀数组的乐纹索引算法[J].计算机科学.2015
[2].焦雅.基于后缀树与后缀数组混合结构的基因序列比对算法研究[D].内蒙古农业大学.2015
[3].胥永康,杨光露,路松峰.基于压缩后缀数组的近似字符串匹配算法[J].计算机工程与应用.2015
[4].李双江.基于压缩后缀数组的空间高效短读比对算法[D].西安电子科技大学.2014
[5].陈月妥.一种新型后缀数组构造外存算法的性能优化技术[D].中山大学.2014
[6].李卓衡.一种外存后缀数组构造算法的工程实现及性能评估[D].中山大学.2014
[7].李龙.基于小波树的后缀数组压缩算法[D].西安电子科技大学.2014
[8].王坚.基于后缀数组的滑动窗口匹配压缩改进算法研究[D].华中科技大学.2012
[9].赵友桥,王坚,路松峰,胥永康.一种后缀数组与滑动窗口结合的压缩算法[J].计算机工程与应用.2012
[10].孙伟东,马宗民.一种适合于GPU计算的并行后缀数组构造算法[J].小型微型计算机系统.2011