Rank/select operations on large alphabets
Alexander Golynski, J. Ian Munro, S. Srinivasa Rao · Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 · 2006
We consider a generalization of the problem of supporting rank and select queries on binary strings. Given a string of length n from an alphabet of size σ, we give the first representation that supports rank and access operations in O(lg lg σ) time, and select in O(1) time while using the optimal n lg σ + o(n lg σ) bits. The best known previous structure for this problem required O(lg σ) time, for general values of σ. Our results immediately improve the search times of a variety of text indexing methods.