The Burrows-WheelerTransform
Stc
Date: 2008-04-03
Time: 11:00
Room: BBL room 471
Speaker: Martijn van Steenbergen
Title: The Burrows-Wheeler Transform
Abstract
The Burrows-Wheeler Transform is a transformation on strings that permutes the input string in such a way that same characters are likely to be next to each other in the output string. This allows compression algorithms such as run-length encoding (RLE) to be much more efficient. Of course an ordinary sort will make RLE more efficient too, but unlike sort the Burrows-Wheeler Transform is reversible! In this talk I will show how the transform works, how its reverse works and why its reverse works.
