Re: Вопрос: А есть ли где-нибудь матописание суперкомрессии без потерь?

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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > > > Интересуют описания суперкомрессии без потерь > > > Это есть в теории множеств. :) > > > Достаточно просто доказывается, что > > > таких алгоритмов не существует. > > Так и предполагал, что в ответ услышу что-то подобное… Вообще-то я попробовал найти в теории множеств такое доказательство, посмотрел и в учебниках и в инете – что-то там я ничего не нашел. Максимум, что я нашел в виде доказательства невозможности существования такого алгоритма в инете – что-то типа «отображением множества всегда является множество», что в общем-то ни о чем не говорит. Множество архивов (цепочек с примерным равенством 1 и 0 в них) гораздо менее мощное, чем множество всех остальных файлов той же длины. > Доказательство довольно простое: > Пусть у нас есть безпотерьный компрессор, сжимающий > любой файл длины N бит как минимум на 1 > бит, и по крайней мере не увеличивающий > в размерах файлы меньшей длины. > Тогда количество всех файлов длины не более чем N будет 2^(N+1)-1. Количество всех архивов, построенных по файлам длины не более чем N будет 2^N-1. > Следовательно, найдется по крайней мере один архив, которому будут соответствовать несколько исходных файлов. Как в таком случае определить по архиву, каков был исходный файл? > Кроме того, а что твой компрессор будет делать с файлами, у которых количество "0" значительно больше, чем количество "1"? > > В то же время есть такой пример – под ДОС была такая замечательная программка-заставка «Полет над песками Марса», размером что-то порядка 1 или 2 килобайт. У меня возник вопрос – а если то же самое мы опишем в МП4 формате (до повтора) – сколько это займет места? > Это неплохой пример избыточности, не используемой в настоящее время видеокодерами. К сожалению, данная избыточность довольно-таки редко встречается. :-) > > Значит можно для данного случая создать какой-то алгоритм, позволяющий получить суперкомпрессию. За счет чего она получается – данные описываются в виде функции. Но это для частного случая – а можно ли применить для любого? > Можно попробовать, если попытаться построить функцию, значения которой будут близки к данным, а потом отдельно закодировать разницу между данными и полученной функцией. > > Возникла тут у меня на основании этих рассуждений одна идейка (в реализации не совсем такая, как описал выше, но в общем-то в первом приближении недалеко от этого), написал несколько тестовых программок – и вдруг неожиданно для самого себя увидел, что вроде бы она (идея) должна работать. > Если заработал упаковщик, это еще ни о чем не говорит. Нужно, чтобы работал распаковщик. :-) > У меня подобным образом обломалась одна идея с фильтрами -- я забыл писать в выходной поток флажки. После восстановления справедливости идея стала давать отрицательные результаты. > > Но есть очень большие сомнения что такой алгоритм потянет современный компьютер… Вполне возможно, что эффект архивации и будет достигнут, но необходимое для вычисления нужной функции время будет измеряться днями или годами или столетиями. Точно математику к сожалению пока не досчитал – слишком уж она при кажущейся простоте идеи получается навернутой – и в теоретическом плане и при возможной реализации в программе. > > И, естественно, у меня возник вопрос – а может я пытаюсь изобрести велосипед? > Скорее, это сродни вечному двигателю. > > Может уже есть что-то подобное, описанное математиками и уже известно примерно, что при достижении компьютерами определенной мощности такие архиваторы появятся? В любом случае математику я наверное досчитаю – надеюсь, что в течении ближайшего месяца. Но имеют ли смысл мои телодвижения в данном направлении? Вот как раз этот вопрос я и хотел для себя прояснить, может все это уже давно известно и не стоит тратить впустую время... > > > Любой архиватор/компрессор сжимает > > > реальные данные за счет имеющихся в > > > данных закономерностей (достаточно > > > частые повторения цепочек символов, > > > существенно разные вероятности > > > появления разных символов и т.д.) > > Опять-таки, здесь говорится о тех архиваторах, которые существуют на сегодня и о тех закономерностях, которые они используют. Но ведь возможны и другие принципы! > Возможны, не спорю. Но есть такое понятие, как "реальные файлы" -- то есть такие файлы, которые обычно люди сжимают на практике. И тот человек, который наиболее полно использует избыточность реальных файлов, и получает хорошо жмущий архиватор. > > > "Теоретически несжимаемые данные" обладают тем свойством, что в них подобные закономерности отсутствуют. > > > Возможно, в некоторых специальных случаях и получится выделить закономерности, но они не будут > > > применимы для подавляющего большинства > > > файлов. > > Опять-таки неверное утверждение! Для любых файлов (правда, надо оговориться – большого размера) существуют закономерности. Их описывает теория вероятности. Их нахождение – задача не из легких, но в принципе по-моему разрешимая. Во всяком случае замеряемая мною на реальных несжимаемых файлах статистика находится в полном соответствии с теорией вероятности - и мне это очень нравится… > Возьми архив, сделанный любым архиватором, использующим арифметический кодер, и посмотри на статистику в этом случае. > Архивы, .mp3 и тому подобное -- это специальный подвид реальных файлов. В том же .mp3, который пожат Хаффманом на выходе действительно имеются закономерности, позволяющие его немного дожать. > zz.mp3 : 202016 bytes > zz.slim: 201466 bytes > zz.ppmd: 200076 bytes > ... > zz.enc : 197533 bytes > ... > zz.ppmonstr: 196525 bytes > zz.777 : 196049 bytes > Возможно, имеет некий смысл сделать компрессор для малоизбыточных файлов. > Но по причинам, описанным выше, этот компрессор не будет сжимать _все_ файлы.

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

[an error occurred while processing this directive]