I'm one of the authors of a more complete c++11 succinct data structure library [1] which includes several engineered implementations of wavelet trees, compress

I'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