3 ms·
The most magical part of this transform is the search! First learned about this in a bioalgorithms course, and the really cool property is that for a string len
by mfworks 1y ago
The most magical part of this transform is the search! First learned about this in a bioalgorithms course, and the really cool property is that for a string length l, you can search for the string in O(l) time. It has the same search time complexity of a suffix tree with O(n) space complexity (with a very low constant multiple). To this day it may be the coolest algorithm I've encountered.
- dgacmu 1y agoI encountered the search version of this, which is turned suffix arrays, in grad school and was so taken by them I incorporated them as the primary search mechanism for the pi searcher. 25 years later it's still the best way to do it. Incredible insight behind bwt and suffix arrays.
- dcl 1y agoA friend doing bioinformatics told me about this at uni, it was definitely one of those "i can't believe this is doable" sort of things.