Alphabet-Independent Compressed Text Indexing
Djamal Belazzougui and Gonzalo Navarro
Self-indexes are able to represent a text within asymptotically the
information-theoretic lower bound under the kth order entropy model, and
offer access to any text substring and indexed pattern searches. Their time
complexities are not optimal, however; in particular they are always multiplied
by a factor that depends on the alphabet size. In this paper we achieve, for
the first time, full alphabet-independence in the time complexities of
self-indexes, while retaining space optimality. We obtain also some relevant
byproducts.