Practical and Parallel Text Compression for Highly Repetitive Data

我们希望开发实用的算法来压缩高度重复的数据，以克服当前常见的压缩器（如gzip或bzip2）的缺点。这些公司成立于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.