FM-index压缩查询算法解析

FM-index 是目前信息检索领域中国际上比较领先的压缩查询方法。该算法是压缩技术和索引技术的结合,它的最大优势在于能够支持在不解开压缩文件的情况下对源文件进行查询。本文对 FM-Index 如何实现压缩,如何建立索引以及如何实现压缩状态下的查询和定位算法进行了详细的解析,并对该算法的核心部分用图示加以说明,为 FM-Index 算法的相关研究及在实际中能良好的应用和改进提供了参考。

可查询XML数据压缩技术概述

随着互联网技术的迅速发展,XML已经成为Web上信息表示和数据交换的事实标准。XML数据的冗余性影响了XML数据传输、查询处理等方面的效率,数据压缩是解决冗余的一种途径。介绍了典型的可查询XML压缩技术,阐述了各种压缩技术的优缺点,比较了各压缩技术的压缩率、压缩时间、支持查询的类型等;最后总结了可查询XML压缩技术的不足之处及其发展的趋势。

配电网监测数据的分布式Map压缩-查询技术

针对配电自动化中大量电力监测数据的处理问题,提出了回避聚合操作的配电网监测数据分布式Map压缩-查询新方法。通过将监测数据分布式Map压缩存储,利用HQL查询引擎及压缩接口将分布式Map压缩应用到连接查询的混洗阶段中,减小传递到查询聚合端的数据量,提高压缩数据的查询速度,并推导了时效性的相关公式。以北京某动车段10 kV电力远动监控系统的实测数据为例,搭建了四节点测试集群。压缩导入对比测试表明,分布式Map压缩速度快于分布式Reduce压缩,分布式Map的Map_Deflate压缩处理时间比分布式Reduce_Deflate减少了45.3%;压缩-查询测试表明,当数据量为2×10~7记录级时,分布式Map的Map_LZO格式压缩-查询耗时大幅降低,比混洗阶段不压缩-查询时减少了31.6%,验证了分布式Map压缩对加速查询的时效性。

基于重叠分块的FM-index性能研究与分析

FM-index压缩查询方法结合压缩技术和索引技术,其最大优势是能够在不解开压缩文件的情况下对源文件进行查询。该文通过理论分析和详细的测试数据研究重叠分块对FM-index压缩查询性能的改善。对改进后的FM-index和压缩软件Winrar在压缩时间和文件占用空间上进行分析和比较,进一步证明了重叠分块对FM-index压缩查询性能的改善。

FM-index算法性能测试及并行化

介绍了FM-index压缩查询技术,详细阐述了FM-index的工作流程,描述了实现计算字符串在压缩文本中出现次数的算法。对FM-index的源代码在Linux平台上进行了测试,从测试结果分析了使用FM-index进行压缩查询的优点和不足。最后给出了加快FM-index压缩速度的一个并行化算法的初步设计思路。