提问人：Ian Kilty 提问时间：11/2/2023 更新时间：11/4/2023 访问量：70
如何找到可以使用霍夫曼编码最有效地压缩的二进制符号集？
How to find the set of binary symbols that can most efficiently compress using Huffman coding?
问：
在我当前使用霍夫曼编码的文件压缩实现中，我采用每个字节的频率并从那里构建树。
我在想，如果我不将程序限制为仅计算字节的频率，而是计算任何长度的二进制符号的频率，则有可能进一步压缩。
例如，在文本文件中，如果有一个“q”，下一个字节始终是“u”。与其使用“q”和“u”，不如使用“qu”和“u”。
但是，不仅仅是连接字节，而是任何长度的任何类型的二进制符号。
我想生成所有可能的消息，然后以某种方式使用某种 Mealy 机器实现选择不重叠的符号子集并生成频率，但我不知所措。
答：
0赞
oleksii
11/4/2023
#1
这是 Kolmogorov、Solomonoff、Chaitin 等人在 1960 年至 1970 年研究的问题。维基百科给出了一个很好的概述，你可以从那里找到原始论文。Kolmogorov 复杂性涉及找到可以再现给定任意输入字符串的最短程序长度的想法。术语“任意”是指任何输入，包括无限多和随机的输入。
研究柯尔莫戈罗夫复杂性的一个关键点是，从根本上说，不可能编写一个单一的通用程序，可以将任意输入字符串压缩到小于输入字符串本身加上一些字节的大小。这种限制来自任意随机噪声数据的本质。随机数据无法压缩。但是，如果您对数据中的内部结构或模式有特定的了解，则可以设计比通用无损压缩更有效的算法，或者为现有算法提供更好的论据。
作为一种实用的方法，您可以尝试使用不同的通用无损压缩算法，并检查它们在数据上的性能。尝试不同的压缩级别和字典大小。更好的压缩通常会影响压缩数据所需的时间。
在某些情况下，如果您有许多包含重复数据的短字符串，您可以尝试训练压缩器并使用已预先计算的字典，以较小的输出使压缩运行得更快。
从评论中我注意到这可能与DNA序列压缩有关-这是一个单独的活跃研究领域，并且有许多关于该主题的论文。我会从那里开始。
评论
qu