Campus Event Calendar
Event Entry
What and Who
bzip2 Compression: Burrows-Wheeler, Move-to-Front and Huffman
Ingmar Weber
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (basic education)
AG 1, AG 2, AG 3, AG 4, AG 5
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 30 May 2006
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
My goal is to give an overview of some nice ideas of a current (text) compression algorithm. No basic knowledge about compression algorithms will be assumed.
I'll explain the basic ideas of the bzip2 algorithm, using text compression as an example.
The key ingredients are:
* The Burrows-Wheeler transform (a reversible "quasi-sorting" algorithm)
* Move-to-Front transformation (a simple trick to exploit local properties for compression)
* Huffman encoding (as one algorithm for entropy encoding)
Maybe I'll also briefly discuss Arithmetic Coding (which is not used in bzip2 due to patent regulations).
I will not discuss any implementation details.
Contact
Ingmar Weber
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Text compression
Ingmar Weber, 05/10/2006 12:52 -- Created document.