Re:Writing a competitive BZip2 encoder in Ada from scratch i...
by amy_petrik on Saturday August 16, 2025 @11:15PM
(#44928579)
well here's a big surprise of BWT
BWT is a transformation transforming a string into "suffix tree space"
You can do searches - very fast searches - in BZ2/BWT compression space
Discussed in the '90s in the legendary dr. dobbs
But more significantly, BWT is the basis for most DNA and RNA sequence aligners nowadays - which perform string search/matching in suffix tree (transformed) space. It's like doing frequency stuff in fourier domain, it's like adding is multiplication in logspace - but in weird data string search space. The BWT.
BWT is a transformation transforming a string into "suffix tree space"
You can do searches - very fast searches - in BZ2/BWT compression space
Discussed in the '90s in the legendary dr. dobbs
But more significantly, BWT is the basis for most DNA and RNA sequence aligners nowadays - which perform string search/matching in suffix tree (transformed) space. It's like doing frequency stuff in fourier domain, it's like adding is multiplication in logspace - but in weird data string search space. The BWT.