News for hackers. Stuff that matters.
Re:The Burrows-Wheeler Transform by mfworks on Thursday October 09, 2025 @11:19PM (#45535105)
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.
Re:The Burrows-Wheeler Transform by dcl on Friday October 10, 2025 @12:08AM (#45535286)
A 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.
Re:The Burrows-Wheeler Transform by dgacmu on Thursday October 09, 2025 @11:28PM (#45535142)
I 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.