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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > Доказательство довольно простое: > > > Пусть у нас есть безпотерьный компрессор, сжимающий > > > любой файл длины N бит как минимум на 1 > > > бит, и по крайней мере не увеличивающий > > > в размерах файлы меньшей длины. > > > Тогда количество всех файлов длины не более чем N будет 2^(N+1)-1. Количество всех архивов, построенных по файлам длины не более чем N будет 2^N-1. > > > Следовательно, найдется по крайней мере один архив, которому будут соответствовать несколько исходных файлов. Как в таком случае определить по архиву, каков был исходный файл? > > Вот с эти я уже в корне не соглашусь -все это верно для полного массива файлов определенной длины. Но мы-то говорим об архивах, которые составляют лишь какую-то часть от массива файлов определенной длины. > Тогда скорее о малоизбыточных файлах, а не об архивах... > > Если посмотреть на приведенное выше доказательство, то получается, что даже традиционные архиваторы не могут существовать в принципе - ведь они тоже отображают больший файл на меньший... > Традиционные архиваторы ориентированы на "реальные" файлы и реально встречающиеся виды избыточности. Файлы, не имеющие такой избыточности, которую могут эффективно устранять традиционные архиваторы, соответственно ими не сжимаются. > > Архив, если его рассматривать как число - это всегда число с примерным равенством единиц и нулей в нем (на достаточно больших файлах отклонение - десятые доли процента), причем в данном числе отсутствуют очень длинные цепочки, состоящие из одних нулей или единиц > Это неверно. Тем самым ты > предполагаешь, что архиватор ни для какого входного файла не будет строить архивы, содержащие длинные цепочки "0" и "1", и то, что количество "0" и "1" в архиве примерно равно. Такое утверждение несколько не соответствует реальности. Оно верно для большинства случаев, но далеко не всегда. > Возьмем .xls из Canterbury Corpus. > CntC_xls.arj -- заметна явная регулярность в архиве, хотя разница между количеством "0" и "1" около 2% > CntC_xls.zip -- регулярности меньше, diff(0,1) ~= 10% (!!!) > Остальные арихиваторы оказались более-менее "чистыми". Хотя Compressia первые 200-300 байт архива забивает таким, что в твоей терминологии на архив совсем не похоже. Bicom тоже любит оставлять в архиве множество регулярностей. > Как отнесется к таким данным твой "дожиматель"? > (например, к числам-архивам не относится число с равным числом 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%, который бы не сжался хоть чуть-чуть любым архиватором в максимальной моде - сниму перед тобой шляпу. > Берем book1 из Calgary Corpus и жмем его 7zip -tZIP -mx. > Я таких не нашел. Более того, если взять архиватор покачественнее, то даже с 1% отклонением (а часто и меньше) все файлы уже жмутся... > Такие файлы могут и не жаться сложными моделями, которые ориентированы на совсем другие виды избыточности. > > Естественно, надо в комплексе поочередно использовать и отображение функцией (если получаем данные с равенством 1 и 0) и традиционные методы сжатия - для всех остальных случаев. Ну это вроде бы как очевидно. > [skip] > > > Возьми архив, сделанный любым архиватором, использующим арифметический кодер, и посмотри на статистику в этом случае. > > Я иду даже дальше. Статистику считаю на основании файлов, созданных генератором случайных чисел. > А какой имено генератор? > > А потом еще проверяю на реальных архивах. И во всех случаях интересующие меня цепочки встречаются строго с частотой, определяемой теорией вероятности - отклонение минимальное. > > Конечно, все это справедливо только для достаточно больших файлов (сотни кил и более). > > Хотя суперкомпрессор и перпетум мобиле - в чем то наверное и сходные идеи, но пока я не могу найти доказательства того, что суперкомпрессия невозможна. А если она все-таки возможна, то наверняка математики это уже доказали - в частности встретил упоминание о сверхплотной упаковке единичных шаров, доказанной Личем, наверняка есть что-то еще. И, возвращаясь к нашим баранам - где мне все-таки об этом почитать поподробнее? > news:comp.compression > Там постоянно обсуждают нечто подобное.

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