不幸的是,这样的程序不存在。
要了解为什么会这样,我们需要做一些数学运算。首先,让我们计算一下有多少个长度为 n 的二进制字符串。每个位都可以是 0 或 1,这为我们提供了每个位的两种选择之一。由于每个位和 n 位有两个选择,因此总共有 2 n 个长度为 n 的二进制字符串。
现在,假设我们要构建一个压缩算法,它总是将长度为 n 的位串压缩为长度小于 n 的位串。为了使它起作用,我们需要计算有多少长度小于 n 的不同字符串。嗯,这是由长度为 0 的位串的数量,加上长度为 1 的位串的数量,再加上长度为 2 的位串的数量,等等,一直到 n - 1。这个总数是
2 0 + 2 1 + 2 2 + ... + 2 n - 1
使用一点数学,我们可以得到这个数字等于 2 n - 1。换句话说,长度小于 n 的位串的总数比长度为 n 的位串的数量小一。
但这是一个问题。为了让我们拥有一个始终将长度为 n 的字符串映射到长度最多为 n - 1 的字符串的无损压缩算法,我们必须有某种方法将长度为 n 的每个位串与一些较短的位串相关联,这样就不会长度为 n 的两个比特串与相同的较短比特流相关联。这样,我们可以通过将字符串映射到相关的较短字符串来压缩字符串,我们可以通过反转映射来解压缩它。没有两个长度为 n 的位串映射到同一个较短的字符串的限制是无损的 - 如果两个长度为 n 的位串映射到同一个较短的位串,那么当解压缩字符串时,不会是一种知道我们压缩了两个原始位串中的哪一个的方法。
这是我们遇到问题的地方。由于有 2 n 个长度为 n 的不同位串,并且只有 2 n -1 个较短的位串,因此我们不可能将每个长度为 n 的位串与一些较短的位串配对,而无需将至少两个长度为 n 的位串分配给相同的较短的位串细绳。这意味着无论我们多么努力,无论我们多么聪明,无论我们的压缩算法多么有创意,都有一个严格的数学限制,即我们不能总是让文本变短。
那么这如何映射到您原来的问题呢?好吧,如果我们得到一个长度至少为 10000 的文本字符串并且需要输出一个较短的程序来打印它,那么我们必须有某种方法将 2 10000 个长度为 10000 的字符串中的每一个映射到2 10000 - 1长度小于 10000 的字符串。该映射还有一些其他属性,即我们总是必须生成一个有效的程序,但这在这里无关紧要 - 根本没有足够的短字符串可供使用。结果,你想解决的问题是不可能的。
也就是说,我们也许可以得到一个程序,它可以将除一个长度为 10000 的字符串之外的所有字符串压缩为更短的字符串。事实上,我们可能会找到一种压缩算法来执行此操作,这意味着以 1 - 2 10000的概率可以压缩任何长度为 10000 的字符串。这是一个如此高的概率,如果我们在宇宙的整个生命周期中一直挑选弦,我们几乎肯定永远不会猜到一根坏弦。
为了进一步阅读,信息论中有一个称为Kolmogorov 复杂性的概念,它是生成给定字符串所需的最小程序的长度。一些字符串很容易压缩(例如,abababababababab),而另一些则不是(例如,sdkjhdbvljkhwqe0235089)。存在称为不可压缩字符串的字符串,对于这些字符串不可能压缩到任何更小的空间。这意味着任何打印该字符串的程序必须至少与给定字符串一样长。有关 Kolmogorov 复杂性的良好介绍,您可能需要查看 Michael Sipser 的“计算理论导论,第二版”的第 6 章,其中对一些更酷的结果进行了很好的概述。如需更严格和深入的了解,请考虑阅读“信息论的要素”第 14 章。
希望这可以帮助!