Cool Algorithm - Fast text search using BWT
blog.avadis-ngs.com
Cool Algorithm - Fast text search using BWT
1–9 of 9 posts
Re: Cool Algorithm - Fast text search using BWT
#2As far as I can tell, author is talking about FM-Index. It compresses the search data into a much smaller index memory footprint. I tried using it few times, but never figured out how to use it as a key-value data store.
If anybody is interested, here is the code: http://pizzachili.di.unipi.it/indexes/FM-indexV2/fmindexV2.t...
Re: Cool Algorithm - Fast text search using BWT
#3As far as I can tell, author is talking about FM-Index. It compresses the search data into a much smaller index memory footprint. I tried using it few times, but never figured out how to use it as a key-value data store. If anybody is interested, here is the code: http://pizzachili.di.unipi.it/indexes/FM-indexV2/fmindexV2.t...
yes this is FM index. The linked paper is authored by Ferragina and Manzini, which is how the name FM index comes.
Re: Cool Algorithm - Fast text search using BWT
#4As far as I can tell, author is talking about FM-Index. It compresses the search data into a much smaller index memory footprint. I tried using it few times, but never figured out how to use it as a key-value data store. If anybody is interested, here is the code: http://pizzachili.di.unipi.it/indexes/FM-indexV2/fmindexV2.t...
I guess FM index is just not the right thing to use when you need a key-value data store. It's a full text index -- a data structure, which allows fast substring queries over a fixed text corpus.
Re: Cool Algorithm - Fast text search using BWT
#5As far as I can tell, author is talking about FM-Index. It compresses the search data into a much smaller index memory footprint. I tried using it few times, but never figured out how to use it as a key-value data store. If anybody is interested, here is the code: http://pizzachili.di.unipi.it/indexes/FM-indexV2/fmindexV2.t...
I guess FM index is just not the right thing to use when you need a key-value data store. It's a full text index -- a data structure, which allows fast substring queries over a fixed text corpus.
Perhaps if you want to store (tag) sub-strings with stored data then it might make sense?
Re: Cool Algorithm - Fast text search using BWT
#6Earlier quoted context omitted.
I guess FM index is just not the right thing to use when you need a key-value data store. It's a full text index -- a data structure, which allows fast substring queries over a fixed text corpus.
Perhaps if you want to store (tag) sub-strings with stored data then it might make sense?
Yup, that might work, but still, this is a weird idea for a key-value store, maybe a DAWG or a radix tree would do better.
Re: Cool Algorithm - Fast text search using BWT
#7BWT is a really neat trick, I first came across it in Andrew Tridgell's thesis on rsync, which is worth a read (http://www.samba.org/~tridge/phd_thesis.pdf). I changed PMD's copy-paste detector (CPD) to use it, which at the time was a massive improvement over its brute-force approach:
http://onjava.com/pub/a/onjava/2003/03/12/pmd_cpd.html?page=...
...fairly obviously, the sorted permutations of BWT allow you just to read off duplicates; I was using permutations of tokens not characters.
CPD now uses Rabin-Karp searching, which is faster still. However, writing a copy-paste detector with BWT is fairly trivial and I still keep that script in my head for languages CPD can't handle.
Re: Cool Algorithm - Fast text search using BWT
#8This is awesome!
Re: Cool Algorithm - Fast text search using BWT
#9Also see Alex Bowe's blog for a description of this:
http://www.alexbowe.com/tag/datastructures