FM-Index：利用RRR小波树（libcds）和快速后缀排序（libdivsufsort）构建的全文索引实现。

简介：
FM-Index 是一种压缩全文索引，提供了一个简洁的 C++ 实现，基于 RRR [4] 小波树 [5]。该索引能够构建一个全文索引，其范围限定在大小为 n 的给定文本 T 上，并支持多种操作，包括 count(P, m) ，用于计算大小为 m 的模式 P 在文本 T 中出现的次数； locate(P, m) ，用于在文本 T 中定位所有大小为 m 的模式 P 的文本位置； extract(A, B) ，用于从索引中提取文本 T 的子串 T[A, B]；以及 recover() ，用于从索引中恢复构建的索引所依赖的文本 T。 这种索引构造方式利用了 nH_k + o(n log sigma) 位空间 [3] 来表示文本的压缩形式，其大小约为文本 T 本身的压缩值，并且无需存储原始文本即可执行上述操作。 进一步的实证评估结果见下文的基准测试部分。 然而，FM-Index 也存在一些局限性，主要体现在其构建过程需要较长的时间，并且在构建过程中对内存资源提出了较高的要求。 索引生成过程涉及使用 ./fmbuild 命令来建立和写入 FM-Index 到文件 alice29.txt alice29.txt.fm。