Теория: алгоритм сжатия, который делает некоторые файлы меньше, но не больше?

Question

Я наткнулся на этот вопрос;

«Алгоритм сжатия без потерь утверждает, что гарантирует, что некоторые файлы меньше и нет файлов больше.
Это;

а) Невозможно

б) возможно, но может работать на неопределенное количество времени,

в) возможно для коэффициента сжатия 2 или менее,

г) Возможно для какого -либо коэффициента сжатия? "

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

Answer 1

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

Это гарантирует, что либо алгоритм имеет столкновения (сжатие с потерей), либо в какой -то момент предпочитает вернуть немодифицированный вход в качестве вывода.

В последнем случае вы не можете определить, как распаковать произвольную строку битов. (Это может быть немодифицированный вход или сжатый выход из более крупной битовой строки).

-> Невозможно.

Answer 2

Просто небольшое разъяснение сообщения rjfalconer ...

Тебе нужно только немного Файлы становятся меньше, поэтому утверждение о том, что строка из 10 бит должна составить карту до 9 бит или меньше, не совсем правильно. В частности, если кто -то предложил такой механизм сжатия, это мог Карту всех строк 10 бит или меньше до точности выхода (то есть преобразование идентификации).

Однако нам говорят, что есть хотя бы один файл что становится меньше. Без потери общности, учитывайте, что для начала с x битов и в конечном итоге как Y -биты, где y строго меньше x.

Теперь рассмотрим домен «файлов с y битами или меньше», который имеет 2^y+1-1 битные строки (включая пустой). Для того, чтобы никто из них не привел к большему файлу, каждый должен сопоставить на немного строки в одном и том же домене, т.е. 2^y+1-1 сжатые файлы. Тем не менее, мы уже знаем, что начальная строка длина x битов сжимается к одному из этих значений - оставляя только 2^y+1-2 возможные значения.

В это Приходит принцип лунки голубей - вы явно не можете карту 2^y+1-1 входы до 2^y+1-2 выходы без повторения вывода, который нарушает обратимость сжатия.

Answer 3

а) Невозможно

Если у вас есть файл, который не может быть сжат дальше, вам все равно нужно добавить информацию, будь то сжата или нет, поэтому в этом случае файл должен был бы расти.

Answer 4

Я знаю, что я немного опоздал, но я нашел это через Google, и кто -то другой мог сделать то же самое, поэтому я опубликую свой ответ: очевидное решение - это a) impossible, Как хорошо указал Джон Скит (и, кстати, есть много доказательств по всему Интернету). Я не подвергаю сомнению невозможность сжатия случайных данных, просто чтобы быть ясным с самого начала; Я понял теорию, которая лежит за ней, и, если вы спрашиваете меня - я доверяю математике. : D.

Но если нам разрешено Думай в поперечном направлении, мы могли бы определенно воспользоваться тем фактом, что этот вопрос не очень определен, что означает, что он не дает строгого определения «алгоритма сжатия» и о свойствах, которые он должен обладать (но чтобы уменьшить немного Файлы, не расширяя никого).

Кроме того, он не устанавливает условия в файлах для сжатия, единственное, что ему интересно, это «Чтобы сделать несколько файлов меньше и не было файлов больше».

Тем не менее, у нас сейчас есть как минимум два способа показать, что на самом деле это существует такой алгоритм:

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

2. Мы можем ограничить количество файлов, которые будут сжаты, скажем, к тем, которые хотя бы X биты длиной. Еще раз, тривиальное решение будет заключаться в том, чтобы оставить каждый файл нетронутым, но один, чтобы мы могли уменьшить, что соответствует его файлу меньше, чем X биты В настоящее время мы делаем Иметь алгоритм, который, цитируя дословные, делает некоторые файлы меньше и нет файлов больше; Тем не менее, он выполняет ограничение на все свои возможные входы (то есть он не может обрабатывать все файлы).

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

Очевидно, что если бы я сделал тест и столкнулся с этим вопросом, я бы положил смелый x на a), а потом просто продолжайте, не задумываясь об этом.

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

Answer 5

д) возможно

... с некоторыми ограничениями.

Я недавно наткнулся Шоко, библиотека сжатия строк для небольших струн. Мне напомнили об этом вопросе при чтении этого утверждения:

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

Если вы уверены, что входные данные являются простым ASCII, ваш буфер OUT для того, чтобы быть только таким большим, как входная строка

http://ed-von-schleck.github.io/shoco/#how-it-works

Answer 6

возможный

to make some files smaller and no files larger

Если указанный алгоритм сжатия увеличивает файл, просто попросите его вернуть исходный файл.