不可能壓縮算法

Question

考慮US Patent #5533051：

給我最好的理解，有什麼專利算法說的是，它可以保證在任何輸入無損一位壓縮。顯然這是完全不可能的（遞歸地應用該算法來達到任何輸入的一位表示）。

我理解這個算法是錯誤的嗎？

Answer 1

你的理解是正確的。所描述的算法將永久循環某些輸入（因爲「輸出文件處於或低於所需大小？」的答案將始終爲「否」）。

查看comp.compression FAQ深入討論了能夠壓縮隨機輸入的任何輸入和壓縮的聲明。

Answer 2

該專利提出了三種編碼方法，以及從一組壓縮例程中選擇最小尺寸壓縮的算法。我假設你在談論第2頁中的算法，該算法旨在從一組例程中選擇最佳結果。

只要「所需的大小」低於能夠壓縮文本的大小，該算法就會遍歷三個例程。如果它不能使用任何例程壓縮到所需大小以下，則它使用「高度隨機數據的例程」。

還有缺陷;它會再次檢查尺寸要求，然後在尺寸高於所需尺寸時重新設置。因此，它會一直循環輸入。我很確定最終的尺寸決定不應該在那裏，最終的例行程序應該是一個倒退。

我找不到專利中的任何聲明，比如您聲明的專利，儘管這裏存在一個會使算法循環的錯誤。