27 ms·
I'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
by matt4711 16y ago
I'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.