[Colloquium] TTI-C Show and Tell Series (Elad Verbin)

[Katherine Cumming]

Speaker:  Elad Verbin, TTI-C and Tel Aviv University
Speaker's home page:
 
Date: Tuesday, August 1, 2006 
Location:  TTI-C Conference Room 
Time:  12:30 pm
Lunch served at 12:00pm
 
 
Speaker: Elad Verbin, TTI-C and Tel Aviv University
 
Title: Text-Compression using the Burrows-Wheeler Transform
 
ABSTRACT:
 
In 1994, Burrows and Wheeler introduced the Burrows-Wheeler
Transform (BWT). Using the BWT they gave two new lossless text
compression algorithms. A well known implementation of these
algorithms is bzip2, which is installed in most unix environments.
BWT-based text compressors are particularly easy to implement, and
give quite good compression ratios. For example, bzip2 typically
compresses text files to about 80% of what gzip does.
 
The first part of the talk will consist of my personal perspective
on BWT-based compression. I will give a detailed presentation of the
Burrows-Wheeler Transform and of the compression algorithms based on
it, along with an intuitive explanation of why they work well.
 
In the second part of the talk I will discuss a theoretical result
by Haim Kaplan, Shir Landau, and myself which was first presented in
CPM '06. We prove a worst-case upper bound on the compression ratio
of a specific BWT-based compressor, called BW0. Specifically, we
adopt a commonly-used statistic that measures compressibility of a
text, called the order-k empirical entropy. We prove that for any
text, the compression ratio of BW0 is upper bounded by a function of
the order-k empirical entropy of the text. This improves and
simplifies Manzini's results from 1999, which were the first
worst-case bounds on BWT-based compression.
 
The talk is intended for a general computer-science audience. No
background on compression algorithms is assumed.
 
 
If you have questions, or would like to meet the speaker, please contact
the Assistant Administrator at 773-834-1994 or darren1 at uchicago.edu
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.   TTI-C (1427 East
60thStreet, Chicago, IL  60637)
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060731/ae82f34b/attachment.htm