Project for summer interns, summer 2013

Entropy coder for Burrows-Wheeler compressor

The purpose of the project is a further development of a compression program based on the Burrows-Wheeler transform. The compressor incorporates new techniques developed at the University of Helsinki and already achieves high performance but there is still room for improvements. The main goal of the project is to develop and implement a new entropy coder for the compressor.

The project requires C++ programming skills and understanding of algorithms and data structures. Advance knowledge of data compression techniques is not necessary.

The source for the compressor is available at https://github.com/pjmikkol/bwtc

Related publications

  1. Juha Kärkkäinen, Pekka Mikkola, Dominik Kempa. Grammar Precompression Speeds Up Burrows-Wheeler Compression.
    In Proc. 18th Symposium on String Processing and Information Retrieval (SPIRE 2011), Springer, 2012, pp. 330-335.
  2. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Slashing the Time for BWT Inversion.
    In Proc. 2012 Data Compression Conference (DCC), IEEE Computer Society 2012, pp. 99-108.
Contact person: Juha Kärkkäinen