Abstract Large-alphabet strings, prevalent in information retrieval and natural language processing, pose unique storage and processing challenges. This paper explores the efficient implementation of the alphabet-partition approach, introducing a compressed data structure that efficiently supports the operations rank and select. Our implementation significantly outperforms existing methods, improving the select operation speed by 80% with only 11% additional space. We demonstrate the utility of our structure in various applications, including inverted list intersections, run-length compressed strings, and distributed computation of rank and select. Notably, for run-length compressed strings using the Burrows–Wheeler transform, our data structure requires only 0. 98–1. 09 times the space of state-of-the-art RLFM-indexes to achieve 1. 23–2. 33 times faster pattern occurrence counting while also providing better theoretical guarantees.
Arroyuelo et al. (Mon,) studied this question.