Efficient Construction of FM-index Using Overlapping Block Processing for Large Scale Texts.

In previous implementations of FM-index, the construction algorithms usually need several times larger memory than text size. Sometimes the memory requirement prevents the FM-index from being employed in processing large scale texts. In this paper, we design an approach to constructing FM-index based on overlapping block processing. It can build the FM-index in linear time and constant temporary memory space, especially suitable for large scale texts. Instead of loading and indexing text as a whole, the new approach splits the text into blocks of fixed size, and then indexes them respectively. To assure the correctness and effectiveness of query operation, before indexing, we further append certain length of succeeding characters to the end of each block. The experimental results show that, with a slight loss on the compression ratio and query performance, our implementation provides a faster and more flexible solution for the problem of construction efficiency. [ABSTRACT FROM AUTHOR]