Dönges, SaskaPuglisi, Simon J.Mutzel, PetraPrezza, Nicola2025-08-072025-08-072025-07-15Dönges, S & Puglisi, S J 2025, Succinct Rank Dictionaries Revisited. in P Mutzel & N Prezza (eds), 23rd International Symposium on Experimental Algorithms, SEA 2025., 15, Leibniz International Proceedings in Informatics, LIPIcs, vol. 338, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, International Symposium on Experimental Algorithms, Venice, Italy, 22/07/2025. https://doi.org/10.4230/LIPIcs.SEA.2025.15conferenceORCID: /0009-0004-2133-3661/work/189559979ORCID: /0000-0001-7668-7636/work/189562241http://hdl.handle.net/10138/599592We study data structures for representing sets of m elements drawn from the universe [0..n − 1] that support access and rank queries. A classical approach to this problem, foundational to the fields of succinct and compact data structures, is to represent the set as a bitvector X of n bits, where X[i] = 1 iff i is a member of the set. Our particular focus in this paper is on structures taking log2 (mn ) + o(n) bits, which stem from the so-called RRR bitvector scheme (Raman et al., ACM Trans. Alg., 2007). In RRR bitvectors, X is conceptually divided into n/b blocks of b bits each. A block containing c 1 bits is then encoded using log2 b + log2(cb) bits, where log b bits are used to encode c, and log2 (cb) bits are used to say which of the (cb) possible combinations the block represents. In all existing RRR implementations the code assigned to a block is its lexicographical rank amongst the (cb) combinations of its class. In this paper we explore alternative non-lexicographical assignments of codes to blocks. We show these approaches can lead to faster query times and offer relevant space-time trade-offs in practice compared to state-of-the-art implementations (Gog and Petri, Software, Prac. & Exp., 2014) from the Succinct Data Structures Library.engcc_byinfo:eu-repo/semantics/openAccesscompressed data structuresdata compressiondata structuresstring algorithmssuccinct data structurestext indexingweighted de Bruijn sequenceComputer and information sciencesConference contributionopenAccess461cda71-4497-409d-aa60-b3dd5ddaf87e105011059781