Practical and Parallel Text Compression for Highly Repetitive Data

我们希望开发实用的算法来压缩高度重复的数据，克服目前常见的压缩器，如gzip或bzip 2的缺点。它们是在20世纪90年代建立的，目标是当时的标准硬件;它们的主要缺点是它们不能捕获相距很远的子串的重复。第一个目标是设计一个压缩工具，它也能从长距离的重复中受益，但仍然只有适度的内存需求。第二个目标是利用几乎任何CPU中存在的共享内存并行性来加速压缩，而不会损失太多的压缩比。在这里，我们想对压缩算法有一个更广泛的了解，特别是包括语法压缩器，它为并行化提供了很好的机会。在理想的情况下，这两个更好地利用现代资源的想法将被集成到生产就绪的软件库（如Linux发行版）中，以便最终消费者可以很容易地从我们的算法工程工作中受益。

We want to develop practical algorithms for compressing highly repetitive data that overcome the shortcomings of currently common compressors such as gzip or bzip2. These have been established in the 1990s and targeted hardware that was standard in those days; their main disadvantage is that they do not capture repetitions of substrings that are far apart. The first goal is to design and engineer a compression tool that does also benefit from such long range repetitions, but still has only moderate memory requirements.As a second goal, we want to exploit the shared-memory parallelism present in virtually any CPU in order to speed up compression, without losing too much compression ratio. Here, we want to have a broader look at compression algorithms, and in particular include grammar compressors which offer excellent opportunitie for parallelization.In the ideal case, both ideas to make better use of modern resources will be integrated into production-ready software repositories (like Linux distributions) so that end consumers can benefit easily from our algorithm engineering efforts.