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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > > Почему кодировать надо сразу на основании вероятности... непонятно. > > > Какими бы ты кодами ни пользовался, ты всегда неявно присваиваешь некоему кодируемому символу или строке определенную вероятность появления в данном месте. > > вот именно, если наш декодер выводил вероятность появления 1 (или к) символа, > > а кодер должен будет выводить вероятности 2 (или к+1) символа > > > > > 123123123123123123123 - вероятность появления каждого символа одинакова, и какова здесь длина кода? > > > Здесь можно (и нужно :) рассматривать условную вероятность символа -- в зависимости от n предыдущих символов. > > > > 111222333111222333 - здесь использовать другой алгоритм :) > > > То же контекстоное моделирование неплохо справится и с этой последовательностью. > > так это и ясно, только другой пак сделает это лучше. > Это уже будет специализированный компрессор. > > > > > Если мы оценим эту вероятность в 9/10, > > > > > то получим среднюю длину кода в > > > > > 4/5*(-log2(9/10))+1/5*(-log2(1/10)) ~= > > > > > 0.7859 бит. > > > > > Так в данном случае такой MMP-компрессор будет кодировать хуже, чем C. > > > > Не в данном случае, а в среднем. А в данном вполне вероятно что лучше. > > > Естественно, _некоторые_ исходые файлы после такого преобразования уменьшатся. > > может стоит заменить _некоторые_ на _многие_, в конце концов все зависит от алгоритма. > Проведи эксперименты, и сам все увидишь. > Возьми генератор случайных чисел, сгенерируй файл на 1Mb, припиши к нему заголовок .zip, распакуй (хотя, чтобы не мучаться, лучше сразу распакуй bicom'ом), и попробуй сжать полученные данные чем-нибудь вроде PPMonstr. > > > > (11 симв в системе по основанию 13 много больше чем 13 симв в системе с основанием 4!) > > > > > А что будем делать, если совпадений будет достаточно мало, и их будет невыгодно кодировать? > > А если их будет предостаточно... > Отчего ты делаешь вывод, что в некое случайном числе, записанном в 13-ричной системе должно быть большое количество повторов? Если мы возьмем наугад некоторую k-ю цифру в такой записи, то вероятность того, что она совпадет с k+1 будет 1/13. > > > > так систем счисления ой как много, причем можно и не через одну пропускать, только бы ресурсов хватило... > > > Тогда тебе прийдется отдельно писать в архив используемую систему счисления... > > вот уж проблемо-та - по 30 бит на систему, коих и будет-то может не более 3-х. Только перебрать ~2^30 (или 2^90)систем и для каждой попробовать сжать - вот проблема. > Переберем все 2^30 систем, но вот беда -- ни в одной из систем больше 20 бит выигрыша не получили. Что поделать, бывает... > > > > А ведь таких случаев будет подавляющее большинство... > > > > (Доказательство 2^4=4^2 выглядит более убедительно :) ) > > > Повторяю доказательство в несколько ином виде: > > > Пусть у нас есть компрессор, позволяющий сжимать и распаковывать без потерь :) произвольные файлы длиной не более N. > > > Предположим, что такой компрессор сжимает как минимум половину исходных файлов как минимум на 1 бит. > > > Тогда: > > > общее количество всех файлов длины не более N бит будет 2^(N+1)-1. Соответственно, наш компрессор будет сжимать не менее 2^N файлов. Общее количество всех файлов длины N-1 (архивов, полученных для сжимаемых файлов) будет 2^N-1. Таким образом, найдется некоторый архив, которому будут соответствовать по крайней мере 2 исходных файла, и однозначно его распаковать не получится. > > эти два исходных файла будут соответствовать одному архиву. Теперь положим, что один из этих файлов является полностью состоящим из нулей. А зачем его вообще сжимать? (а если добавить и одни единицы, получается что один число-архив еще и не используеться!) > Ты считаешь, что не встречаются файлы, состоящие из одних нулей? > > > Мы пришли к противоречию, которое показывает, что по крайней мере одно из исходных утверждений неверно. Следовательно, либо произвольный компрессор сжимает хоть на один бит менне половины исходных файлов длины не более, чем N, либо он не сможет распаковать некоторые файлы без потерь. > > > Замечу, что и рекурсивные схемы сжатия также попадают под это доказательство. > > > Если ты принципиально согласен с этим доказательством, то тема исчерпана. > > Как же тут можно согласиться. > > Мне все больше и больше начинает нравиться эпиграф этого форума! > > Математику придумали человеки, а людям свойственно ошибаться... . (Это так, размышления.) :) > > Теперь о доказательстве: > > (Из предыдущих реплик:) > > > > Легко убедиться, что уже на длине цепочки в 20 бит из 1048576 чисел 520676 находятся в диапазоне отклонения 1 и 0 в пределах 5% (то есть количество чисел с равенством 1 и 0 или дефицитом-избытком их на один). То есть уже на 20-битной цепочке количество чисел-архивов меньше чем чисел-неархивов. > > из этого числа (520676 - верю на слово) следует еще выкинуть и комбинации, типа - четверть 0, четверть 1, а далее все возможные комбинации оставшихся 0 и 1. а именно выкинуть все комбинации, которые умнутся "стандартными" упаковщиками как минимум на пару бит. В итоге останется всего 2^18 цепочек, которые-то нам и надо ужать, поскольку обычными способами они не мнуться. А и не надо, мы их можем просто отобразить в цепочку из 18 бит, прибавить к архиву 1 бит, который покажет чем мы сжимали - "супер" или обычным упаковщиком. В итоге получили - 19 вместо 20 бит. Вот и сжали. ;) > Откуда получена цифра 2^18 цепочек? Навскидку, или все-таки подсчетом? > Итак, некоторый исходный файл твой "супер"-компрессор может закодировать двумя различными способами. > Это означает, что количество всех возможных архивов будет _больше_, чем число всех возможных исходных файлов, а значит, по крайней мере 1 исходный файл увеличится в размерах. > Еще раз посмотри на доказательство невозможности суперсжатия, и скажи, где же ошибка -- в твоих рассуждениях или моих? > > > Сразу замечу, что рекурсивное применение такого подхода не будет возможно, поскольку ты собираешься отображать множество "архивов" на множество всех файлов. > > Это верно отчасти - рекурсия будет возможна до тех пор, пока стандартные архиваторы смогут находить в достаточном количестве файлов достаточную избыточность. Или по-другому - при слишком коротких цепочках,(типа пара бит :)) архиваторы отдыхают, а наш "супер-пупер компрессор" 'продолжает работать, работать и работать!'. > Ты только что предлагал сделать компрессор, работающий только для "архивов", то есть отображающий множество всех "архивов" на множество всех теоретически возможных файлов. > Скажи, каким образом этот компрессор сможет сжимать рекурсивно? > Или ты считаешь, что на выходе компрессора всегда будет файл, попадающий под твое определение "архива"? > > Кто-то что-то хотел сделать "для поднятия траффика", а тут и так он уже зашкаливает! ;) > Вот тебе простенькая задача на суперсжатие: упакуй произвольное число от 0 до 260 в 1 байт.

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