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:
Glad you mentioned this. The author linked to my blog post, where I mention fast rank/select structures. There are faster ways to do it without a supporting structure too of course :) but I do like this post.
I'm interested in what you use the WT for in your job... I'm just starting off my PhD in succinct data structures, so it's nice to know that people use them :P
Cool, WT and succinct data structures are definitely an interesting field these days.
I'm primarily using as a compact order preserving structure to support fast lookups for both (token -> position) and (position -> token). I'm using an updatable variant to support O(1) appends, and then use it for realtime indexing/compression. I probably should do a blog post at one point...
Would be interesting to hear about faster ways to do rank/select without using support structures... I'll keep an eye on your blog :-)
> I'm primarily using as a compact order preserving structure to support fast lookups for both (token -> position) and (position -> token). I'm using an updatable variant to support O(1) appends, and then use it for realtime indexing/compression. I probably should do a blog post at one point...
That's very interesting, are you using raw or compressed bitmaps (such as RLE or RRR)?
A limitation of (updatable) wavelet trees is that you need to know in advance the set of symbols that you will see (otherwise you would need to change the tree structure). Is it a problem for you?
I wrote a paper with a solution to this problem, I can't share it until mid march, let me know if you are interested.
My solution is to use a fixed tree with bloated leaf nodes (use more bits per element in the leaf node). A high number of nodes with a low number of elements causes a high overhead, so I simply rebuild the tree at a few given thresholds to keep the overhad and the cost of the bloated leaf nodes down. We can discuss further by email, if you want. I'd love to read your paper! :-)
It uses the same algorithms as Sux4j for rank/select (https://github.com/ot/succinct/blob/master/rs_bit_vector.hpp) but it has exhaustive unit tests and the resulting files can be memory-mapped instead of loaded in memory, which has a number of advantages.
I'm also going to release soon an optimized implementation of wavelet trees (actually a more generic variant that we are developing).
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...