压缩有理论限制吗？
想象一下，在接下来的 10 年里，您可以使用世界上所有的超级计算机。你的任务是尽可能无损地压缩 10 部完整长度的电影。另一个标准是普通计算机应该能够即时解压缩，并且不需要花费太多硬盘来安装解压缩软件。
我的问题是，与当今最好的替代方案相比，您能实现多少压缩？ 1%、5%、50%？更具体地说：给定固定的字典大小（如果也称为视频压缩），压缩是否存在理论上的限制？
Imagine that you had all the supercomputers in the world at your disposal for the next 10 years. Your task was to compress 10 full-length movies losslessly as much as possible. Another criteria was that a normal computer should be able to decompress it on the fly and should not need to spend much of his HD to install the decompressing software.
My question is, how much more compression could you achieve than the best alternatives today? 1%, 5%, 50%? More specifically: is there a theoretical limit to compression, given a fixed dictionary size (if it is called that for video compression as well)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
压缩的限制由源的随机性决定。欢迎学习信息论！请参阅数据压缩。
The limits of compression are dictated by the randomness of the source. Welcome to the study of information theory! See data compression.
存在理论上的限制：我建议阅读此关于信息论和鸽子洞原理的文章。似乎以一种非常容易理解的方式总结了这个问题。
There is a theoretical limit: I suggest reading this article on Information theory and the pigeon hole principle. It seems to sum up the issue in a very easy to understand way.
如果您有要压缩的所有电影的固定目录，您只需发送电影的 ID，然后“解压缩”即可使用该索引查找数据。因此，压缩可以是固定大小的 log2(N) 位，其中 N 是电影的数量。
我怀疑实际的下限比这个要高得多。
你说的真的是无损吗？我认为，当今的大多数视频压缩都是有损的。
If you have a fixed catalogue of all the movies you were ever going to compress, you could just send an id for the movie and have the "decompression" lookup up the data with that index. So compression could be to a fixed size of log2(N) bits, where N was the number of movies.
I suspect the practical lower bound is rather higher than this.
Do you really mean lossless? Most of today's video compression is lossy, I thought.
利用信息论的最新发展重新定义限制非常重要。为此，我推荐以下文章，该文章非常详细且清晰。
压缩限制的现代方法
为了定义压缩极限，必须报告该极限有效的假设。
在信息论中，使用了以下 3 个基本假设：
信息由熵函数 H(X) 定义。
编码器和解码器都知道标识源的信息。
考虑源及其同构。这意味着我们可以一次解码一个符号。
第一个极限是最著名的，由香农定义，其中所有 3 个假设均成立。
氨(X)
具有源 X 的 H(X) 熵。
第二极限。我们删除第二个假设，解码器不知道来源。
NH(X)+来源信息
第三个限制，我们去掉第三个假设。在这种情况下，使用了集合塑造理论SST，这是一种新的彻底改变信息论的方法。该理论研究一对一函数 f，将一组字符串转换为一组由更长长度的字符串组成的相同大小的集合。通过这种方法，我们得到以下极限：
N2H(Y)+源信息≈NH(X)
其中f(X)＝Y并且N 2 ＞N。
在实践中，我们获得的压缩增益相当于获得了描述源所需的信息。描述来源所需的信息代表低效率熵编码。
然而，在这种情况下，不可能一次解码一个符号（代码不是瞬时的），但在获得原始消息之前必须对消息进行完整解码。
该领域已取得重要进展。可以将该理论应用于数据压缩的具体案例“集合整形理论在霍夫曼编码中的实际应用”。
另一个有趣的方面是，作者共享了执行集合整形理论中描述的变换的代码和函数。该文件在 Matlab 文件交换上共享： https ://www.mathworks.com/matlabcentral/fileexchange/115590-test-sst-huffman-coding?s_tid=FX_rc1_behav
It is important to redefine the limits with the latest developments regarding information theory. For this purpose, I recommend the following article which is very detailed and clear.
A Modern approach to compression limit
In order to define a compression limit it is essential to report the hypotheses for which the limit is valid.
In information theory, 3 fundamental hypotheses are used which are the following:
the information is defined by the entropy function H(X).
the information that identifies the source is known both by the encoder and by the decoder.
the source and its isomorphisms are considered. It means that we can decode a symbol at a time.
First limit, the most famous, defined by Shannon in which all 3 hypotheses are true.
NH(X)
With H(X) entropy of the source X.
Second limit. we remove the second hypothesis the decoder does not know the source.
NH(X)+source information
Third limit, let's remove the third hypothesis. In this case, the Set Shaping Theory SST is used, a new method that is revolutionizing information theory. This theory studies the one-to-one functions f that transform a set of strings into a set of equal size made up of strings of greater length. With this method, we get the following limit:
N2H(Y)+ source information≈NH(X)
with f(X)=Y and N2>N.
In practice, we obtain a gain in terms of compression equivalent to the information necessary to describe the source is obtained. The information needed to describe the source represents the inefficiency of the entropy coding.
In this case, however, it is not possible to decode a symbol at a time (the code is not instantaneous) but the message must be decoded in full before obtaining the original message.
Important progress has been made in this area. It was possible to apply this theory to a concrete case of data compression "Practical applications of Set Shaping Theory in Huffman coding".
Another interesting aspect is that the authors shared the code and the function that performs the transform described in the set shaping theory. The file is shared on Matlab file exchange: https://www.mathworks.com/matlabcentral/fileexchange/115590-test-sst-huffman-coding?s_tid=FX_rc1_behav