4 ms·
The problem with succinct data structures (and wavelet trees especially, but also rank-select dictionaries) is that while they have excellent performance charac
by siganakis 13y ago
The problem with succinct data structures (and wavelet trees especially, but also rank-select dictionaries) is that while they have excellent performance characteristics when you look at them from a theoretical perspective, they tend to perform relatively poorly in practice.
This seems to be due to how much memory is accessed when checking a single bit, and the difficulty in predicting branches.
Of course it could just be that all my implementations have sucked, but even in playing around with libcds[1] didn't yield the kind of performance expected.
If anyone knows of a fast implementation of Wavelet Trees, I'd love to see it.
[1] https://github.com/fclaude/libcds https://github.com/fclaude/libcds
- matt4711 13y agoI'm one of the authors of a more complete c++11 succinct data structure library [1] which includes several engineered implementations of wavelet trees, compressed suffix arrays and compressed suffix trees. while you are right that random access is one of the main bottlenecks of succinct data structures, we found that sometimes SDS can be faster than their uncompressed counterparts [2] The github URL contains some additional resources such as tutorial slides and cheatsheets if you want to check it out. [1] https://github.com/simongog/sdsl-lite/ https://github.com/simongog/sdsl-lite/ [2] http://people.eng.unimelb.edu.au/sgog/optimized.pdf http://people.eng.unimelb.edu.au/sgog/optimized.pdf