Фиксированная точка на широко используемом в наши дни алгоритме сжатия - PullRequest
Новая
       4

Фиксированная точка на широко используемом в наши дни алгоритме сжатия

6 голосов
/ 20 августа 2009

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

Чтобы объяснить, давайте назовем C : byte[] -> byte[] функцию, которая представляет алгоритм сжатия. Я хочу знать, существует ли (и что это такое, если это возможно в разумные сроки) файл f такой, что

C(f) = f

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

Знаете ли вы о таком явлении?

Ответы [ 2 ]

4 голосов
/ 20 августа 2009

Да! Это вариант проблемы quine .

  1. Пример, который использует gzip : http://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

  2. Пример, который использует zip / unzip : http://www.steike.com/code/useless/zip-file-quine/

3 голосов
/ 20 августа 2009

Предупреждение: скорее педантичный ответ.

Во многих случаях D (f) = f (D определяется как декомпрессия). Однако сжатие не так точно определено. Для большинства алгоритмов сжатия разные реализации алгоритма сжатия будут давать разные выходные файлы (разных размеров). Рассмотрим две программы, 1 и 2. Для полной совместимости необходимо, чтобы D1 (F) равнялась D2 (F) для всех действительных F. Аналогично, необходимо, чтобы D2 (C2 (f)) == D2 (C1 ( F)) == D1 (C1 (F)) == D1 (C2 (F)) для всех действительных F. Однако совершенно необязательно, чтобы C1 (F) == C2 (F), а это на самом деле редко дело.

Таким образом, вы вряд ли, если вы фактически сожмете такие кавычки, в конечном итоге получите один и тот же файл, если только вы не используете для этого ту же программу, которая использовалась для его генерации (что маловероятно, поскольку такие квази обычно ручной работы, C (F) даже не тестировался).

Хотя возможно (на самом деле, тривиально!) Создать программу, для которой C (F) == F для некоторого F, большинство людей вместо этого указывают в виде кавычек на более четко определенный случай, когда D (F) == F (поскольку D1 (F) == D2 (F) для всех действительных, совместимых декомпрессий формата F, при условии, что F допустимо).

Итак, есть вероятные случаи, когда C (F) == F, но, как правило, это неправильный вопрос, и вместо этого вам следует задавать случаи, когда D (F) == F ... какие другие люди, которые ответили на вопрос предоставили.

...