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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > Доказательство довольно простое: > > Пусть у нас есть безпотерьный компрессор, сжимающий > > любой файл длины N бит как минимум на 1 > > бит, и по крайней мере не увеличивающий > > в размерах файлы меньшей длины. > > Тогда количество всех файлов длины не более чем N будет 2^(N+1)-1. Количество всех архивов, построенных по файлам длины не более чем N будет 2^N-1. > > Следовательно, найдется по крайней мере один архив, которому будут соответствовать несколько исходных файлов. Как в таком случае определить по архиву, каков был исходный файл? > Вот с эти я уже в корне не соглашусь -все это верно для полного массива файлов определенной длины. Но мы-то говорим об архивах, которые составляют лишь какую-то часть от массива файлов определенной длины. > Если посмотреть на приведенное выше доказательство, то получается, что даже традиционные архиваторы не могут существовать в принципе - ведь они тоже отображают больший файл на меньший... > Архив, если его рассматривать как число - это всегда число с примерным равенством единиц и нулей в нем (на достаточно больших файлах отклонение - десятые доли процента), причем в данном числе отсутствуют очень длинные цепочки, состоящие из одних нулей или единиц (например, к числам-архивам не относится число с равным числом 1 и 0, первую половину из которых составляют только 0, а вторую - только 1). И надо рассматривать не полные отношения файлов размерностью различающихся на единицу, а отношение только файлов-архивов большей длины ко всем файлам на 1 бит меньше. Подсчитать каков процент архивов для цепочек в миллионы бит на практике, не знаю можно ли это сделать, разве что как-то оценочным путем... > Для доказательства моей правоты считаю, что будет достаточно доказать, что в массиве цепочек одинаковой длины мы всегда можем однозначно сопоставить числу-архиву число, которое можно сжать традиционными способами - число-неархив на достаточно коротких цепочках. > Можно самому написать программку - взять цепочки длиной скажем от 10 до 30 бит и подсчитать для каждой длины сколько от общего количества чисел составляют числа с примерным равенством 1 и 0. > Легко убедиться, что уже на длине цепочки в 20 бит из 1048576 чисел 520676 находятся в диапазоне отклонения 1 и 0 в пределах 5% (то есть количество чисел с равенством 1 и 0 или дефицитом-избытком их на один). То есть уже на 20-битной цепочке количество чисел-архивов меньше чем чисел-неархивов. > А посмотрев по тенденции что должно получиться при снижении отклонения с 5% до долей процента на более длинных цепочках и еще учтя, что надо исключить числа с длиными цепочками 1 и 0 подряд, можно утверждать, что для реальных архивов каждому из них можно однозначно сопоставить не то, чтобы по одному, а по несколько чисел-неархивов той же длины. > И теория множеств этому никак не противоречит. > > Кроме того, а что твой компрессор будет делать с файлами, у которых количество "0" значительно больше, чем количество "1"? > Если сможешь найти файл размером в несколько сот кил с отклонением 0 и 1 более 1,5%, который бы не сжался хоть чуть-чуть любым архиватором в максимальной моде - сниму перед тобой шляпу. Я таких не нашел. Более того, если взять архиватор покачественнее, то даже с 1% отклонением (а часто и меньше) все файлы уже жмутся... > Естественно, надо в комплексе поочередно использовать и отображение функцией (если получаем данные с равенством 1 и 0) и традиционные методы сжатия - для всех остальных случаев. Ну это вроде бы как очевидно. > > Если заработал упаковщик, это еще ни о чем не говорит. Нужно, чтобы работал распаковщик. :-) > Это-то как раз и не проблема. Запустил функцию - быстро получил результирующий файл. Проблема - в нахождении функции. Кстати, считаю что на каждый результирующий файл их может быть достаточно большое число (см.выше) и каждая из них - будет создавать одинаковый файл. > Но на практике проверить это утверждение к сожалению без написания паковщика невозможно. Двойка в многомиллионных степенях - неподвластное вычислению число. > > Возьми архив, сделанный любым архиватором, использующим арифметический кодер, и посмотри на статистику в этом случае. > Я иду даже дальше. Статистику считаю на основании файлов, созданных генератором случайных чисел. А потом еще проверяю на реальных архивах. И во всех случаях интересующие меня цепочки встречаются строго с частотой, определяемой теорией вероятности - отклонение минимальное. > Конечно, все это справедливо только для достаточно больших файлов (сотни кил и более). > Хотя суперкомпрессор и перпетум мобиле - в чем то наверное и сходные идеи, но пока я не могу найти доказательства того, что суперкомпрессия невозможна. А если она все-таки возможна, то наверняка математики это уже доказали - в частности встретил упоминание о сверхплотной упаковке единичных шаров, доказанной Личем, наверняка есть что-то еще. И, возвращаясь к нашим баранам - где мне все-таки об этом почитать поподробнее?

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