压缩有理论上的限制吗？

Question

想象一下，在接下来的10年里，你可以使用世界上所有的超级计算机。您的任务是尽可能无损地压缩10部全长电影。另一个标准是，一台正常的计算机应该能够在运行时对其进行解压缩，并且不需要花费大量的HD来安装解压缩软件。

我的问题是，你能比目前最好的替代品多压缩多少? 1%，5%，50%？更具体地说:在给定固定字典大小的情况下，压缩是否存在理论上的限制(如果视频压缩也是如此)？

Answer 1

压缩的极限是由源的随机性决定的。欢迎学习information theory！参见data compression。

Answer 2

理论上有一个限制:我建议阅读这篇article on Information theory and the pigeon hole principle。它似乎以一种非常容易理解的方式总结了这个问题。

Answer 3

如果你有一个固定的目录，所有你曾经要压缩的电影，你可以只发送一个id的电影，并有“解压缩”查找该索引的数据。因此，压缩可以是固定大小的log2(N)位，其中N是电影的数量。

我怀疑实际的下限要比这个高得多。

你真的是说无损吗？我想，今天的大多数视频压缩都是有损的。