huffman-code - 结合无损数据压缩算法

Question

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

让我们仅采用两种更流行的算法:霍夫曼编码和运行长度编码。

假设我们有一个由数字 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 位。

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

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

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

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

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

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

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

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

假设我们有以下代码:AABCABAAB。 在纯二进制中，它将被编码为 00 00 01 10 00 01 00 00 01 (obv 空格仅用于可读性目的)。 霍夫曼将其编码为 0 0 11 10 0 11 0 0 11。空格更多地显示了字符串如何不被更改，因此假设我们在此范围内处理代码(符号方面)，则可以检测到完全相同数量的重复。

这让我想到了另一点(鉴于这已经是很长的评论，我不会在这里讨论):按位分析代码。

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

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

Answer 1

这些组合是常规完成的。您应该阅读一些有关压缩的书籍。

LZ77 是 RLE 的更通用形式，它复制先前字符串的重复项。 (距离一和长度n的匹配编码最后字节的n个副本。)LZ77通常后面跟着霍夫曼、算术或范围编码。

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

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