3 ms·
Something like that + data compression. If you have some data type mapped to a sequence of symbols, WT can speed up search in it. Please also note it is not a c
by aist11 14y ago
Something like that + data compression. If you have some data type mapped to a sequence of symbols, WT can speed up search in it. Please also note it is not a complete full text search index (like ones used in genome sequencing). It is a rank/select dictionary.
- dunham 14y agoI believe he's doing full text search on this by running Burrows-Wheeler on the data first. See here for more details: http://alexbowe.com/fm-index/ I started reimplementing all of this in Go about a year ago, but moved onto other stuff before I finished.
- aist11 14y agoSure, that is what I meant. Some additional structures (BWT, ...) are required for a complete FTS. WT allows only 1-symbol searches that might be enough in practical applications (databases?). I also have an implementation of dynamic LOUDS-based multiary WT (it is much faster on large alphabets), but it haven't been fully finished yet.