导读:本文包含了自索引论文开题报告文献综述及选题提纲参考文献，主要关键词:DNA数据压缩,基于参考基因组,自索引,垂直压缩
自索引论文文献综述
荣河江[1]（2018）在《基于自索引结构的高通量基因组重测序数据压缩算法》一文中研究指出测序技术的进步,使得人们对基因组测序的兴趣日益增加。早期测序技术需要几年的时间来捕获30亿个核苷酸的基因组,目前新一代测序技术在数天内就可以对220亿个核苷酸的基因组进行测序。在测序速度提升的同时,测序成本也直线下降。基因组测序在个性化医疗和公共健康中日益发挥着重要的作用。越来越多的基因组测序数据在不断产生,这些数据需要进行有效的存储、传输和分析。如何解决高速增长的数据与有限的存储空间的矛盾,成为重要的研究课题。DNA数据压缩为解决问题提供了一种有效思路。但由于DNA数据自身的特点,传统的压缩方法难以达到很好的压缩效果。本文针对上述问题,在前两章调研了现有的高通量数据压缩技术,并对相关的压缩算法原理和以及面临的挑战进行分析,最后提出了改进的高通量数据压缩算法。本论文做了如下几件工作:(1)调研了高通量测序数据集的存储格式,以及现有的压缩算法。分析了测序数据的生物特性,同时通过分析表明,对质量分数的有损压缩,在提高压缩性能的同时,在下游分析中还能保持较好(有时甚至更优)的性能。(2)在基于参考基因组进行差异化压缩编码的方案基础上,采用垂直方向的编码方式,同时对质量数采用稀疏化处理和均值处理相结合的方式,获得较好的有损压缩性能,实验表明压缩效果更优。(3)针对数据需要随机解压缩和快速检索的需求,在分析自索引压缩技术原理的基础上,提出基于PBWT数据结构的自索引压缩技术,实验表明,自索引技术的引入,在随机解压缩上有较好的性能。本文在基于参考基因组的压缩算法基础上,提出了基于自索引结构的随机解压缩算法,在压缩效率上有一定的优势,同时可以满足局部检索和解压缩的需求。这在一定程度上可以缓解海量高通量数据的存储和传输压力,为后续相关研究提供经验和借鉴。(本文来源于《哈尔滨工业大学》期刊2018-06-01）
郭文钰[2]（2018）在《全文自索引压缩算法的研究》一文中研究指出随着互联网技术的不断发展,网络信息爆炸式地增长,繁杂的文本数据带给人们便利的同时,也给文本检索带来巨大的挑战。倒排索引技术虽然能解决部分需求,但当分词不准确或者无法进行分词时,就会导致检索的精准度出现问题。全文自索引算法不是以“词”的粒度来分割文本,而是以文本的单个符号进行分割,可以解决精准匹配的问题。全文自索引所占有的空间是原文本所占空间的4～20倍,造成非常大的空间浪费,所以全文自索引压缩算法对全文检索有着重要的意义。本文研究了后缀数组、rank/select/access操作、BWT数据轮转算法、小波树和整数编码压缩算法,在此基础上设计高效的全文自索引压缩算法,主要工作如下:(1)本文在Sad-CSA算法的基础上,利用其上下文划分的理念,保存一层上下文结构,提出了 PEF-CSA自索引压缩算法。该算法利用Partitioned-Elias-Fano编码压缩算法对后缀数组转化而成的间断单调递增的近邻数组φ进行压缩,并采用二级压缩结构得到良好的压缩效果和查询性能。(2)本文在原始FM-Index算法基础上提出了 Adaptive-FM-Index自索引压缩算法。将原文本T经过BWT数据轮转得到T~(bwt）,利用Huffman小波树结构存储T~(bwt),得到HWT(T~(bwt)),将HWT(T~(bwt))每个节点存储的bit串划分得到超块与块的两级结构,提升了查询的速度,并且根据块的数据分布特点,选取自适应的编码方式,提升了压缩性能,结合采样后缀数组与采样名次数组的辅助结构提供高效的自索引结构。(3)本文实现了 PEF-CSA自索引压缩算法和Sad-CSA压缩算法、RL-CSA压缩算法、SDSL-CSA算法。实验表明,PEF-CSA自索引压缩算法的压缩率和计数查询性能是CSA算法中最优的,定位查询性能也高于大多数CSA算法。实现了Adaptive-FM-Index 自索引压缩算法,并且实现了 FM-RRR 算法、FM-uncompressed算法、FM-hybrid算法、RLFM算法。实验表明,Adaptive-FM-Index自索引压缩算法的压缩率,计数查询性能与定位查询性能都普遍好于其他FM-Index算法,并且在字符频率失衡的数据集上压缩效果更好。Adaptive-FM-Index自索引压缩算法压缩率优于PEF-CSA自索引压缩算法,但在english类的平衡数据集上,PEF-CSA自索引压缩算法的压缩率更低,PEF-CSA自索引压缩算法的定位查询性能优于Adaptive-FM-Index自索引压缩算法。(本文来源于《北京交通大学》期刊2018-03-01）
刘亦韬[3]（2015）在《基于压缩全文自索引的分布式索引技术研究》一文中研究指出分布式全文检索技术是信息处理领域的核心技术之一，目前被广泛应用于竞争情报、信息检索、搜索引擎以及信息过滤等领域。对高效分布式全文索引技术的深入探讨不仅拥有重要的理论价值，同时还具有巨大的商业价值。随着互联网的日益普及，各式各样的数据以更快的速度产生，数据总量成指数级增长，面对海量的数据，相关数据索引文件的大小也持续增加。传统的单机索引系统基本不能满足海量数据的索引需求，而分布式索引系统可满足上述需求，并实现海量数据的分布式索引。分布式索引系统的核心技术涵盖了分布式索引创建、索引查询、分布式索引的数据分配以及分布式索引的负载均衡等内容。本文将近几年来流行的文本处理技术——压缩全文自索引应用到分布式索引当中，并讨论该索引结构下的查询策略。本文对分布式全文索引技术研究的内容包括：（1）当前主流的分布式索引系统主要采用倒排索引结构，运行在高性能集群中的倒排索引对查询的响应时间可达到毫秒级别。然而，倒排索引除了需存储自身信息之外的信息，还需要额外存储信息用于支持搜索引擎实现存储片段抽取、排序和位置信息、查询缓存等功能，从而导致存储空间的利用效率偏低。本文创新的将当前文本索引研究的热点压缩全文自索引应用到分布式索引系统当中，提出一种基于改进哈夫曼编码的小波树压缩算法，并与后缀数组将结合，实现了能适应分布式环境下的压缩全文自索引结构及对应的高效创建算法。（2）索引系统在搜索引擎中主要发挥以下两种作用：第一，根据一定的规则创建网页文档的索引，便于后续查询；第二，按照用户提出的查询命令检索索引文件，同时按一定规则对索引文件进行排序并将结果返回客户端。基于新改进的压缩全文自索引结构，提出了一种分布式环境下的查询处理策略。（3）结合以上研究内容和相关研究成果，提出一种分布式全文索引系统架构，该系统有利于实现各种各样非结构化数据的分布式索引，进而实现海量非结构化数据的查询和索引性能。详细介绍了系统中索引集群、查询集群以及分布式文件系统的设计，最后测试该分布式索引系统查询处理的高效性。(本文来源于《杭州电子科技大学》期刊2015-03-01）
陈龙刚[4]（2014）在《压缩全文自索引算法的研究》一文中研究指出在信息检索领域,基于数据库的条目型检索系统和基于倒排表的检索系统能解决一部分需求,但在字符串精确匹配、生物序列分析、任意模式检索等领域,无法通过数据库系统和倒排表完成。全文索引技术(full-text index)可以在一定程度上解决这类问题,但是形如后缀数组(suffix array,SA)和后缀树(suffix trie,ST)这样的全文索引结构需要很大的空间,实用性不强。压缩索引(compressed full-text self-index)技术解决了上述问题,它对原始数据进行压缩表示,所需空间与纯压缩算法相当,而且能够在不需要恢复出原始数据的情况下提供高效的模式匹配功能。本文研究了常见后缀数组构建算法、压缩后缀数组、Bit Map、FM-index、熵与编码等方面的知识。在此基础上,设计和实现了高效的压缩索引方案,包含以下叁部分。首先,针对常见后缀数组计算方法内存峰值过大、计算速度慢的问题,提出了高效的SA计算方法DCV,具有省内存、速度快的优点,运行时内存峰值为原始数据的5倍左右,运行时间与知名的LS方法相当,总体性能优越。其次,我们针对压缩后缀数组(compressed suffix array,CSA)设计了两种高效、简洁的结构:CSA和Adaptive-CSA,分别对?数组的差分序列使用gamma编码和自适应的混合编码,理论结果保持了该领域已有理论结果的性能,可以在O(m log n)的时间内完成count查询,m表示模式长度,可以将原始数据压缩到2nHk(T)+n+o(n)比特,Hk(T)表示原文T的k阶经验熵,结合自适应策越、调优的编码方法、查找表等优化手法,使我们的CSA结构在构建时间、压缩率、查询速度上优于常见CSA结构,在Canterbury Corpus和Pizza&Chili Corpus上的各项测试结果优势明显。最后,提出了一种高效的Bit Map索引结构,对每块数据能自动的选择最佳编码方法,并能根据数据的分布选择最合适的块大小等参数,并以此为基础,结合小波树实现了第二种压缩索引方案Adaptive-FM,充分利用数据分布特点,具有数据感知的能力,理论结果保持了该领域已有理论结果的性能,count查询可以在O(m log?)时间内完成,?表示字符表大小,所需空间为2nHk(T)+o(n)log?比特,Canterbury Corpus和Pizza&Chili Corpus数据集上的测试表明Adaptive-FM综合性能优越,特别是压缩率。所开发的压缩索引已工程化,可在https://github.com/chenlonggang/上获取。(本文来源于《西安电子科技大学》期刊2014-11-01）
路炜,刘燕兵,王春露,刘庆云,郭莉[5]（2014）在《压缩的全文自索引算法研究》一文中研究指出针对传统全文索引技术空间浪费过大等问题,介绍压缩的全文自索引技术。该技术仅利用索引数据即可完成子串搜索,并且可以从索引数据无损地还原出原始的文本信息,是一种无需存储原始文本信息的"自索引"技术,从而大大节省存储空间。综述现有的十几种典型的压缩的全文自索引算法的基本思想及其实现,并在多种数据集上对这些算法进行综合的测试评估。实验结果表明,压缩的全文自索引技术有效地节省了空间开销,实用价值较高。(本文来源于《计算机应用与软件》期刊2014年03期）
刘小珠,彭智勇,陈旭[6]（2010）在《高效的随机访问分块倒排文件自索引技术》一文中研究指出针对倒排索引空间开销大、查询时间效率低以及难以同时支持连接布尔查询和排序查询的问题,提出了一种同时提高空间效率与查询时间效率的高效随机访问分块倒排文件自索引RABIF.为了在降低空间消耗的同时支持连接布尔查询与排序查询,RABIF将倒排列表进行合理地分块,然后对每个子块的不同部分采用相应的压缩方式,在不需要插入任何附加辅助信息的前提下实现压缩索引的快速定位与随机访问.理论分析及实验结果表明,与忽略倒排文件自索引SIF相比,提出的RABIF空间开销平均减少5.3%,布尔查询时间平均减少17.8%;对于0.2%与1%排序查询,查询时间分别平均减少34.4%与27.5%.(本文来源于《计算机学报》期刊2010年06期）
傅厚荃[7]（2009）在《xml文件压缩存储和自索引研究》一文中研究指出XML目前已经成为Internet上的“国际语言”,所以,如何使数据库管理系统对XML文件进行良好的支持就成为了当前的研究热点。本文讨论的内容,就是在纯XML数据库管理系统下,对XML文件进行压缩存储以及对压缩后的文件实现自索引。由于XML文件需要对数据的结构进行描述,具体的方式就是加入标签,这使得XML文件所占的存储空间变大。而对应的解决办法,就是对文件进行压缩。传统的压缩方法不能保持XML文件的结构,所以当进行查询的时候,需要将文件先进行解压缩,或者先要对查询关键字进行同样的压缩处理,才能够进行查询。本文针对XML数据冗余大的问题,同样对文件进行了压缩处理。但是,本文采取保持XML文件结构,只对其中文本结点中的文字内容部分进行压缩。这样在节点级别进行查询操作时可以不进行解压,当查询定位到某个节点以后,才需要把相应的内容进行解压缩操作,这样就提高了效率。对于本文提出的存储方法,给出了对应的查询方式,其特点就是在锁定要查询内容所在的节点位置的前提下,再对节点内容进行解压缩,同时,在解压缩的过程中,创建出文本的后缀数组作为节点内容文本的全文索引,然后使用索引进行进一步的查询,其查询效率就大大提高了。因为系统并不需要单独存放文本内容的索引文件,而是在解压缩的过程中生成索引,这也就使被压缩的文件具有了自索引的特点。(本文来源于《天津师范大学》期刊2009-03-01）
刘胜飞,张云泉,张迪[8]（2009）在《基于自索引的DBF压缩查询工具研究》一文中研究指出介绍了DBF表的文件格式和基于自索引的全文查询算法FM-index。针对DBF文件同时包含二进制文件头和纯文本数据记录的特点,以及对查询结果的特定要求,扩充了现有的FM-index算法,使其支持对DBF文件的压缩查询。测试结果表明,虽然FM-index在压缩/解压时间上与WinRAR仍有一段差距,但是FM-index对压缩查询功能的支持大大提高了文件的查询性能。(本文来源于《计算机应用研究》期刊2009年02期）
帅训波,周相广,黄复贤[9]（2008）在《一种改进的自索引排序算法设计与分析》一文中研究指出在自索引排序算法研究基础上,从对待排的数据进行优化处理角度,提出了一种新型自索引排序算法,给出了算法思想、算法描述和算法分析,其理论意义在于将自索引排序算法的空间复杂度o(n+m)(其中m为待排的数据序列最大值)改进为o(Δm)(其中Δm为关键字变化范围),对比实验结果分析表明,改进后的算法有更好的排序效果.(本文来源于《德州学院学报》期刊2008年02期）
自索引论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
随着互联网技术的不断发展,网络信息爆炸式地增长,繁杂的文本数据带给人们便利的同时,也给文本检索带来巨大的挑战。倒排索引技术虽然能解决部分需求,但当分词不准确或者无法进行分词时,就会导致检索的精准度出现问题。全文自索引算法不是以“词”的粒度来分割文本,而是以文本的单个符号进行分割,可以解决精准匹配的问题。全文自索引所占有的空间是原文本所占空间的4～20倍,造成非常大的空间浪费,所以全文自索引压缩算法对全文检索有着重要的意义。本文研究了后缀数组、rank/select/access操作、BWT数据轮转算法、小波树和整数编码压缩算法,在此基础上设计高效的全文自索引压缩算法,主要工作如下:(1)本文在Sad-CSA算法的基础上,利用其上下文划分的理念,保存一层上下文结构,提出了 PEF-CSA自索引压缩算法。该算法利用Partitioned-Elias-Fano编码压缩算法对后缀数组转化而成的间断单调递增的近邻数组φ进行压缩,并采用二级压缩结构得到良好的压缩效果和查询性能。(2)本文在原始FM-Index算法基础上提出了 Adaptive-FM-Index自索引压缩算法。将原文本T经过BWT数据轮转得到T~(bwt）,利用Huffman小波树结构存储T~(bwt),得到HWT(T~(bwt)),将HWT(T~(bwt))每个节点存储的bit串划分得到超块与块的两级结构,提升了查询的速度,并且根据块的数据分布特点,选取自适应的编码方式,提升了压缩性能,结合采样后缀数组与采样名次数组的辅助结构提供高效的自索引结构。(3)本文实现了 PEF-CSA自索引压缩算法和Sad-CSA压缩算法、RL-CSA压缩算法、SDSL-CSA算法。实验表明,PEF-CSA自索引压缩算法的压缩率和计数查询性能是CSA算法中最优的,定位查询性能也高于大多数CSA算法。实现了Adaptive-FM-Index 自索引压缩算法,并且实现了 FM-RRR 算法、FM-uncompressed算法、FM-hybrid算法、RLFM算法。实验表明,Adaptive-FM-Index自索引压缩算法的压缩率,计数查询性能与定位查询性能都普遍好于其他FM-Index算法,并且在字符频率失衡的数据集上压缩效果更好。Adaptive-FM-Index自索引压缩算法压缩率优于PEF-CSA自索引压缩算法,但在english类的平衡数据集上,PEF-CSA自索引压缩算法的压缩率更低,PEF-CSA自索引压缩算法的定位查询性能优于Adaptive-FM-Index自索引压缩算法。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
自索引论文参考文献
[1].荣河江.基于自索引结构的高通量基因组重测序数据压缩算法[D].哈尔滨工业大学.2018
[2].郭文钰.全文自索引压缩算法的研究[D].北京交通大学.2018
[3].刘亦韬.基于压缩全文自索引的分布式索引技术研究[D].杭州电子科技大学.2015
[4].陈龙刚.压缩全文自索引算法的研究[D].西安电子科技大学.2014
[5].路炜,刘燕兵,王春露,刘庆云,郭莉.压缩的全文自索引算法研究[J].计算机应用与软件.2014
[6].刘小珠,彭智勇,陈旭.高效的随机访问分块倒排文件自索引技术[J].计算机学报.2010
[7].傅厚荃.xml文件压缩存储和自索引研究[D].天津师范大学.2009
[8].刘胜飞,张云泉,张迪.基于自索引的DBF压缩查询工具研究[J].计算机应用研究.2009
[9].帅训波,周相广,黄复贤.一种改进的自索引排序算法设计与分析[J].德州学院学报.2008