parallel-processing - 是否可以使 lzw 压缩/解压缩并行？

Question

我已经阅读了这篇关于如何使用 LZW 压缩/解压缩数据的文章，但我希望让它使用多个线程......但我认为这是不可能的。你怎么看？关于这个主题的任何论文或文章？甚至提示如何做到这一点。

Answer 1

您可能想阅读这篇论文，特别是第 2.2 节准确解释了如何并行化 LZW 方案。

Answer 2

在低级别并行化压缩算法将提供有限的加速，并且可能比它的价值更麻烦。原因是真正的好处在于压缩大量数据。在这种情况下，简单地将数据分解成碎片并使用普通算法单独压缩它们要容易得多。

LZW 很老，效果不是很好。其他方法可以更快更有效地压缩。您可以查看从lz4到zlib到lzma到 ppmd、paq 等的各种方案，按照从最快压缩最少到最慢压缩最好的顺序。并行化的一个例子是pigz，它使用zlib使用尽可能多的处理器和内核将大文件压缩为gzip 格式。它以并行方式提供从先前块到后续块的历史记录，以便与串行、单处理器 gzip 压缩相比不会失去压缩效率。

Answer 3

当需要进行大量整数运算时，使用多线程并行化压缩或解压缩算法是合理的。但lzw不需要它。例如，您可以查看lzws源代码。

整数运算量很少。主要瓶颈是dictionary。您可以使用内存超频和自定义 malloc realloc 策略获得更高的性能。