基于并行化诱导排序快速实现Burrows-Wheeler变换算法

为解决生物序列比对算法中主流索引技术Burrows-Wheeler变换(BWT)构建索引效率低的问题,文章提出了一种利用并行化诱导排序改进BWT索引构建的方法。首先,该研究充分发挥诱导排序的线性时间复杂度优势,高效地建立后缀数组。其次,基于此,采用并行化优化算法对后缀类型和子串处理过程进行优化。最后,通过与主流算法在真实生物数据集上的对比实验,结果显示,经过优化的算法在索引构建速度上相较于传统算法取得了明显的提升,从而证明了该方法的有效性。

基于BWT改进的LZW算法在传感器网络中的应用

传感器网络能量有限,网内数据不易直接传输,需要进行压缩。针对有损数据压缩的局限性,基于数据分块和BWT变换思想,提出了一种改进的无损数据压缩算法-B-LZW,保证了数据的完整性。通过信息熵理论分析及实验仿真,比较了B-LZW算法与传统的LZW算法的性能。结果表明,在对实时性要求不高的传感器网络应用中,该算法能更有效地减轻网络节点存储负担,降低数据丢包率,提高压缩率2.75%～3%,节约网络能量,进一步延长网络寿命。

泥沙沉降速度实验研究方法回顾与评述

在总结回顾国内外泥沙沉降速度测量方法的基础上,重点介绍了两种可以应用于土壤侵蚀过程模型的实验方法:G riffith沉降管法和BWT沉降管法,并根据我国水土流失的实际情况,提出了在研究我国侵蚀泥沙沉降规律时需要解决的问题。

一类矢量地图的无损压缩算法

充分考虑平面矢量地图文件的存储特性,对点,线,面类图层文件采用不同的几何压缩算法,有机结合“无附加码书”字典编码方法,可逆并显著地压缩了矢量地图,并得到了更有利于提高后续BWTBlock-Sorting文本压缩算法效果的预处理结果,从而实现了平面矢量地图的有效的无损压缩。采用实际的地图数据,经实验分析表明:本算法具有较高的压缩性能,较好的压缩和解压效率和简单实用性。

基于AVX指令集BWT算法在DNA序列比对中应用

新一代高通量测序技术发展产生大规模DNA序列片段,快速准确地将短序列比对到参考基因组成为生物信息学重要研究课题之一。针对BWT索引技术序列比对算法研究,提出基于Intel微架构AVX指令集优化BWT算法,通过改进计算方式实现算法并优化。结果表明,应用AVX指令集可减少CPU访存次数,降低算法时间复杂度,提高序列比对效率,为基因数据分析提供更高效快速序列比对方法,加快对全基因组序列处理。

基于动力电池海量数据的特性化压缩处理研究

动力电池数据的后台存储和分析无论是对于动力电池故障预警、动力电池回收、溯源管理,还是为动力电池的后续价值评估,都提供了数据支撑。面向海量数据传输存储的发展需求,文章提出针对动力电池数据特性的处理压缩方法。将多种压缩算法进行对比选择;针对动力电池的不同数据类型、不同运行场景进行多方面分析研究,给出相应的处理方法;最终经过对运行数据的处理压缩,实现数据传输、存储成本的有效降低。

一种适合于传感器网络的新型压缩算法研究

数据压缩可以高效节约网络能量,有效延长网络寿命。针对B-LZW算法的缺陷,提出了一种新型的可以直接应用于传感器网络的改进算法—MC-B-LZW;在设计中引入了miniCache,完善了算法的操作性,可使该算法嵌入到现有的各类传感节点中;测试B-LZW及其改进算法MC8,MC16,MC32和MC64的性能;通过比较压缩率和执行时间2个指标,得出结论:MC16算法性能最优,压缩率较B-LZW平均提高13.6%,执行时间较B-LZW几乎没有延长,是一种比较理想的压缩算法。

压缩的全文自索引算法研究

针对传统全文索引技术空间浪费过大等问题,介绍压缩的全文自索引技术。该技术仅利用索引数据即可完成子串搜索,并且可以从索引数据无损地还原出原始的文本信息,是一种无需存储原始文本信息的"自索引"技术,从而大大节省存储空间。综述现有的十几种典型的压缩的全文自索引算法的基本思想及其实现,并在多种数据集上对这些算法进行综合的测试评估。实验结果表明,压缩的全文自索引技术有效地节省了空间开销,实用价值较高。

一种灵活的精度可控的可搜索对称加密方案

中查找到关键词记录的这3种搜索情况.同时,系统也结合3种搜索设计了一种模糊增强搜索进一步增强系统的实用性.FASSE方案的具体实现语言是Java编程开发语言,并且最终实验得出FASSE在https://eprint.iacr.org/complete/的论文数据集中平均搜索完每一篇论文的时间为114.26ms.

BWT与经典压缩算法研究

为提高无损压缩的效果,分析了BWT的基本原理,回顾并比较了霍夫曼编码、算术编码、LZ77和LZW算法的性能,然后把BWT与多阶算术编码、LZW编码结合起来研究,结果表明,对大于BWT分组数据块的文件先经过BWT预处理,再进行压缩,压缩效果明显提高。

基于BWT的文本压缩算法研究

为了理解高效的文本压缩算法,探究文本压缩的原理和意义,对基于BWT的字符串轮转理论进行了深入的理解;游程编码作为一种简单有效的压缩方式,在数据压缩中有十分广泛的应用,文本压缩的研究对于多媒体的压缩研究有着十分重要的意义。把BWT结合游程编码对选定的文本信息进行了压缩比较,实验证明了该算法的高效性和实用性。同时对基于BWT压缩算法的发展趋势进行了展望及分析。

一种基于MPM和BWT算法的XML文档压缩方法

XML文档在网络存储和交换应用中被广泛采用,但是其冗余量大、占用空间和带宽多的缺点也给其应用带来了一定的阻碍。提出了一种将MPM算法(Multilevel Pattern Matching)和BWT(Burrows-Wheeler Transform)算法相结合来压缩XML文档的压缩方法,给出了算法的详细描述。通过实验同其它压缩算法进行了比较,证明该方法是科学和高效的。

采用BWT的多核并行的子串匹配算法

针对P-BWT精确匹配算法存在只支持短串查询并且只能工作在单处理器上的问题,提出了一个多核并行的支持任意查询长度的精确查询算法.改进了P-BWT索引上的查询过程,当一个查询串跨越了多个数据分片时,首先在其匹配的最后一个分片上查询,然后依次在前面分片上进行验证.进一步提出了一个多核并行查询算法来减少搜索和验证过程的迭代次数.实验结果表明,所述算法可以高效并行地完成子串匹配任务.

基于BW转换的压缩算法的分析与研究

本文在Burrows-Wheeler提出的转换的基础上,分析了该转换的一些特点,并加以证明。然后结合了算术编码,并与其它的算法进行了比较。实验表明,该算法要明显优于其它的同类算法。

一种空间高效的多核并行近似子串匹配方法

子串匹配问题是信息检索、信号处理以及生物信息学等领域中的研究重点.随着文本数据的快速增长,在大数据集上高效地完成近似子串匹配是一项挑战.另一方面,多核架构已经成为当今的主流计算机架构,如何在大规模数据中利用多核的优势提高近似子串匹配的效率是本文的研究重点.BWT索引是生物信息学中广泛应用的索引方法,其特点是索引空间小,支持高效压缩和子串匹配.但现有的基于BWT的方法没有考虑多个查询串上的计算共享以及多核资源的动态分配.本文在传统的BWT搜索方法基础上对搜索过程进行了改进,采用过滤和验证的方式完成近似子串匹配.首先,对查询串进行分割重组来减少搜索过程中的重复计算.其次,利用多核优势,动态地按需分配处理器资源从而提高搜索和验证的效率.最后,实验研究展示了本文提出的方法的高效性.

嵌入式系统下电网录波数据的压缩解压算法

随着电网录波数据的应用越来越广泛,电网录波数据的数据量日益增加,这对基于嵌入式平台的电网录波数据保存和传输提出了更高的要求。为了缓解硬件的资源压力,节省新设备投资成本,需要对COMTRADE文件格式的电网录波数据进行无损压缩。针对COMTRADE文件格式的特点,提出了用游程编码压缩数字量通道,以及基于BWT变换预处理的miniLZO压缩算法压缩模拟量通道。试验表明,此算法通道压缩效果良好,能获得理想的压缩率。

基于HLS的BWT算法的硬件加速方法

本文针对BWT算法在序列对比过程中当数据量大时运算耗时长的缺点,研究使用VivadoHLS来实现BWT算法的硬件加速方法。首先按照HLS的代码规范编写C++代码,通过资源消耗和并行化两方面的优化在提高算法效率的同时使得资源消耗最小,然后生成由FPGA实现的BWT算法对应的RTL级硬件电路,最后通过综合和仿真结果评估硬件优化效果。实验结果表明,对5M的DNA参考基因组创建index的耗时从32个clock减少为12个clock,单条reads匹配速率提高为原来的242.8%,同时优化方案打破了PC上匹配时长与reads长度的线性相关关系,使得任意长度的reads都可以在3个clock内完成匹配。

XML文档的有效压缩和查询

针对XML数据的半结构化特征,从XML的文本和结构特征上,结合BWT方法,来消除冗余数据。用实验说明对于压缩后文本查询的高效性。分析了当前结构连接的不足,提出了ESL方法,通过该方法,得到的结构索引比原始数据明显要小的多。提出了处理XML查询的一个模型,并对实现该模型作了初步的探讨。

基于BWT改进的LZSS算法在报文压缩中的应用

电网的智能化使远动信息数据量急剧增大,对硬件设备的存储能力提出了很大的挑战。为缓解硬件设备压力,减少对硬件设备的投资,并且保证解压后能完整还原原始数据,需对报文进行无损压缩。针对IEC60870-5-104报文规约结构,提出基于BWT改进的LZSS算法,使用BWT变换对字符串进行预处理,再将数据由LZSS算法进行压缩。实验仿真结果表明,该改进算法压缩效率相对于传统LZSS算法更好,平均压缩比减少15.58%,平均耗时减少6.949 s,能够有效减少电力报文数据的存储空间。

一种基于LFU置换的BWT压缩算法的改进

BWT算法是目前广泛关注的一种基于块压缩的无损压缩算法。由BWT变换,MTF变换和熵编码三部分组成。本文对其做了具体介绍和分析并在此基础上提出了一种基于LFU缓冲区置换策略的MTF变换的改进方法,实验结果表明改进后的算法使压缩比有所提高。