C# 快速高效地压缩大量数据块

Question

我有大约270k个数据块对，每个对由一个32KiB和一个16KiB的块组成。

当我将它们保存到一个文件中时，会得到一个非常大的文件。但是数据很容易压缩。使用WinRAR进行强压缩后，5.48GiB的文件大小变为了37.4MiB。

但是我需要随机访问每个单独的块，因此我只能逐个压缩块。为此，我使用了.NET提供的Deflate类，将文件大小减小到了382MiB（这已经可以接受了）。但速度不够快。

很多速度损失可能是由于始终为每个块创建新的MemoryStream和Deflate实例引起的。但似乎它们并不是设计用于重复使用的。

而且我想（更好的？）压缩可以通过使用“全局”字典来实现，而不是为每个块都使用一个字典。

是否有适合该任务的压缩算法实现（最好是C#）？

以下链接包含每个字节号出现的百分比，分为三种块类型（仅限32KiB块）。第一和第三种块类型的出现率为37.5％，第二种为25％。 块类型百分比 长话短说： Type1主要由1组成。 Type2主要由0和1组成。 Type3主要由0组成。 大于128的值尚未出现。

16KiB块几乎总是由零组成。

- Arokh

---

实际上，在deflate中，字典被限制为32K（一个“滑动窗口”，每添加一个输入字节时最旧的字节将被移除）。 - Cameron

你愿意编写自己的压缩/解压缩程序吗？ - Cameron

Answer 1

如果您想尝试不同的压缩方式，可以从RLE开始尝试，这对于您的数据应该是适合的。链接如下：http://en.wikipedia.org/wiki/Run-length_encoding，即使在最简单的实现中，它也会非常快速。相关的http://en.wikipedia.org/wiki/Category:Lossless_compression_algorithms包含更多链接，如果您想自己编写或找到他人的实现，则可以从其他算法开始。

随机评论： "...A lot of the speed loss is probably ..." 不是解决性能问题的方法。请测量并查看是否真的存在问题。

- Alexei Levenkov

---

+1 对于 RLE 和基准测试的评论。RLE + Huffman 编码可能会提供相当不错的压缩率，并且比常规 deflate 更快。当然，Huffman 编码需要更多的操作。 - Cameron

RLE 似乎已经找到了宝藏。在对数据结构进行一些修改以优化 RLE 后，它现在可以轻松地与 deflate 竞争。虽然 RLE 的大小略大，但我有一些进一步优化的想法。 - Arokh

Answer 2

Gzip被认为是“不错”的，这意味着压缩比可以接受，速度也很快。 如果你想要更高的压缩比，还有其他选择，比如7z。

如果你想要更快的速度，似乎这是你的目标，更快的替代方案将在一定的压缩效率成本下提供显著的速度优势。 "显著"应翻译为多倍速度更快，例如5x-10x。这样的算法在“内存”压缩场景中备受青睐，例如你的场景，因为它们使得访问压缩块几乎没有痛苦。

例如，Clayton Stangeland刚刚发布了C#的LZ4。源代码可在此处以BSD许可证获得： https://github.com/stangelandcl/LZ4Sharp 项目主页上有一些与gzip的比较指标，例如：

i5 memcpy 1658 MB/s
i5 Lz4 Compression 270 MB/s Decompression 1184 MB/s  
i5 LZ4C# Compression 207 MB/s Decompression 758 MB/s 49%
i5 LZ4C# whole corpus Compression 267 MB/s Decompression 838 MB/s Ratio 47%
i5 gzip whole corpus Compression 48 MB/s Decompression 266 MB/s Ratio 33%

希望这能帮到你。

- Cyan

Answer 3

无论你如何尝试，都无法随机访问Deflate流（除非你放弃LZ77部分，但这正是目前大多数情况下使压缩比高的原因——即使这样，也有棘手的问题要解决）。这是因为压缩数据的一部分允许引用前面32K字节的先前部分，该先前部分可能反过来引用另一部分等等，即使你确定所需数据在压缩流中的确切位置（目前你不知道），你最终还是需要从开始解码流以获取所需数据。

但是，你可以使用一个流将许多（但不是所有）块一起压缩。然后你会得到相当好的速度和压缩效果，但你不必解压缩所有块才能获得想要的那个块；只需解压缩包含你块的特定块即可。你需要一个额外的索引来跟踪文件中每个压缩块的起始位置，但这是相当低的开销。把它看作是在压缩所有内容（这对于压缩很好，但对于随机访问很糟糕）和逐个压缩每个块之间做出的妥协（这对于随机访问很好，但对于压缩和速度很糟糕）。

- Cameron