Run-Length FM-index

The FM-index is a succinct text index needing only O(Hkn) bits of space, where n is the text size and Hk is the kth order entropy of the text. FM-index assumes constant alphabet; it uses exponential space in the alphabet size, σ. In this paper we show how the same ideas can be used to obtain an index needing O(Hkn) bits of space, with the constant factor depending only logarithmically on σ. Our space complexity becomes better as soon as σ log σ>log n, which means in practice for all but very small alphabets, even with huge texts. We retain the same search complexity of the FM-index. FM-index The FM-index [3] is based on the Burrows-Wheeler transform (BWT) [1], which produces a permutation of the original text, denoted by T bwt = bwt(T). String T bwt is a result of the following forward transformation: (1) Append to the end of T a special end marker $, which is lexicographically smaller than any other character; (2) form a conceptual matrix M whose rows are the cyclic shifts of the string T $, sorted in lexicographic order; (3) construct the transformed text L by taking the last column of M. The first column is denoted by F