Автор: Сергей, <zu@valley.ru>
Россия, 20 ноября 2002 года в 22:50:18
В ответ на : Re: еще дополнение (уточнение) от Serge Osnach
в 20 ноября 2002 года в 16:47:31:
> Теперь самое время оценить этот выигрыш :)
Ну что ж, попробую.
Допустим, что удастся добиться сжатия на каждом проходе в среднем на 1% с вероятностью 0.99. Предположим, что хотим сжимать файлы не хуже, чем вдвое - для этого потребуется порядка 70 проходов. Вероятность благоприятных для нас вариантов - 0,99^70 = 0,4948. То есть почти в половине случаев получаем требуемый выигрыш.
Если удастся получить 1% с вероятностью 0,9999 то вероятность благоприятного для нас исхода - 0,993. Дальше - лучше. Вопрос достижений хороших параметров -вопрос технологии. Считаю, что его можно решить (используя сверхмощные компьютеры и соответствующие алгоритмы) но отнюдь не уверен, что удастся мне или еще кому-то в ближайшее время.> А вот и нет. Компрессор не может сжимать хотя бы на 1 бит половину или больше файлов размера не больше, чем N бит при достаточно большом N (а ведь именно об этом случае и идет речь).
> Этот факт прямо следует из того, что количество файлов размером не более N почти вдвое больше количесва файлов размером не более N+1.
> Следовательно, твоя оценка слишком оптимистична :) 2^100 - это число порядка того же, что и вес в граммах Земли. Запомним эту цифру.
Выводить функцию сразу для всего файла - дело безнадежное. Естественно функция для файла представляет из себя набор более простых функций. попробуем экспериментировать на 200-битных числах.
Попробуем написать генератор функций. При этом функции он генерит следущим образом - берет на реальном архиве пару смежных 200 - битных цепочек и выбирает для обоих из них случайную функцию с интересующими нас параметрами для обоих цепочек (функция одна, но аргументы разные, так что каждая из полученных интересующих нас цепочек - разная и меньшей длины, чем исходная). Потом следующую пару и т.д. Составляем коллекцию скажем так из 1 000 000 функций. Потом берем несколько гигов реальных архивов и пропускаем через нее все эти функции. Определяем насколько часто и качественно каждая из них удовлетворяет нас. На основании этих данных составляем коллекцию из нескольких десятков (сотен) тысяч "золотых функций".
Пробуем жать реальные файлы.
В развитие темы гоняем иные коллекции и наборы архивов, обновляем "золотую коллекцию" все более лучшими функциями.
Вот в общем-то как все это мне представлялось.
А теперь вспомним о числе 2^100 и попробуем понять - а сколько на всех компьютерах Земли существует в принципе файлов (и будет создано в обозримом будущем). Это число явно на много десятков порядков меньше (это бы значило, что используя Землю в качестве носителя мы записали бы по 100 бит на каждый ее грамм, хотя конечно плотность записей на носитель гораздо больше, но ведь и их масса по отношению к Земле ничтожна) - а ведь мы-то работаем с 200 - битными цепочками.
Если, число всех возможных файлов на Земле оценить в 2^40 то какой процент это составляет от 2^200 - большинство из которых может и увеличиваться?
И можно ли достичь вероятности попадания скажем в 0,999999 - (мне то до сих пор казалось, что увеличивая число функций и их качество удастся добиться величины больше 1).
Если учесть, что все существующие файлы производит ограниченное число программ
(источников) и есть для всех них определенное число закономерностей, которые на сегодня мы не можем уловить, то получается, что хотя теоретически суперкомпрессор создать нельзя, но на практике он вполне может существовать.
|