摘要： 介绍了FM-index压缩查询技术,详细阐述了FM-index的工作流程,描述了实现计算字符串在压缩文本中出现次数的算法。对FM-index的源代码在Linux平台上进行了测试,从测试结果分析了使用FM-index进行压缩查询的优点和不足。最后给出了加快FM-index压缩速度的一个并行化算法的初步设计思路。
关键词:
FM-index,
压缩查询,
BW转换,
后缀数组
Abstract: FM-index is a new technology for searching compressed text.This paper introduceds the working procedure of FM-index and analyzes the algorithm of counting string occurrence in compressed text.The source code of FM-index is tested on two kinds of Linux platforms.Based on the experimental results,it summarizes the advantages of adopting FM-index to search compressed text.Finally,it puts forward one elementary parallel method to accelerate FM-index compress speed.
中图分类号:
张广治,张云泉,李伟华,李玉成. FM-index算法性能测试及并行化[J]. , 2005, 31(22): 61-63.
ZHANG Guangzhi1,ZHANG Yunquan1,2,LI Weihua3,LI Yucheng1,2. Performance Testing of FM-index Algorithm and Parallelization[J]. , 2005, 31(22): 61-63.