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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > > > Пусть мы распаковываем некие случайные данные неким достаточно слабым биективным компрессором 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 - вероятность появления каждого символа одинакова, и какова здесь длина кода? > Здесь можно (и нужно :) рассматривать условную вероятность символа -- в зависимости от 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!) > > > А что будем делать, если совпадений будет достаточно мало, и их будет невыгодно кодировать? > > так систем счисления ой как много, причем можно и не через одну пропускать, только бы ресурсов хватило... > Тогда тебе прийдется отдельно писать в архив используемую систему счисления... > > А ведь таких случаев будет подавляющее большинство... > > (Доказательство 2^4=4^2 выглядит более убедительно :) ) > Повторяю доказательство в несколько ином виде: > Пусть у нас есть компрессор, позволяющий сжимать и распаковывать без потерь :) произвольные файлы длиной не более N. > Предположим, что такой компрессор сжимает как минимум половину исходных файлов как минимум на 1 бит. > Тогда: > общее количество всех файлов длины не более N бит будет 2^(N+1)-1. Соответственно, наш компрессор будет сжимать не менее 2^N файлов. Общее количество всех файлов длины N-1 (архивов, полученных для сжимаемых файлов) будет 2^N-1. Таким образом, найдется некоторый архив, которому будут соответствовать по крайней мере 2 исходных файла, и однозначно его распаковать не получится. > Мы пришли к противоречию, которое показывает, что по крайней мере одно из исходных утверждений неверно. Следовательно, либо произвольный компрессор сжимает хоть на один бит менне половины исходных файлов длины не более, чем N, либо он не сможет распаковать некоторые файлы без потерь. > Замечу, что и рекурсивные схемы сжатия также попадают под это доказательство. > Если ты принципиально согласен с этим доказательством, то тема исчерпана. > > > > P.S.: А не подскажут ли мне добрые люди, куда бежать в том случае, если я вдруг обнаружу формулу, вокруг которой ведутся все эти дискуссии? (на всякий случай ;D ) > > > К доктору? :) > > Думаешь поймет? (или к доктору фмн?) ;)

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