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

Question

Я сталкивался с этим вопросом;

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

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

b) Возможно, но может работать неопределенное время,

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

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

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

Answer 1

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

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

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

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

Answer 2

Просто небольшое уточнение сообщения Р.Дж. Фальконера ...

Вам нужно только, чтобы некоторые файлы становились меньше, поэтому утверждение о том, что строка из 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

возможно

to make some files smaller and no files larger

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

Answer 4

д) Возможно

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

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

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

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

http://ed -von-schleck.github.io / Сохо / # как-это работает

Answer 5

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

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

Кроме того, он не накладывает каких-либо условий на файлы, подлежащие сжатию, единственное, что его интересует, - это "сделать некоторые файлы меньше, а файлов больше нет" .

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

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

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

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

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

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

Answer 6

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

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