View in EDS

Engineering rank/select data structures for large-alphabet strings.

Saved in:
Bibliographic Details
Title: Engineering rank/select data structures for large-alphabet strings.
Authors: Arroyuelo, Diego1 (AUTHOR), Carmona, Gabriel2 (AUTHOR), Larrañaga, Héctor3 (AUTHOR), Riveros, Francisco3 (AUTHOR), Rojas-Morales, Carlos Eugenio3 (AUTHOR), Sepúlveda, Erick3 (AUTHOR)
Source: Computer Journal. Jan2026, Vol. 69 Issue 1, p108-132. 25p.
Subjects: Data structures, Run-length encoding, Natural language processing, Data compression, Information retrieval
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. [ABSTRACT FROM AUTHOR]
Copyright of Computer Journal is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
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. [ABSTRACT FROM AUTHOR]
ISSN:00104620
DOI:10.1093/comjnl/bxaf102