Papers & Presentations

Atoms frequently share what they know in journals, at conferences, and in classrooms.

The Burrows-Wheeler Transform: Better Compression with a Reversible Sort

Presented by
Presented at
The Burrows-Wheeler Transform: Better Compression with a Reversible Sort
at
!!Con
|
May 1, 2015
Additional Presentations:
Written in
!!Con
|
May 2015

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.