Алгоритм невозможного сжатия - PullRequest
1 голос
/ 22 февраля 2010

Рассмотрим Патент США № 5533051 :

Насколько я понимаю, запатентованный алгоритм говорит о том, что он может гарантировать однобитовое сжатие без потерь на любом входе. Ясно, что это абсолютно невозможно (рекурсивно применять алгоритм для достижения однобитного представления любого входа).

Я правильно понимаю этот алгоритм?

Ответы [ 2 ]

3 голосов
/ 22 февраля 2010

Ваше понимание верно. Описанный алгоритм будет зацикливаться вечно для некоторых входных данных (так как ответ на вопрос «имеет ли выходной файл требуемый размер или меньше?» Всегда будет «нет»).

См. FAQ по comp.compression для подробного обсуждения утверждений о возможности сжатия любого ввода и сжатия произвольного ввода.

2 голосов
/ 22 февраля 2010

В патенте представлены три метода кодирования, а также алгоритм выбора сжатия минимального размера из набора процедур сжатия. Я предполагаю, что вы говорите об алгоритме на листе 2, который предназначен для выбора наилучшего результата из набора процедур.

Алгоритм будет проходить по трем подпрограммам до тех пор, пока «требуемый размер» будет меньше размера, до которого он может сжимать текст. Если он не может сжать ниже требуемого размера с помощью какой-либо из подпрограмм, он использует «подпрограмму для сильно рандомизированных данных».

И есть недостаток; он снова проверяет требование к размеру, а затем сбрасывает, если размер превышает требуемый размер. Следовательно, он будет зацикливаться для некоторых входов. Я вполне уверен, что окончательное решение о размере не должно быть там, и что окончательная рутина должна действовать как запасной вариант.

Я не могу найти ни одного утверждения в патенте, подобного тому, которое вы заявляете, хотя есть ошибка, которая сделает цикл алгоритма.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...