4 ms·

I wonder if they're using succint data structures. I'm in bioinformatics and the first time I implemented a wavelet tree to reduce the size of genomes in memor

I wonder if they're using succint data structures. I'm in bioinformatics and the first time I implemented a wavelet tree to reduce the size of genomes in memory.. It was just breathtaking.

ausjke 9y ago
very interesting, can you elaborate and on it a little more? I need quick fuzzy search on a low-end embedded device that has limited storage(both RAM and HDD), was thinking about putting the index on a server with plenty RAM then do websocket or RPC for that.
- ethanwillis 9y ago
  There's a very good blog post for the implementation details here: http://alexbowe.com/wavelet-trees/ http://alexbowe.com/wavelet-trees/ I had a decent implementation in Python, but it's on my old macbook that I would need to dig up. If you're interested you can add me on telegram: @rightcheek. Now to go with Wavelet trees you may or may not need to know about suffix arrays and optimal suffix array construction. Take a look at this: https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array This is what's going to give you space efficiency in combination with a wavelet tree. And the wavelet tree also gives you good rank/select efficiency. Edit: Here's a suffix array construction algorithm implementation I did (not sure if it's fully correct) https://github.com/ethanwillis/comp7295_final/blob/master/saca.py https://github.com/ethanwillis/comp7295_final/blob/master/sa... It is based on this paper: https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf https://local.ugene.unipro.ru/tracker/secure/attachment/1214...
dogruck 9y ago
Neat, TIL about wavelet trees. https://en.m.wikipedia.org/wiki/Wavelet_Tree https://en.m.wikipedia.org/wiki/Wavelet_Tree
jagger27 9y ago
That's a beautiful structure. Thanks for sharing.

4 ms·

I wonder if they're using succint data structures. I'm in bioinformatics and the first time I implemented a wavelet tree to reduce the size of genomes in memor

by ethanwillis 9y ago

I wonder if they're using succint data structures. I'm in bioinformatics and the first time I implemented a wavelet tree to reduce the size of genomes in memory.. It was just breathtaking.

ausjke 9y ago
very interesting, can you elaborate and on it a little more? I need quick fuzzy search on a low-end embedded device that has limited storage(both RAM and HDD), was thinking about putting the index on a server with plenty RAM then do websocket or RPC for that.
- ethanwillis 9y ago
  There's a very good blog post for the implementation details here: http://alexbowe.com/wavelet-trees/ http://alexbowe.com/wavelet-trees/ I had a decent implementation in Python, but it's on my old macbook that I would need to dig up. If you're interested you can add me on telegram: @rightcheek. Now to go with Wavelet trees you may or may not need to know about suffix arrays and optimal suffix array construction. Take a look at this: https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array This is what's going to give you space efficiency in combination with a wavelet tree. And the wavelet tree also gives you good rank/select efficiency. Edit: Here's a suffix array construction algorithm implementation I did (not sure if it's fully correct) https://github.com/ethanwillis/comp7295_final/blob/master/saca.py https://github.com/ethanwillis/comp7295_final/blob/master/sa... It is based on this paper: https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf https://local.ugene.unipro.ru/tracker/secure/attachment/1214...
dogruck 9y ago
Neat, TIL about wavelet trees. https://en.m.wikipedia.org/wiki/Wavelet_Tree https://en.m.wikipedia.org/wiki/Wavelet_Tree
jagger27 9y ago
That's a beautiful structure. Thanks for sharing.