Wavelet trees are awesome. There are several ways to speed up the rank/select operations, which the article doesn't mention. For example, you can create a simple (popcount, offset) index for each bitmap. Then when you need to find the nth bit (the select operation), you can simply do a binary search to find the offset with the nearest count. Likewise for the access (or the rank operation) you can find the popcount for the nearest offset in the index.
I use wavelet tree heavily in my job. They are very useful for compact representations of order preserving collections of strings which supports fast lookups.
Update: Sux4j has some interesting implementations of fast select/rank:
I use wavelet tree heavily in my job. They are very useful for compact representations of order preserving collections of strings which supports fast lookups.
Update: Sux4j has some interesting implementations of fast select/rank:
http://sux.dsi.unimi.it/
http://sux4j.dsi.unimi.it/docs/it/unimi/dsi/sux4j/bits/Selec...