Alphabet-Independent Compressed Text Indexing
Djamal Belazzougui and Gonzalo Navarro
Self-indexes can represent a text in asymptotically optimal space
under the k-th order entropy model, give access to text substrings, and
support indexed pattern searches. Their time complexities are not optimal,
however: they always depend 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 on compressed suffix trees.