Мне всегда казалось интуитивно очевидным, что невозможно написать архиватор, который сжимает ВСЁ. Но оказалось, что это убеждение разделяют не все . И пришлось мне, некоторое время назад, быстренько доказать следующее:
Для простоты будем рассматривать сжатие последовательностей из 0 и 1. Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные (иначе нельзя однозначно разархивировать).
Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.
Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.
Отсюда, в частности, следует, что если от вас требуют написать архиватор, который сжимет ВСЁ, то лучшим решением будет оставить все как есть .
Здравствуйте, MichaelP, Вы писали:
MP>Отсюда, в частности, следует, что если от вас требуют написать архиватор, который сжимет ВСЁ, то лучшим решением будет оставить все как есть .
Из "все последовательности 0 и 1 длиной меньше или равной N"
следует, что такие последовательности образуют полное множество, непредставимое множеством меньшей мощности, а из
"Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные"
следует, что сжать, в указанном смысле, исходное множество нельзя.
Может кто помнит историю с пари на $5000 на создание архиватора? В журнале Компьтерра описывалась?
Здравствуйте, mrhru, Вы писали:
M>Из "все последовательности 0 и 1 длиной меньше или равной N"
M>следует, что такие последовательности образуют полное множество, непредставимое множеством меньшей мощности, а из
M>"Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные"
M>следует, что сжать, в указанном смысле, исходное множество нельзя.
Я где-нибудь утверждал, что отображать надо на ТО ЖЕ множество?
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, mrhru, Вы писали:
M>>Из "все последовательности 0 и 1 длиной меньше или равной N"
M>>следует, что такие последовательности образуют полное множество, непредставимое множеством меньшей мощности, а из
M>>"Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные"
M>>следует, что сжать, в указанном смысле, исходное множество нельзя.
MP>Я где-нибудь утверждал, что отображать надо на ТО ЖЕ множество?
Здравствуйте, mrhru, Вы писали:
M>Здравствуйте, MichaelP, Вы писали:
MP>>Отсюда, в частности, следует, что если от вас требуют написать архиватор, который сжимет ВСЁ, то лучшим решением будет оставить все как есть .
M>Из "все последовательности 0 и 1 длиной меньше или равной N"
M>следует, что такие последовательности образуют полное множество, непредставимое множеством меньшей мощности, а из
Понятие мощности множества несколько отличается от "суммы длин последовательностей" , но направление мысли правильное.
M>Может кто помнит историю с пари на $5000 на создание архиватора? В журнале Компьтерра описывалась?
Если это то, о чем я думаю — там воспользовались лазейкой в условиях конкурса и загоняли дополнительную информацию в имена и другие атрибуты файлов. В итоге, формально, суммарная длина файлов всегда была меньше исходной.
Здравствуйте, MichaelP, Вы писали:
MP>Для простоты будем рассматривать сжатие последовательностей из 0 и 1. Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные (иначе нельзя однозначно разархивировать). MP>Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.
MP>Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.
Если множество всех последовательностей L<=N отображается само на себя, то суммарная длина очевидно не меняется.
Если некоторые последовательности отображаются из L<=N в L>N, то очевидно в множестве L<=N возникает ровно столько же дыр, куда ничего не отобразилось (число элементов-то не изменилось).
Для каждой пары электрон-дырка суммарная длина получила некоторую положительную прибавку.
M>>Может кто помнит историю с пари на $5000 на создание архиватора? В журнале Компьтерра описывалась?
MP>Если это то, о чем я думаю — там воспользовались лазейкой в условиях конкурса и загоняли дополнительную информацию в имена и другие атрибуты файлов. В итоге, формально, суммарная длина файлов всегда была меньше исходной.
Там была лазейка с возможность разбиения архива на части. При архивировании, исходный файл разбивался по границам байтов с определенным значением, например 0x00. Такие байты просто выбрасывались. В результате длина архива, как сумма его составляющих, получалась короче на ~1/256.
P>Если множество всех последовательностей L<=N отображается само на себя, то суммарная длина очевидно не меняется.
P>Если некоторые последовательности отображаются из L<=N в L>N, то очевидно в множестве L<=N возникает ровно столько же дыр, куда ничего не отобразилось (число элементов-то не изменилось).
P>Для каждой пары электрон-дырка суммарная длина получила некоторую положительную прибавку.
Появился несколько другой вопрос:
Существует ли такая последовательность из 0 и 1 длиной N, такая, что в ней не существует 2 равных непересекающихся подпоследовательностей длиной M? Очевидно, что при M = 1 и длине N > 2 это уже не верно, но гораздо интереснее выяснить максимально возможное M для любого N. Если выяснится, что M неограничено растёт при увеличении N, то можно найти такое N, для которого существует универсальный архиватор действующий просто — находящий последовательности M и заменяющий одну из них информацией о её длине, местоположении и местоположении первой последовательности Если же это не возможно, то значит есть предел для M, чему он тогда равен?
Здравствуйте, DjAndy, Вы писали:
DA>Появился несколько другой вопрос: DA>Существует ли такая последовательность из 0 и 1 длиной N, такая, что в ней не существует 2 равных непересекающихся подпоследовательностей длиной M? Очевидно, что при M = 1 и длине N > 2 это уже не верно, но гораздо интереснее выяснить максимально возможное M для любого N. Если выяснится, что M неограничено растёт при увеличении N, то можно найти такое N, для которого существует универсальный архиватор действующий просто — находящий последовательности M и заменяющий одну из них информацией о её длине, местоположении и местоположении первой последовательности Если же это не возможно, то значит есть предел для M, чему он тогда равен?
MP>Для простоты будем рассматривать сжатие последовательностей из 0 и 1. Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные (иначе нельзя однозначно разархивировать).
MP>Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.
MP>Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.
А теперь, когда доказательство найдено, имхо, более сложный вопрос:
Назовем последовательность сжатой, если в результате отображения ее длина уменьшилась. Соответственно несжатой будем считать ту, у котрой длина увеличилась или осталась той же.
Доказать, что при тех же условиях, что и в предыдущей задаче, количество несжатых последовательностей всегда больше чем сжатых.
Здравствуйте, MichaelP, Вы писали:
MP>Назовем последовательность сжатой, если в результате отображения ее длина уменьшилась. Соответственно несжатой будем считать ту, у котрой длина увеличилась или осталась той же.
MP>Доказать, что при тех же условиях, что и в предыдущей задаче, количество несжатых последовательностей всегда больше чем сжатых.
Множества вложены друг в друга {L<=N-1} + {L=N} = {L<=N}
Если какие-то точки из множества L=N сжались, т.е. отобразились в L<=N-1,
то ровно столько точек в множестве L<=N-1 уже стало занято для перехода точек из этого множества.
Поэтому по крайней мере столько же точек выйдет из множества L<=N-1, т.е. будут несжаты.
Таким образом имеем, что число несжатых последовательностей не меньше числа сжатых.
Но сушествуют последовательности, которые не могут быть сжаты по определению — {0} и {1}.
Поэтому нестрогое неравенство заменяется на строгое.
Здравствуйте, MichaelP, Вы писали:
MP>Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.
MP>Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.
MP>Отсюда, в частности, следует, что если от вас требуют написать архиватор, который сжимет ВСЁ, то лучшим решением будет оставить все как есть .
Пусть априорно известны вероятности подпоследовательностей длины K (например, 8 -- т.е. частоты различных байт-символов), и эти вероятности не равны.
Тогда, как показал Хаффман, элементарно строится код, дающий мат.ожидание СКС <= 1.
В общем, заводя разговоры про сжатие, нужно быть очень аккуратным с вероятностями.
Простая сумма длин всех входных против всех выходных — соответствует мат.ожиданию при равномерном распределении.
...
К>Пусть априорно известны вероятности подпоследовательностей длины K (например, 8 -- т.е. частоты различных байт-символов), и эти вероятности не равны. К>Тогда, как показал Хаффман, элементарно строится код, дающий мат.ожидание СКС <= 1.
К>В общем, заводя разговоры про сжатие, нужно быть очень аккуратным с вероятностями. К>Простая сумма длин всех входных против всех выходных — соответствует мат.ожиданию при равномерном распределении.
Гм...
Творчески развивая эту мысль , приходим к следующему:
Мы знаем, что нам надо архивировать все последовательности длиной меньше или равной N...
Здравствуйте, mrhru, Вы писали:
M>Творчески развивая эту мысль , приходим к следующему:
M>Мы знаем, что нам надо архивировать все последовательности длиной меньше или равной N...
Какая разница, что все? Вероятности-то разные!
Например, из 20кбайтных блоков — 30% это вирусы десятка разновидностей. Их можно кодировать 1 байтом (а благодарный дайлапщик сам уже у себя запустит вирус из локального архива).
Здравствуйте, Кодт, Вы писали:
M>>Творчески развивая эту мысль , приходим к следующему:
M>>Мы знаем, что нам надо архивировать все последовательности длиной меньше или равной N...
К>Какая разница, что все? Вероятности-то разные!
К>Например, из 20кбайтных блоков — 30% это вирусы десятка разновидностей. Их можно кодировать 1 байтом (а благодарный дайлапщик сам уже у себя запустит вирус из локального архива).
Это понятно.
Вопрос был, если я всё правильно напутал, такой: если упаковать все последовательности длиной меньше или равной N, то какова будет общая длина архива. Полагалось, то не меньше суммы длин всех пакуемых последовательностей.
Но, "все последовательности длиной меньше или равной N" однозначно задаются только лишь числом N. Поэтому, будет достаточно в качестве результата архивации и использовать само число N. Всё.
Здравствуйте, Кодт, Вы писали:
К>Пусть априорно известны вероятности подпоследовательностей длины K (например, 8 -- т.е. частоты различных байт-символов), и эти вероятности не равны. К>Тогда, как показал Хаффман, элементарно строится код, дающий мат.ожидание СКС <= 1.
Ссылка на Хафмана здесь не совсем уместна. Например, если возьмем блок длины 1, то Хафманом мы текст никогда не упакуем. Более того, теорему о том, что, при длине сообщения стремящейся к бесконечности, можно длину кода сколь угодно близко приблизить к энтропии сообщения, доказал, если мне не изменяет память, Шеннон. И доказательство очень непростое. Кстати, насколько я помню, один из вариантов доказательства приводит, по сути дела, к идее арифметичиского кодирования.
А в остальном все верно.
К>В общем, заводя разговоры про сжатие, нужно быть очень аккуратным с вероятностями. К>Простая сумма длин всех входных против всех выходных — соответствует мат.ожиданию при равномерном распределении.
Я же возражал не против упаковки, а против упаковки ВСЕГО. То, что вопрос актуален, гворит то, что даже в этой ветке есть попытки
Здравствуйте, Pushkin, Вы писали:
P>Множества вложены друг в друга {L<=N-1} + {L=N} = {L<=N} P>Если какие-то точки из множества L=N сжались, т.е. отобразились в L<=N-1, P>то ровно столько точек в множестве L<=N-1 уже стало занято для перехода точек из этого множества. P>Поэтому по крайней мере столько же точек выйдет из множества L<=N-1, т.е. будут несжаты. P>Таким образом имеем, что число несжатых последовательностей не меньше числа сжатых. P>Но сушествуют последовательности, которые не могут быть сжаты по определению — {0} и {1}. P>Поэтому нестрогое неравенство заменяется на строгое.
У меня самого было аналогичное, но несколько более громоздкое.
И отдельное спасибо за то, что ты один из немногих, кто не отвечал вопросом на вопрос .
. И пришлось мне, некоторое время назад, быстренько доказать следующее:
.
Вот и я также доказал!
Перекуём баги на фичи!
У меня самого было аналогичное, но несколько более громоздкое.
.
