One particularly interesting aspect about rank/select is how it is amenable to SIMD. E.g. here’s a Rust implementation: https://github.com/sujayakar/rsdict
This is fun! Up until now the only succinct data I’d heard of was the “succinct circuit”. Imagine we have a 10 node graph where all edges exist (“complete”) except the edge 1->2. You could describe it in a conventional way (adjacency list, edge dict, matrix) or you could describe it as a function:
is_edge(x, y) = !(x == 1 && y == 2)
Succinct circuits can only represent a subset of graphs, but they use a fraction of the space. After all, they’re succinct!
Here’s the really interesting bit to me: checking if an edge exists is ~O(1) in a matrix. In a circuit, it’s P-complete. And this “lifts” the complexity of graph algorithms by one tier. P-complete problems become EXPTIME-complete, NP-complete problems become NEXPTIME-complete. I find that super cool!
Huge ASTs could be stored relatively compactly but still support interesting search operations, which might open up new ways to implement programming language compilers.
Guessing @conartist6 might be interested in this for BABLR.
Borland Turbo Pascal was an IDE, with editor, debugger, compiler, that ran on a system with 64K of RAM. It used a “succinct” data structure to represent the parsed program, back in the days when compact and efficient data representation was a necessity, not an obscure novelty, due to memory constraints. Sorry, can’t find a reference for the details, I read about this years ago. I remember it was supposed to be some sort of pointer-free compact byte code representation. I’m wondering how similar these “new ways” are to the old ways of implementing compilers.
The method I’ve used for rank involves precomputing rank sums: you keep a running total of 1 bits for each large block (every 64kb, for example), and then a second array of counts within smaller blocks (maybe every 4kb). You store each packed into only as many bits as they need, and the block sizes can be tuned for time/space tradeoffs.
To find the rank of a bit offset, you’d start with the preceding 64k block’s total, then add each 4k block’s count until you’re close to the offset, then popcount the remaining individual 64-bit words up to the exact bit offset. This can be made reasonably efficient. It’s also effectively constant time, since there’s one random access for the large block total, followed by adding a bounded number of adjacent smaller block counts within the final large block, then a bounded number of word popcounts within the final small block.
For select, you can binary search on that rank result, or you can build a similar index using precomputed tables to jump to roughly the right area, then scan and count bits to find the exact offset. Either rank or select can be implemented in terms of the other.
My implementation was for a LOUDS, a kind of succinct trie structure whose backing bitvector has an almost perfectly even balance of 1s and 0s by design. There are different approaches with better tradeoffs if you know the ratio of 0s to 1s is likely to be very skewed, though.
I found Erik Demaine’s open courseware lectures about succinct data structures particularly helpful when I was first learning about those data structures – I think it was sessions 17 and 18 here, but it may have been different recordings from the same course. He describes the block sample sum and popcounting approach.
For more depth, Gonzalo Navarro’s Compact Data Structures describes a couple other approaches for rank & select, along with several other succinct structures. If you’re at all interested in this stuff I’d absolutely recommend checking it out, it’s a challenging read at times but it’s fascinating.
Good question I myself don’t know the answer to, but I’m sure there are papers you can dig up (keywords “succinct rank select” should get you started). You can also look at existing implementations such as the one in the vers crate.
I’ve been looking into rank-select (broadword rank9 tricks) and Elias Fano. I a trying to figure out the optimal indexing structures for fast capture of waveform (arbitrary fields really) with chunked compression. Haven’t had any good insights into my problem but I’ve found succinct data structures fascinating.
You talk about indexing XML files, but I’ve also seen this technique used for JSON. The Hackage
hw-json-simdpackage draws on the paper Semi-indexing Semi-structured Data in Tiny Space, which you might find interesting.Thank you for that reference, I will read that with interest!
One particularly interesting aspect about rank/select is how it is amenable to SIMD. E.g. here’s a Rust implementation: https://github.com/sujayakar/rsdict
The vers crate I mention also has SIMD support, available behind a feature.
This is fun! Up until now the only succinct data I’d heard of was the “succinct circuit”. Imagine we have a 10 node graph where all edges exist (“complete”) except the edge
1->2. You could describe it in a conventional way (adjacency list, edge dict, matrix) or you could describe it as a function:Succinct circuits can only represent a subset of graphs, but they use a fraction of the space. After all, they’re succinct!
Here’s the really interesting bit to me: checking if an edge exists is ~O(1) in a matrix. In a circuit, it’s P-complete. And this “lifts” the complexity of graph algorithms by one tier. P-complete problems become EXPTIME-complete, NP-complete problems become NEXPTIME-complete. I find that super cool!
Guessing @conartist6 might be interested in this for BABLR.
Borland Turbo Pascal was an IDE, with editor, debugger, compiler, that ran on a system with 64K of RAM. It used a “succinct” data structure to represent the parsed program, back in the days when compact and efficient data representation was a necessity, not an obscure novelty, due to memory constraints. Sorry, can’t find a reference for the details, I read about this years ago. I remember it was supposed to be some sort of pointer-free compact byte code representation. I’m wondering how similar these “new ways” are to the old ways of implementing compilers.
This is wonderful. So, the question now is, how do I implement efficient rank/select for bitvectors?
The method I’ve used for rank involves precomputing rank sums: you keep a running total of 1 bits for each large block (every 64kb, for example), and then a second array of counts within smaller blocks (maybe every 4kb). You store each packed into only as many bits as they need, and the block sizes can be tuned for time/space tradeoffs.
To find the rank of a bit offset, you’d start with the preceding 64k block’s total, then add each 4k block’s count until you’re close to the offset, then popcount the remaining individual 64-bit words up to the exact bit offset. This can be made reasonably efficient. It’s also effectively constant time, since there’s one random access for the large block total, followed by adding a bounded number of adjacent smaller block counts within the final large block, then a bounded number of word popcounts within the final small block.
For select, you can binary search on that rank result, or you can build a similar index using precomputed tables to jump to roughly the right area, then scan and count bits to find the exact offset. Either rank or select can be implemented in terms of the other.
My implementation was for a LOUDS, a kind of succinct trie structure whose backing bitvector has an almost perfectly even balance of 1s and 0s by design. There are different approaches with better tradeoffs if you know the ratio of 0s to 1s is likely to be very skewed, though.
I found Erik Demaine’s open courseware lectures about succinct data structures particularly helpful when I was first learning about those data structures – I think it was sessions 17 and 18 here, but it may have been different recordings from the same course. He describes the block sample sum and popcounting approach.
For more depth, Gonzalo Navarro’s Compact Data Structures describes a couple other approaches for rank & select, along with several other succinct structures. If you’re at all interested in this stuff I’d absolutely recommend checking it out, it’s a challenging read at times but it’s fascinating.
Good question I myself don’t know the answer to, but I’m sure there are papers you can dig up (keywords “succinct rank select” should get you started). You can also look at existing implementations such as the one in the vers crate.
This might be helpful, I just ran into it (in an unfortunately phrased orange site comment…)
https://stackoverflow.com/questions/72580828/what-is-a-succinct-rank-data-structure-how-does-it-work
I’ve been looking into rank-select (broadword rank9 tricks) and Elias Fano. I a trying to figure out the optimal indexing structures for fast capture of waveform (arbitrary fields really) with chunked compression. Haven’t had any good insights into my problem but I’ve found succinct data structures fascinating.