Alphabet-Independent Compressed Text Indexing
Djamal Belazzougui, Gonzalo Navarro · ACM Transactions on Algorithms · 2014
Self-indexes are able to represent a text asymptotically within the information-theoretic lower bound under thekth 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 article, we achieve, for the first time,full alphabet independencein the time complexities of self-indexes while retaining space optimality. We also obtain some relevant byproducts.