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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > Многоуважаемый Serge Osnach, давайте ка продолжим нашу дискуссию, пожалуй, с почти чистого листа. ;) > > > > Пусть мы распаковываем некие случайные данные неким достаточно слабым биективным компрессором C. > > > ok. > > > > Обозначим результат распаковки им случайных данных как C(-1)(random) > > > тоже ясно > > > >Предположим для определенности, что этот компрессор -- PPM order-1, Escape method A. > > > это мне мало о чем говорит, но я согласен. > > Посмотри на > > http://compression.graphicon.ru/book/ > > и > > http://compression.graphicon.ru/download/articles/ppm/smirnov_2000_ppm_faq.html > thanks ;) > > > Пусть мы распаковываем 100-й символ, и контекст 1-го порядка, соотвествующий 99-му символу был просмотрен 4 раза, и всегда там встречался пробел. Тогда с вероятностью > > > 4/5 этот декомпрессор 100-м символом выдаст пробел. > > > тоже верно. > > > Естественно, что наиболее оптимально этот символ закодирует компрессор, который в детерминированном контексте, где некий символ встречался 4 раза присвоит этому символу вероятность 4/5. > > > Естественно, если это компрессор того же типа как PPM, - для него все так и будет, в этом я не сомневаюсь. Но если это будет компрессор типа MMP order-1/3, Escape method зю, который будет рассматривать этот символ не только в детерминированном контексте, где некий символ встречался 4 раза, но и еще в других контекстах, (а не только по пред. совпадениям) скорректирует свой результат, например в сторону вероятности 9/10, и в итоге окажеться прав. > > Он окажется сильно неправ в 1-4/5 (то есть в 1/5) случаев. > > Пусть у нас есть некая случайная величина, принимающая значение "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. > Почему кодировать надо сразу на основании вероятности... непонятно. > 123123123123123123123 - вероятность появления каждого символа одинакова, и какова здесь длина кода? > 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!) > > А что будем делать, если совпадений будет достаточно мало, и их будет невыгодно кодировать? > так систем счисления ой как много, причем можно и не через одну пропускать, только бы ресурсов хватило... > А ведь таких случаев будет подавляющее большинство... > (Доказательство 2^4=4^2 выглядит более убедительно :) ) > > > P.S.: А не подскажут ли мне добрые люди, куда бежать в том случае, если я вдруг обнаружу формулу, вокруг которой ведутся все эти дискуссии? (на всякий случай ;D ) > > К доктору? :) > Думаешь поймет? (или к доктору фмн?) ;)

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