不可能压缩算法

Question

考虑US Patent #5533051：

给我最好的理解，有什么专利算法说的是，它可以保证在任何输入无损一位压缩。显然这是完全不可能的（递归地应用该算法来达到任何输入的一位表示）。

我理解这个算法是错误的吗？

Answer 1

你的理解是正确的。所描述的算法将永久循环某些输入（因为“输出文件处于或低于所需大小？”的答案将始终为“否”）。

查看comp.compression FAQ深入讨论了能够压缩随机输入的任何输入和压缩的声明。

Answer 2

该专利提出了三种编码方法，以及从一组压缩例程中选择最小尺寸压缩的算法。我假设你在谈论第2页中的算法，该算法旨在从一组例程中选择最佳结果。

只要“所需的大小”低于能够压缩文本的大小，该算法就会遍历三个例程。如果它不能使用任何例程压缩到所需大小以下，则它使用“高度随机数据的例程”。

还有缺陷;它会再次检查尺寸要求，然后在尺寸高于所需尺寸时重新设置。因此，它会一直循环输入。我很确定最终的尺寸决定不应该在那里，最终的例行程序应该是一个倒退。

我找不到专利中的任何声明，比如您声明的专利，尽管这里存在一个会使算法循环的错误。