演讲人： Elad Verbin ITCS, Tsinghua University
时间： 2007-09-14 14:40-2007-09-14 16:40
地点：FIT Building 4-603, Tsinghua University
课件下载：点击下载
内容：
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.
In the first part of the talk 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 present upper bounds and lower bounds on the compression ratio of BWT-based compressors, as a function of the (k -th order) entropy of the input stream.
Lastly, I'll present a research direction which I find particularly interesting.
The talk is intended for a general computer-science audience. No background on compression algorithms is assumed.
This is based on joint work with Haim Kaplan and Shir Landau.
个人简介:
Elad Verbin has done his Ph.D. studies in Tel Aviv University, and is now a postdoc at ITCS, Tsinghua University. He is interested in combinatorial algorithms and in randomized algorithms.
