###
Run-Length FM-index

####
Veli Mäkinen and Gonzalo Navarro

The FM-index is a succinct text index needing only *O(H_k n)* bits of
space, where *n* is the text size and *H_k* is the *k*th order
entropy of the text.
Hidden in the sublinear factor lies an exponential dependence on the alphabet
size, *s*. In this paper we show how the same ideas can be used to obtain
an index needing *O(H_k n)* bits of space, with the constant factor
depending only logarithmically on *s*. Our space complexity becomes better
as soon as *s log s > 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.