FM-index压缩查询算法解析

Analysis on FM-index Compression Enquiry Algorithm

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

FM-index is an advanced compression information index method in the world.It is an integration of compression technology and index technology,which supports the enquiry of source files when they are uncompressed.This paper makes a detailed analysis on how FM-index performs compression,establishes index and realizes enquiry and positioning algorithm trader compression condition,and provides reference for relevant research as well as the application and improvement of FM-index algorithm in practice.