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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > > > Какими бы ты кодами ни пользовался, ты всегда неявно присваиваешь некоему кодируемому символу или строке определенную вероятность появления в данном месте. > > вот именно, если наш декодер выводил вероятность появления одного (или к) символа, > > а кодер должен будет выводить вероятности двух (или к+1) символов > > > > > > > > > 123123123123123123123 - вероятность появления каждого символа одинакова, и какова здесь длина кода? > > > > > Здесь можно (и нужно :) рассматривать условную вероятность символа -- в зависимости от n предыдущих символов. > > > > > > 111222333111222333 - здесь использовать другой алгоритм :) > > > > > То же контекстоное моделирование неплохо справится и с этой последовательностью. > > > > так это и ясно, только другой пак сделает это лучше. > > > Это уже будет специализированный компрессор. > > Что значит специализированный? Это компрессор, работающий по другому алгоритму. > ...который хорошо работает тольков специфических случаях. > > > > > Естественно, _некоторые_ исходые файлы после такого преобразования уменьшатся. > > > > может стоит заменить _некоторые_ на _многие_, в конце концов все зависит от алгоритма. > > > Проведи эксперименты, и сам все увидишь. > > Сначала нужно придумать алгоритмы. :) > Да, это серьезная проблема. > > > Возьми генератор случайных чисел, сгенерируй файл на 1Mb, припиши к нему заголовок .zip, распакуй (хотя, чтобы не мучаться, лучше сразу распакуй bicom'ом), и попробуй сжать полученные данные чем-нибудь вроде PPMonstr. > > Соглашусь, что именно эта парочка мало что даст. > Предложи другую. Только распаковщик должен быть биективным. > Эксперименты показали, что в подавляющем большинстве случаев наблюдается увеличение размера. Помнится, я по разнице размеров пережатых файлов хотел оценивать степень схожести моделей разных компрессоров. > > > > > > (11 симв в системе по основанию 13 много больше чем 13 симв в системе с основанием 4!) > > > > > > > А что будем делать, если совпадений будет достаточно мало, и их будет невыгодно кодировать? > > > > А если их будет предостаточно... > > > Отчего ты делаешь вывод, что в некое случайном числе, записанном в 13-ричной системе должно быть большое количество повторов? Если мы возьмем наугад некоторую k-ю цифру в такой записи, то вероятность того, что она совпадет с k+1 будет 1/13. > > На основании этого нельзя делать вывод о том, что взяв в другой системе счисления t, некоторую цифру n, вероятность ее совпадения со следующей будет 1/t. И почему повторов должно быть большое количество, достаточно и среднего. ;) > Среднего как раз недостаточно. Какая, собственно, разница -- кодировать определенную цифру с вероятностью 1/t, или повтор с той же вероятностью? > > > > > Тогда тебе прийдется отдельно писать в архив используемую систему счисления... > > > > вот уж проблемо-та - по 30 бит на систему, коих и будет-то может не более 3-х. Только перебрать ~2^30 (или 2^90)систем и для каждой попробовать сжать - вот проблема. > > > Переберем все 2^30 систем, но вот беда -- ни в одной из систем больше 20 бит выигрыша не получили. Что поделать, бывает... > > Этот вывод сделан на основании опыта, или каких-то рассуждений? > В самом лучшем случае на 20 бит мы можем сжать 1/2^20 файлов. Это при том, что размер несжимаемых файлов будет стремится к бесконечности. > Пусть у нас 2^20 систем счисления, тогда вероятность того, что мы по крайней мере не увеличим файл будет (1-1/2^20)^(2^20) ~= 1/e. > > > > > > А ведь таких случаев будет подавляющее большинство... > > > > > > (Доказательство 2^4=4^2 выглядит более убедительно :) ) > > > > > Повторяю доказательство в несколько ином виде: > > > > > Пусть у нас есть компрессор, позволяющий сжимать и распаковывать без потерь :) произвольные файлы длиной не более N. > > > > > Предположим, что такой компрессор сжимает как минимум половину исходных файлов как минимум на 1 бит. > > > > > Тогда: > > > > > общее количество всех файлов длины не более N бит будет 2^(N+1)-1. Соответственно, наш компрессор будет сжимать не менее 2^N файлов. Общее количество всех файлов длины N-1 (архивов, полученных для сжимаемых файлов) будет 2^N-1. Таким образом, найдется некоторый архив, которому будут соответствовать по крайней мере 2 исходных файла, и однозначно его распаковать не получится. > > > > эти два исходных файла будут соответствовать одному архиву. Теперь положим, что один из этих файлов является полностью состоящим из нулей. А зачем его вообще сжимать? (а если добавить и одни единицы, получается что один число-архив еще и не используеться!) > > > Ты считаешь, что не встречаются файлы, состоящие из одних нулей? > > Если смотреть с точки зрения математики, то таких файлов бесконечно. Но тогда с этой точки зрения компрессоры не могут существовать вообще. Но они же работают для большинства файлов. Почему, ты сам писал. Потому что они ориентированы на реальные файлы. И здесь тоже - зачем нам жать файл из 1000 нулей? С ним и обычный PPM справиться хорошо. > > > > > Мы пришли к противоречию, которое показывает, что по крайней мере одно из исходных утверждений неверно. Следовательно, либо произвольный компрессор сжимает хоть на один бит менне половины исходных файлов длины не более, чем N, либо он не сможет распаковать некоторые файлы без потерь. > > > > > Замечу, что и рекурсивные схемы сжатия также попадают под это доказательство. > > > > > Если ты принципиально согласен с этим доказательством, то тема исчерпана. > > > > Как же тут можно согласиться. > > > > Мне все больше и больше начинает нравиться эпиграф этого форума! > > > > Математику придумали человеки, а людям свойственно ошибаться... . (Это так, размышления.) :) > > > > Теперь о доказательстве: > > > > (Из предыдущих реплик:) > > > > > > Легко убедиться, что уже на длине цепочки в 20 бит из 1048576 чисел 520676 находятся в диапазоне отклонения 1 и 0 в пределах 5% (то есть количество чисел с равенством 1 и 0 или дефицитом-избытком их на один). То есть уже на 20-битной цепочке количество чисел-архивов меньше чем чисел-неархивов. > > > > из этого числа (520676 - верю на слово) следует еще выкинуть и комбинации, типа - четверть 0, четверть 1, а далее все возможные комбинации оставшихся 0 и 1. а именно выкинуть все комбинации, которые умнутся "стандартными" упаковщиками как минимум на пару бит. В итоге останется всего 2^18 цепочек, которые-то нам и надо ужать, поскольку обычными способами они не мнуться. А и не надо, мы их можем просто отобразить в цепочку из 18 бит, прибавить к архиву 1 бит, который покажет чем мы сжимали - "супер" или обычным упаковщиком. В итоге получили - 19 вместо 20 бит. Вот и сжали. ;) > > > Откуда получена цифра 2^18 цепочек? > > > Навскидку, или все-таки подсчетом? > > Видишь ли, для меня проблематично пробовать упаковать 2^18 комбинаций файлов обычным паком, к тому же они и не сожмут 18 бит :), а если смотреть на цепочку из 2000 бит, и прикинуть что мы будем упаковывать 1е+1000 вариантов в сек, то нам потребуется ~1e+500 сек. Боюсь я столько не проживу. :( > Да уж... > > > Итак, некоторый исходный файл твой "супер"-компрессор может закодировать двумя различными способами. > > Если не будем учитывать еще и файл, состоящий из одних единиц, то да. > > > Это означает, что количество всех возможных архивов будет _больше_, чем число всех возможных исходных файлов, а значит, по крайней мере 1 исходный файл увеличится в размерах. > > Как же так. Берем N=5, имеем 2^5 файлов, Выкидываем первую и последнюю комбинацию, получаем 30 файлов. А сумма 2^0+2^1+2^2+2^3+2^4 = 31. Все упакованные файлы меньше размером, чем исходные. > А как ты будешь сжимать файлы длиной N1 > Еще раз посмотри на доказательство невозможности суперсжатия, и скажи, где же ошибка -- в твоих рассуждениях или моих? > > В моих вроде все верно. > Тогда, стало быть, ошибка в моем доказательстве? Тогда найди ее и скажи, где именно. > Опровержением будет считаться работающий (распаковывающий) .exe "суперкомпрессора". Правила тестирования просты -- я беру файл в 1Mb, сжимаю, несу архив и декомпрессор на "чистую" машину и распаковываю. > На дальнейшие мессаги без опровержения доказательства я не вижу смысла отвечать. Опровергать частные схемы "суперкомпресии" мне уже несколько надоело. > > > > > Сразу замечу, что рекурсивное применение такого подхода не будет возможно, поскольку ты собираешься отображать множество "архивов" на множество всех файлов. > > > > Это верно отчасти - рекурсия будет возможна до тех пор, пока стандартные архиваторы смогут находить в достаточном количестве файлов достаточную избыточность. Или по-другому - при слишком коротких цепочках,(типа пара бит :)) архиваторы отдыхают, а наш "супер-пупер компрессор" 'продолжает работать, работать и работать!'. > > > Ты только что предлагал сделать компрессор, работающий только для "архивов", то есть отображающий множество всех "архивов" на множество всех теоретически возможных файлов. > > На множество всех реальных файлов, "теоретические" файлы нам не нужны! ;) > > > > > Скажи, каким образом этот компрессор сможет сжимать рекурсивно? > > Всему свое время, не нужно торопить события, а то наша переписка слишком быстро закончится. (Может на этой неделе :) > > > Или ты считаешь, что на выходе компрессора всегда будет файл, попадающий под твое определение "архива"? > > Нет конечно, если на выходе файл "не архив" (коим может быть файл, полностью состоящий из нулей :), мы же понимаем, что все сжать в 0 бит невозможно, поэтому и не делаем это. > > > > Кто-то что-то хотел сделать "для поднятия траффика", а тут и так он уже зашкаливает! ;) > > > Вот тебе простенькая задача на суперсжатие: упакуй произвольное число от 0 до 260 в 1 байт. > > Сдается мне, что эта задача для дошкольников, но only for you я напишу решение: > > Общее количество чисел от 0 до 260 - 176, (посчитай если не веришь, только не забудь про систему счисления по основанию 8), а в 1 байте - 256. Усе! > > ;) > Хорошо, переформулирую :) > Упакуй произвольное число от 0x000 до 0x108 в 1 байт. С грантированным восстановлением исходного числа.

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