Здравствуйте, MichaelP, Вы писали:
MP>Для простоты будем рассматривать сжатие последовательностей из 0 и 1. Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные (иначе нельзя однозначно разархивировать). MP>Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.
MP>Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.
Если множество всех последовательностей L<=N отображается само на себя, то суммарная длина очевидно не меняется.
Если некоторые последовательности отображаются из L<=N в L>N, то очевидно в множестве L<=N возникает ровно столько же дыр, куда ничего не отобразилось (число элементов-то не изменилось).
Для каждой пары электрон-дырка суммарная длина получила некоторую положительную прибавку.
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>Мне всегда казалось интуитивно очевидным, что невозможно написать архиватор, который сжимает ВСЁ. Но оказалось, что это убеждение разделяют не все .
Простейшее доказательство невозможности универсального архиватора(вроде тут ещё не было):
Теорема:
Ни одна программа не может сжать без потерь ВСЕ файлы размера >=N для любого N>=0.
Доказательство:
Предположим, что есть программа, сжимающая все файлы длины >=N хотя бы на один бит.
Сожмем ей все файлы длины строго N(всего 2^N файлов). Поскольку все сжатые файлы имеют длину
не больше N-1, всего возможно не более (2^N)-1 файлов: 2^(N-1) файлов размера N-1, 2^(N-2) файлов
размера N-2 и так далее вплоть до одного файла нулевого размера. Так что по крайней мере 2 входных файла сожмутся в один и тот же выходной, то есть потери неизбежны.
Здравствуйте, MichaelP, Вы писали:
MP>Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.
MP>Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.
MP>Отсюда, в частности, следует, что если от вас требуют написать архиватор, который сжимет ВСЁ, то лучшим решением будет оставить все как есть .
Пусть априорно известны вероятности подпоследовательностей длины K (например, 8 -- т.е. частоты различных байт-символов), и эти вероятности не равны.
Тогда, как показал Хаффман, элементарно строится код, дающий мат.ожидание СКС <= 1.
В общем, заводя разговоры про сжатие, нужно быть очень аккуратным с вероятностями.
Простая сумма длин всех входных против всех выходных — соответствует мат.ожиданию при равномерном распределении.
Мне всегда казалось интуитивно очевидным, что невозможно написать архиватор, который сжимает ВСЁ. Но оказалось, что это убеждение разделяют не все . И пришлось мне, некоторое время назад, быстренько доказать следующее:
Для простоты будем рассматривать сжатие последовательностей из 0 и 1. Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные (иначе нельзя однозначно разархивировать).
Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.
Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.
Отсюда, в частности, следует, что если от вас требуют написать архиватор, который сжимет ВСЁ, то лучшим решением будет оставить все как есть .
Здравствуйте, MichaelP, Вы писали:
MP>Мне всегда казалось интуитивно очевидным, что невозможно написать архиватор, который сжимает ВСЁ. Но оказалось, что это убеждение разделяют не все . И пришлось мне, некоторое время назад, быстренько доказать следующее:
Ответим сначала на такой вопрос: Для некоторого заданного алгоритма архивации, существует ли такое N, что он сжимает хотя бы на 1 бит любую последовательность из K > N бит? Если такое N существует, то, очевидно, любую последовательность длины K > N можно сжать до N бит, последовательно применяя алгоритм к результату. Следовательно, для того, чтобы такое N существовало, необходимо, чтобы множество всей информации было как минимум ограничено, что не есть правда Отсюда имеем, для любого алгоритма архивации для любого N, найдётся по-крайней мере одна последовательность длины K > N, которую невозможно сжать данным алгоритмом. чтд.
... << RSDN@Home 1.0 beta 6a | Сейчас пятница, 09:03, слушаю 02 — The Four Horsemen >>
Здравствуйте, 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 на создание архиватора? В журнале Компьтерра описывалась?
Если это то, о чем я думаю — там воспользовались лазейкой в условиях конкурса и загоняли дополнительную информацию в имена и другие атрибуты файлов. В итоге, формально, суммарная длина файлов всегда была меньше исходной.
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, чему он тогда равен?
...
К>Пусть априорно известны вероятности подпоследовательностей длины 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>Поэтому нестрогое неравенство заменяется на строгое.
У меня самого было аналогичное, но несколько более громоздкое.
И отдельное спасибо за то, что ты один из немногих, кто не отвечал вопросом на вопрос .
Здравствуйте, mrhru, Вы писали:
M>Вопрос был, если я всё правильно напутал, такой: если упаковать все последовательности длиной меньше или равной N, то какова будет общая длина архива. Полагалось, то не меньше суммы длин всех пакуемых последовательностей.
M>Но, "все последовательности длиной меньше или равной N" однозначно задаются только лишь числом N. Поэтому, будет достаточно в качестве результата архивации и использовать само число N. Всё.
Для определенности, будем считать каждую N-значную последовательность монолитным блоком. (Мощность множества блоков, очевидно, S = 2^N).
Рассмотрим суперпоследовательность, в которой каждый блок вошел один раз.
Это значит, что частоты P блоков в ней равны (P = 1/S). И, тем самым, каждый отдельный блок несет одинаковую порцию информации, равную I = -log2 P, т.е. N бит.
То есть, кодирование по Хаффману ничего не дает...
А вот теперь сюрприз! Сколько информации находится в суперпоследовательности? Думаете, L = S * N бит? Хренушки.
Рассмотрим множество суперпоследовательностей. Его мощность T — это число перестановок S блоков, то есть (S!).
Будем считать, что все они равновероятны.
Следовательно, количество информации в одной суперпоследовательности равно J = log2 T,
T ~= (S/e)^S, J = S * log2(S/e) = S * log2(2^N/e) = S * (N — log2 e)
то есть ее можно закодировать двоичным числом меньшей разрядности.
Коэффициент расширения составит J/L = 1-(log2 e)/N.
(КР — величина обратная коэффициенту сжатия. Чем меньше 1, тем лучше).
Пример: N=2. Всего существуют 24 перестановки из 4 2-битных блоков. Следовательно, суперпоследовательность можно закодировать ]log2 24[ = 5 битами. Хотя длина ее составляет 8 бит.
А на деле получается, что суперпоследовательность кто-то должен генерировать. И заниматься случайными перестановками для больших значений S невозможно.
Поэтому генератор, скорее всего будет лепить блоки по порядку.
Это значит, что у одной суперпоследовательности вероятность 1, а у остальных — 0.
То есть это вообще 0 бит!!!
Добавим к коду значение N чтобы отличать разные суперпоследовательности. На это уйдет ]log2 N[ бит. Коэффициент расширения составит (log2 N)/(N*2^N) -- что-то стремящееся к нулю.
Ну что, есть еще желание заниматься спекулятивными тестированиями архиваторов?
На самом деле, если в суперпоследовательности каждый блок встречается равное, но большое число K раз, то T будет стремиться к L = K*S*N. Но этого потолка все равно не достигнет
MP>Ссылка на Хафмана здесь не совсем уместна. Например, если возьмем блок длины 1, то Хафманом мы текст никогда не упакуем. Более того, теорему о том, что, при длине сообщения стремящейся к бесконечности, можно длину кода сколь угодно близко приблизить к энтропии сообщения, доказал, если мне не изменяет память, Шеннон. И доказательство очень непростое. Кстати, насколько я помню, один из вариантов доказательства приводит, по сути дела, к идее арифметичиского кодирования.
Поправочка Здесь, конечно, речь шла не о конкретном сообщении, а о мат. ожидании по всем возможным сообщениям.
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, 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>>Поэтому нестрогое неравенство заменяется на строгое.
MP> У меня самого было аналогичное, но несколько более громоздкое.
Гм, по-моему, здесь либо некая путаница в терминах и понятиях, либо в доказательстве Pushkin'а есть излишество. Извиняюсь.
Мы по прежнему говорим о ВСЕХ последовательностях длины <=N?
Тогда НИКАКАЯ последовательность не может быть сжата в указанном смысле, так как результатом получится ДРУГАЯ последовательность из нашего множества ВСЕХ.
Это ИСПОЛЬЗУЕТСЯ в доказательстве — упоминаются последовательности {0} и {1}.
Тогда решение получается очень простое: НИКАКАЯ последовательность не может быть сжата и соответственно количество несжатых (все) последовательностей всегда больше чем сжатых (ноль).
Здравствуйте, mrhru, Вы писали:
M>Мы по прежнему говорим о ВСЕХ последовательностях длины <=N? M>Тогда НИКАКАЯ последовательность не может быть сжата в указанном смысле, так как результатом получится ДРУГАЯ последовательность из нашего множества ВСЕХ.
Исходное множество — множество всех последовательностей с L<=N.
Это множество состоит из M=2^(N+1)-1 элементов М.
Архиватор — любое однозначное и обратимое отображение этого множества в любое подмножество множества вообще ВСЕХ последовательностей (любой длины). Количество элементов в этом подмножестве по определению равно M.
Любой архиватор очевидно переведёт некоторое количество (K) исходных последовательностей в последовательности с меньшей длиной, а некоторое количество (оставшиеся M-K) в последовательности с неменьшей длиной.
Утверждение состояло в том, что для любого архиватора K < M-K
Здравствуйте, Pushkin, Вы писали:
P>Исходное множество — множество всех последовательностей с L<=N. P>Это множество состоит из M=2^(N+1)-1 элементов М.
P>Архиватор — любое однозначное и обратимое отображение этого множества в любое подмножество множества вообще ВСЕХ последовательностей (любой длины). Количество элементов в этом подмножестве по определению равно M.
P>Любой архиватор очевидно переведёт некоторое количество (K) исходных последовательностей в последовательности с меньшей длиной, а некоторое количество (оставшиеся M-K) в последовательности с неменьшей длиной.
P>Утверждение состояло в том, что для любого архиватора K < M-K
Здравствуйте, orangy, Вы писали:
O>Ответим сначала на такой вопрос: Для некоторого заданного алгоритма архивации, существует ли такое N, что он сжимает хотя бы на 1 бит любую последовательность из K > N бит? Если такое N существует, то, очевидно, любую последовательность длины K > N можно сжать до N бит, последовательно применяя алгоритм к результату. Следовательно, для того, чтобы такое N существовало, необходимо, чтобы множество всей информации было как минимум ограничено, что не есть правда Отсюда имеем, для любого алгоритма архивации для любого N, найдётся по-крайней мере одна последовательность длины K > N, которую невозможно сжать данным алгоритмом. чтд.
Все правильно. Но можно доказать и более сильные утверждения. Что и было сделано в этой ветке.
Здравствуйте, DjAndy, Вы писали:
DA>M = log2(N)
DA>Конечно логично, тогда информация о местоположении последовательности будет занимать как раз M бит. Но откуда следует эта формула?
Прошу прощения. Эта формула — ответ на другой вопрос, а именно: — какова максимальная длина N последовательности, в которой любая подпоследовательность длиной М встречается ровно один раз?
И ответ: N = 2^M.
А вот на исходный вопрос:
"Существует ли такая последовательность из 0 и 1 длиной N, такая, что в ней не существует 2 равных непересекающихся подпоследовательностей длиной M? Очевидно, что при M = 1 и длине N > 2 это уже не верно, но гораздо интереснее выяснить максимально возможное M для любого N."
ответ гораздо проще: максимально возможное M для любого N — это когда M = N.
Но тем не менее, вопрос о генерации таких последовательностей может оказаться интересным. Выделим его в отдельную задачку.
Здравствуйте, White Eagle, Вы писали:
WE>Простейшее доказательство невозможности универсального архиватора(вроде тут ещё не было): WE>Теорема: WE>Ни одна программа не может сжать без потерь ВСЕ файлы размера >=N для любого N>=0. WE>Доказательство: WE>Предположим, что есть программа, сжимающая все файлы длины >=N хотя бы на один бит. WE>Сожмем ей все файлы длины строго N(всего 2^N файлов). Поскольку все сжатые файлы имеют длину WE>не больше N-1, всего возможно не более (2^N)-1 файлов: 2^(N-1) файлов размера N-1, 2^(N-2) файлов WE>размера N-2 и так далее вплоть до одного файла нулевого размера. Так что по крайней мере 2 входных файла сожмутся в один и тот же выходной, то есть потери неизбежны.
Доказательство достаточно известно, но, в свое время, оно меня не устроило, т.к. на самом деле оставляет место для следующих возражений:
Ну и что, что два файла не сжимаются. Зато я могу сжать
1. "в среднем" по всем файлам
2. большинство файлов.
Наверняка я был не превым, но, в свое время, я для себя доказал несправедливость этих утверждений, а сейчас "попросил" доказать их в качестве задачек. С чем отлично и справился Pushkin.
суммарная длина получила некоторую положительную прибавку.
. 
Перекуём баги на фичи!
Отсюда имеем, для любого алгоритма архивации для любого N, найдётся по-крайней мере одна последовательность длины K > N, которую невозможно сжать данным алгоритмом. чтд.
Вот и я также доказал!
У меня самого было аналогичное, но несколько более громоздкое.
Здесь, конечно, речь шла не о конкретном сообщении, а о мат. ожидании по всем возможным сообщениям.
