3 ms·
> My implementation is very similar to SSA_RRR on the pizza&chilli website. Thanks for the code, I've seen you are using libcds's wavelet tree. I was wondering
by ot 16y ago
> My implementation is very similar to SSA_RRR on the pizza&chilli website.
Thanks for the code, I've seen you are using libcds's wavelet tree. I was wondering if you had implemented your own, since apart from libcds and sdsl (and some unreadable research code) I couldn't find any other implementation of the WT so I'm always curious to see if there are any developments in the engineering of wavelet trees, the current implementations are still too slow to be really useful, I think.
- matt4711 16y agoI'm trying to get myself to implement a wavelet tree. There is however a lot of low level stuff that I'm still not sure how to implement. Especially RRR. This paper [1] is the most recent practical wavelet tree paper I know of. [1] http://portal.acm.org/citation.cfm?id=1483966 http://portal.acm.org/citation.cfm?id=1483966
- ot 16y agoThere is also this one: http://portal.acm.org/citation.cfm?id=1198521 http://portal.acm.org/citation.cfm?id=1198521 Instead of RRR it uses RLE and gamma codes. Oddly, I have found no comparisons between this approach and RRR. I would expect RLE to compress better, and it is also conceptually simpler, but I don't know how fast it is.