Теория: Алгоритм сжатия, который делает некоторые файлы меньше, но не больше?
Я сталкивался с этим вопросом;
"Алгоритм сжатия без потерь гарантирует, что некоторые файлы будут меньше, а файлов больше не будет.
Это;
а) невозможно
б) возможно, но может работать неопределенное количество времени,
c) Возможно для коэффициента сжатия 2 или меньше,
d) возможно ли для любого коэффициента сжатия?
Я склоняюсь к (а), но не могу дать четкого объяснения, почему. (Я перечислю мысли друга, и я придумала как возможный ответ)
6 ответов
По принципу "голубиных отверстий", имея строку из 10 битов, у вас есть 1024 возможных входа, и вам нужно отобразить до 9 бит или меньше, чтобы было < 1024 выхода.
Это гарантирует, что либо в алгоритме есть коллизии (сжатие с потерями), либо в какой-то момент решено вернуть немодифицированный ввод как вывод.
В последнем случае вы не можете определить, как распаковать произвольную строку битов. (Это может быть неизмененный ввод или сжатый вывод из большей битовой строки).
-> Невозможно.
Просто небольшое уточнение поста Р.Дж. Фальконера...
Вам нужно только, чтобы некоторые файлы становились меньше, поэтому утверждение о том, что строка из 10 битов должна отображаться в 9 или менее битах, не совсем верно. В частности, если бы кто-то предложил такой механизм сжатия, он мог бы отобразить все строки размером 10 бит или меньше в один и тот же выход (то есть преобразование идентичности).
Однако нам говорят, что есть хотя бы один файл, который становится меньше. Не теряя общности, учтите, что начинать с x битов и заканчивать как y битов, где y строго меньше x.
Теперь рассмотрим область "файлов с y битами или меньше", которая имеет 2y + 1-1 битные строки (включая пустую). Чтобы ни один из них не приводил к большему файлу, каждый из них должен отображаться в битовую строку в том же домене, то есть 2 года+ 1-1 сжатых файлов. Однако мы уже знаем, что начальная строка длиной x битов сжимается до одного из этих значений, оставляя только 2y + 1-2 возможных значения.
В этот момент вступает в действие принцип "дырки голубя" - вы явно не можете отобразить 2y + 1-1 входа на 2y + 1-2 выхода без повторения вывода, что нарушает обратимость сжатия.
А) невозможно
Если у вас есть файл, который не может быть сжат в дальнейшем, вам все равно придется добавить информацию о том, был ли он сжат или нет, поэтому в этом случае файл должен будет расти.
Возможный
to make some files smaller and no files larger
если указанный алгоритм сжатия увеличивает размер файла, просто верните исходный файл.
Я знаю, что я немного опоздал, но я нашел это через Google, и кто-то другой мог сделать то же самое, поэтому я отправлю свой ответ: очевидное решение a) impossibleтакже указал Джон Скит (и между прочим, в интернете много доказательств). Я не подвергаю сомнению невозможность сжать случайные данные, просто чтобы быть ясным с самого начала; Я понял теорию, которая стоит за ней, и, если вы спросите меня, я доверяю математике.: D
Но, если нам позволят мыслить со стороны, мы можем определенно воспользоваться тем фактом, что вопрос не является четко определенным, что означает, что он не дает строгого определения "алгоритма сжатия" и свойств, которые он должен иметь (но уменьшить некоторые файлы, не раскрывая никого).
Кроме того, он не накладывает каких-либо условий на файлы, подлежащие сжатию, единственное, что его интересует, - это "сделать некоторые файлы меньше, а файлы больше не будут".
Тем не менее, теперь у нас есть по крайней мере два способа показать, что на самом деле такой алгоритм существует:
Мы можем использовать имя файла для хранения некоторой информации о файле (или даже всего файла, если это позволяет файловая система, уменьшая каждый файл до 0 бит). Можно просто решить оставить нетронутым каждый файл, кроме одного, уменьшив его до 0 бит и переименовав его с заранее определенным именем. Я согласен, что это может считаться мошенничеством, но опять же, в первоначальном вопросе нет никаких ограничений, и этот алгоритм будет эффективно достигать цели (до тех пор, пока никто не переименует файл, поэтому это будет очень плохой выбор дизайна, кроме быть бессмысленным).
Мы можем ограничить количество файлов для сжатия, скажем, по крайней мере, теми
Xбиты длинные Еще раз, тривиальным решением было бы оставить каждый файл без изменений, кроме одного, который мы можем уменьшить, чтобы он соответствовал файлу, меньшему чемXбиты. Теперь у нас есть алгоритм, который, цитируя дословно, делает некоторые файлы меньше, а файлов больше нет; однако он выполняет ограничение на все возможные входные данные (то есть не может обрабатывать все файлы).
Тем, кто утверждает, что это не имеет никакого практического применения, я говорю, что согласен с вами... но, эй, это теория, и это была просто теоретическая диссертация.;)
Очевидно, что если бы я прошел тест и столкнулся с этим вопросом, я бы поставил жирный X на a)и затем просто продолжайте, не думая слишком много об этом.
Тем не менее вполне возможно показать, что, поскольку естественный язык по своей сути неоднозначен и вопрос формально не выражен, каждый из других возможных ответов не обязательно является неправильным: ставить правильные условия и в конечном итоге более четко указывать, что подразумевается под определенными понятиями. мы можем по закону быть в состоянии достичь цели любого из других перечисленных вариантов, совершая какие-то хитрости и заставляя программу достичь желаемого поведения.
е) возможно
... с некоторыми ограничениями.
Недавно я натолкнулся на Shoco, библиотеку сжатия строк для небольших строк. Мне напомнили об этом вопросе при чтении этого заявления:
... самым замечательным свойством shoco является то, что сжатый размер никогда не будет превышать размер вашей входной строки, если это простой ASCII.
Если вы уверены, что входные данные являются простыми ASCII, ваш буфер для вывода должен быть таким же большим, как входная строка