I'm trying to get myself to implement a wavelet tree. There is however a lot of ... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		matt4711 on March 22, 2011 \| parent \| context \| favorite \| on: Succinct Data Structures: Cramming 80,000 words in... 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

ot on March 22, 2011 [–]

There is also this one: 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.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact