@inproceedings{3bffb93ad2f844caa72e1ae5b3664ef9,
title = "Grammar precompression speeds up burrows-wheeler compression",
abstract = "Text compression algorithms based on the Burrows-Wheeler transform (BWT) typically achieve a good compression ratio but are slow compared to Lempel-Ziv type compression algorithms. The main culprit is the time needed to compute the BWT during compression and its inverse during decompression. We propose to speed up BWT-based compression by performing a grammar-based precompression before the transform. The idea is to reduce the amount of data that BWT and its inverse have to process. We have developed a very fast grammar precompressor using pair replacement. Experiments show a substantial speed up in practice without a significant effect on compression ratio.",
author = "Juha K{\"a}rkk{\"a}inen and Pekka Mikkola and Dominik Kempa",
year = "2012",
doi = "10.1007/978-3-642-34109-0\_34",
language = "English",
isbn = "9783642341083",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "330--335",
booktitle = "String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings",
note = "19th International Symposium on String Processing and Information Retrieval, SPIRE 2012 ; Conference date: 21-10-2012 Through 25-10-2012",
}