Home
Schedule
Abstract Template
Masters Attendance

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.