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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > > Пусть у нас есть некая случайная величина, принимающая значение "1" с вероятностью 4/5 и "0" с вероятностью 1/5. Тогда средняя длина кода, которая потребуется для того, чтобы ее закодировать, зная эту вероятность, будет 4/5*(-log2(4/5))+1/5*(-log2(1/5)) ~= 4/5* 0.322 + 1/5*2.322 ~= 0.7219 бит. > > > > Именно такой будет средняя длина кода в дет. контексте у C. > > > Почему кодировать надо сразу на основании вероятности... непонятно. > > Какими бы ты кодами ни пользовался, ты всегда неявно присваиваешь некоему кодируемому символу или строке определенную вероятность появления в данном месте. > вот именно, если наш декодер выводил вероятность появления 1 (или к) символа, > а кодер должен будет выводить вероятности 2 (или к+1) символа > > > 123123123123123123123 - вероятность появления каждого символа одинакова, и какова здесь длина кода? > > Здесь можно (и нужно :) рассматривать условную вероятность символа -- в зависимости от n предыдущих символов. > > > 111222333111222333 - здесь использовать другой алгоритм :) > > То же контекстоное моделирование неплохо справится и с этой последовательностью. > так это и ясно, только другой пак сделает это лучше. > > > > Если мы оценим эту вероятность в 9/10, > > > > то получим среднюю длину кода в > > > > 4/5*(-log2(9/10))+1/5*(-log2(1/10)) ~= > > > > 0.7859 бит. > > > > Так в данном случае такой MMP-компрессор будет кодировать хуже, чем C. > > > Не в данном случае, а в среднем. А в данном вполне вероятно что лучше. > > Естественно, _некоторые_ исходые файлы после такого преобразования уменьшатся. > может стоит заменить _некоторые_ на _многие_, в конце концов все зависит от алгоритма. > > > > > Рассмотрим 100 символов например в системе с основанием 4. (т.е. 400 бит). Переведем их в систему с основанием 13 так: берем 11 симв.(44 бита) и записываем как 6 симв. (44 бита) в системе с основанием 13. (получим теже 400 бит или 401 (: ) Сжимаем их в новой системе, и преобразуем обратно, но уже 7 симв. из сист с основанием 13 в 13 симв. с основанием 4. Или проще: 32012020130230123010 -=> AAAABBB333 -=> жмем в A(4)B(3)3(3) -=> > > > > > 102330120323________ > > > > Замечательный пример суперсжатия -- из 11 символов получили 13! ;-) > > > Это шутка, или действительно не все понятно в этом примере? ;( > > > (11 симв в системе по основанию 13 много больше чем 13 симв в системе с основанием 4!) > > > > А что будем делать, если совпадений будет достаточно мало, и их будет невыгодно кодировать? > А если их будет предостаточно... > > > так систем счисления ой как много, причем можно и не через одну пропускать, только бы ресурсов хватило... > > Тогда тебе прийдется отдельно писать в архив используемую систему счисления... > вот уж проблемо-та - по 30 бит на систему, коих и будет-то может не более 3-х. Только перебрать ~2^30 (или 2^90)систем и для каждой попробовать сжать - вот проблема. > > > А ведь таких случаев будет подавляющее большинство... > > > (Доказательство 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 бит. Вот и сжали. ;) > > Сразу замечу, что рекурсивное применение такого подхода не будет возможно, поскольку ты собираешься отображать множество "архивов" на множество всех файлов. > Это верно отчасти - рекурсия будет возможна до тех пор, пока стандартные архиваторы смогут находить в достаточном количестве файлов достаточную избыточность. Или по-другому - при слишком коротких цепочках,(типа пара бит :)) архиваторы отдыхают, а наш "супер-пупер компрессор" 'продолжает работать, работать и работать!'. > Кто-то что-то хотел сделать "для поднятия траффика", а тут и так он уже зашкаливает! ;)

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