The Burrows-Wheeler Transform: Better Compression with a Reversible Sort
The Burrows-Wheeler Transform is my favorite algorithm! It partially sorts data, exposing structural patterns that make other compression algorithms more effective. Amazingly, the original input can be recovered from just the transformed data with just a starting offset.
In this talk, I'll give a bit of background info about the BWT and its uses, then reveal the insights that make it possible. I'll build up a straightforward version in Python, then show optimizations a production implementation might make.