Здравствуйте, 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
Здравствуйте, 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 >>
Здравствуйте, 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.
Но тем не менее, вопрос о генерации таких последовательностей может оказаться интересным. Выделим его в отдельную задачку.
Здравствуйте, 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 входных файла сожмутся в один и тот же выходной, то есть потери неизбежны.
Здравствуйте, 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, которую невозможно сжать данным алгоритмом. чтд.
