Доказательство невозможности суперкомпрессии


Сайт о сжатии >> Форум #Компрессор# >> [Ответить] [Ответы]

Автор: Serge Osnach, <ench@netcity.ru>
Kiev, Ukraine, 25 ноября 2002 года в 16:08:44

В ответ на : Re: суперкомпрессия от Алексей в 25 ноября 2002 года в 15:35:57:


> > > > То ли еще будет... Тема-то популярная :)
> > > :-)
> > Тебе-то смешно, а comp.compression читать невозможно.
> А где енто?
Смотри на http://groups.google.com

> > > > > Имеет ли смысл перекинуть всю эту
> > > > > занимательную и поучительную переписку в
> > > > > ru.compress в целях поднятия трафика?
> > > > Всю-то зачем?
> > > "...в целях поднятия трафика"
> > FAQ уже пора писать на тему суперсжатия...

> А может кто-нибудь соизволит доказать что это вообще невозможно? Сколько бы людей понапрасну не мучалось...

Пусть у нас есть безпотерьный компрессор, сжимающий
любой файл длины N бит как минимум на 1
бит, и по крайней мере не увеличивающий
в размерах файлы меньшей длины.
Тогда количество всех файлов длины не более чем N будет 2^(N+1)-1. Количество всех архивов, построенных по файлам длины не более чем N будет 2^N-1.
Следовательно, найдется по крайней мере один архив, которому будут соответствовать несколько исходных файлов. Как в таком случае определить по архиву, каков был исходный файл?

Ответы:



Ответить на это сообщение

Тема:

Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.