Рассмотрят US Patent #5533051:невыполнима алгоритм сжатия
Моего лучшего понимания, что запатентованный алгоритм говорит, что он может гарантировать без потерь один-разрядного сжатия на любом входе. Ясно, что это совершенно невозможно (рекурсивно применять алгоритм для достижения однобитового представления любого ввода).
Я понимаю этот алгоритм неправильно?
Ваше понимание неверное. Алгоритм, как описано, будет циклически работать для некоторых входов (так как ответ на «является выходным файлом с размером или ниже требуемого размера?» Всегда будет «нет»).
См. comp.compression FAQ для углубленного обсуждения претензий на возможность сжатия любого ввода и сжатия случайного ввода.
В патенте представлены три метода кодирования, а также алгоритм для выбора сжатия минимального размера из набора подпрограмм сжатия. Я предполагаю, что вы говорите об алгоритме в листе 2, который предназначен для выбора лучшего результата из набора подпрограмм.
Алгоритм будет проходить через три процедуры до тех пор, пока «требуемый размер» будет ниже размера, с которым он может сжимать текст. Если он не может сжать ниже требуемого размера с помощью любой из подпрограмм, он использует «процедуру для высоко рандомизированных данных».
И есть недостаток; он снова проверяет требования к размеру и затем сбрасывается, если размер превышает требуемый размер. Следовательно, он будет зависеть навсегда для некоторых входов. Я уверен, что окончательное решение о размере не должно быть там, и что окончательная процедура должна действовать как резерв.
Я не могу найти никаких претензий в патенте, как тот, который вы заявляете, хотя там есть ошибка, которая сделает цикл алгоритма.
Автор GZip имеет краткий обзор этого патента, который может вас заинтересовать: http://gailly.net/05533051.html – Xiaofu