结合无损数据压缩算法

Question

我想知道我们可以在多大程度上进行无损数据压缩；我无法找到无损算法的在线模拟器来执行一些经验测试。我可以自己做一个，但不幸的是我这段时间没有足够的时间；我仍然对我的直觉很好奇，我将对此进行解释。

让我们仅采用两种更流行的算法：Huffman Coding和Run-lenght Enconding。

假设我们有一个数字A符号的字母表和来自该字母表的任意长的符号序列：例如：

Alphabet  = {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, W, Y, Z}
Sequence1 =  SFBJNERUSNJGSDKKDEIJGNMSDJDDSUSJNF
Sequence2 =  MNMNMNREGUHSDFJUF
Sequence3 =  MMMMMNNNNNASDUERJGASIUJMMMNNNUNS

现在，如果我们只用一个固定长度的n比特字对每个符号进行编码，我们就会得到未压缩的序列，即长N比特。

如果我们使用 Huffman 编码一个序列，我们将使用H位而不是N位，从而节省(1-H/N)*100%位空间。

如果我们使用 RLE 编码相同的序列，我们将使用R位，节省(1-R/N)*100%.

我想知道，如果我们申请RLE + Huffman或者Huffman + RLE我们可以比仅使用其中之一节省更多空间会发生什么。

对我来说，这似乎是一个非常基本的想法，但是在谷歌上搜索我没有找到关于这个主题的任何有趣的东西。

编辑：嗯，我可能没有考虑到如果我先使用 RLE，我将无法使用 Huffman，因为与单个符号的固定长度代码的对应关系会丢失；但仍然应该可以先使用霍夫曼，然后再使用 RLE。

顺便说一句，我对其中的逻辑很感兴趣，我的意思是串联使用多个无损压缩算法。

编辑 2：当我对 Mark Adler 的回复发表评论时，我意识到我可能已经找到了我的问题的答案。就是这个：

作为符号到符号代码的霍夫曼如何影响检测？

比方说，我们有下面的代码：AABCABAAB。在纯二进制中，它将被编码为00 00 01 10 00 01 00 00 01（obv 空格仅用于可读性目的）。霍夫曼将其编码为0 0 11 10 0 11 0 0 11. 空格更多地显示了字符串是如何没有改变的，因此可以检测到完全相同数量的重复，假设我们正在这个范围内（符号方式）接近代码。

这让我想到了另一点（我不会在这里讨论，因为这已经是一个很长的评论）：逐位分析代码。

所以，我实际上认为我得出了一个结论：正如我们所知，任何字典（或基于替换）编码器将可变数量的符号分组为固定长度的码字，而霍夫曼（或任何其他熵编码器）编码固定长度的符号转换成可变数量的比特，从而将熵逼近最小值；ERGO，这将是毫无意义的（且仅计算的废物）首先让霍夫曼运行，因为其他的算法将最有可能引入更多的冗余这霍夫曼也能减少。

当然这只是一篇理论论文，因为在实践中我们可以考虑其他因素（例如计算时间）......更不用说要编码的字符串的不同配置可能导致不同结果的事实。但是，嗯……这对我来说很有意义。:)

Answer 1

这些类型的组合是例行公事。你应该阅读一些关于压缩的书籍。

LZ77 是一种更通用的 RLE 形式，它复制先前字符串的重复。（距离为 1 和长度为n 的匹配对最后字节的n 个副本进行编码。）LZ77 后面通常是霍夫曼编码、算术编码或范围编码。

Huffman 应该遵循 LZ77 或 RLE，而不是先于它。霍夫曼编码将使检测重复变得更难，而不是更容易。为了首先使用 RLE，您只需将符号集扩展到文字之外。例如，zip、gzip、zlib 等中使用的 Deflate 格式有 286 个符号集来编码 256 个文字字节、29 个长度前缀代码和一个流代码的结尾。29 个长度前缀代码中的每一个都隐含了一个零到五位的后缀，它跟随着代码以添加到基值以获得长度。长度代码及其后缀的存在意味着它后面是另一个霍夫曼代码，这是 30 个距离代码前缀之一，每个前缀都有 0 到 13 位的后缀，用于指定匹配的后退距离。

还有许多其他变换（它们可能会或可能不会自行压缩）后面跟着熵编码。其中包括 Burrows-Wheeler 变换 (BWT)、Move-To-Front 变换 (MTF)，通常遵循 BWT，图像的离散余弦变换（可以无损完成，但最常用于有损压缩算法）等。以可逆方式变换数据中的组共性，为熵编码步骤提供更多增益。