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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-34109-0_34 | SPIRE |
Keywords | Field | DocType |
ziv type compression algorithm,grammar-based precompression,compression ratio,grammar precompression speed,bwt-based compression,substantial speed,wheeler compression,pair replacement,main culprit,good compression ratio,fast grammar precompressor,text compression | Compression (physics),Inverse,Data compression ratio,Burrows–Wheeler transform,Computer science,Algorithm,Grammar,Compression ratio,Data compression,Speedup | Conference |
Volume | ISSN | Citations |
7608 | 0302-9743 | 1 |
PageRank | References | Authors |
0.36 | 10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Juha Kärkkäinen | 1 | 1354 | 95.20 |
Pekka Mikkola | 2 | 1 | 0.36 |
Dominik Kempa | 3 | 142 | 16.37 |