Re: еще дополнение о суперкомпрессии

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

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 > > Пусть мы распаковываем 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. > Если мы оценим эту вероятность в 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! ;-) > > (Пример является вымышленным, и любое совпадение с реальными данными... ) :] > А что будем делать, если совпадений будет достаточно мало, и их будет невыгодно кодировать? А ведь таких случаев будет подавляющее большинство... > > P.S.: А не подскажут ли мне добрые люди, куда бежать в том случае, если я вдруг обнаружу формулу, вокруг которой ведутся все эти дискуссии? (на всякий случай ;D ) > К доктору? :)

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

[an error occurred while processing this directive]