Engineering rank/select data structures for large-alphabet strings

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 ${mathsf{rank}}$ and ${mathsf{select}}$. Our implementation significantly outperforms existing methods, improving the ${mathsf{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 ${mathsf{rank}}$ and ${mathsf{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.