结合无损数据压缩算法

Question

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

让我们只看两种更流行的算法：Huffman编码和Run-lenght-encoding。

假设我们有一个由数字符号组成的字母表和该字母表中任意长的符号序列：例如：

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或〈code〉Huffman-RLE，我们可以比只使用其中一个节省更多的空间，会发生什么。

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

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

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

编辑2：当我对马克·阿德勒的回复发表评论时，我意识到我可能已经找到了问题的答案。就是这样：

哈夫曼是一种符号到符号的代码，它如何影响检测？

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

这让我想到了另一点（鉴于这已经是一个很长的注释，我将在这里不讨论）：逐位分析代码。

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

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




Answer 1

这些组合是例行进行的。你应该读一些关于压缩的书。

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

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

还有许多其他变换（可能会压缩，也可能不会压缩）都是在熵编码之后进行的。其中包括Burrows-Wheeler变换（BWT）、通常遵循BWT的移前变换（MTF）、图像的离散余弦变换（可以无损完成，但最常用于有损压缩算法）等。这些变换以可逆的方式将数据中的公共性分组，为熵编码步骤提供更多增益。