Архивация - предела нет...

[Ринат]

Странный вопрос может назреть: уже несколько десятков лет программное обеспечение и сами "железки" развиваются в усиленном темпе, но есть понятие, алгоритм которого застрял два-три десятка лет назад... Это алгоритм архивации информации. Одна из тех проблем, которые еще не нашли решения. Скажем, мы архивируем текст; размеры выходного файла уменьшены многократно. Но попробуйте проархивировать видео- или музыкальный фрагмент... Абсолютно никакой компактности, а порой даже добавка "лишнего веса". Как ни странно, но возникает чувство, что это никого не волнует. И впрямь, чейчас появились винчестеры с огромной емкостью (выше 100 Гб), зачем же архивировать информацию, которая и так просторно размещается на болванке? Но, всегда ли хранят такую информацию? Достаточно вспомнить, как тяжко приходится юзеру, отправляющему или получающему файл размера скажем 50 Мб. Что ж, некоторые фирмы решили и эту проблему, создав сверхвысокоскоростную передачу данных (быстрый интернет). И опять противоречие: такая передачя и стоит недешево, а отправка-принятие файла размером уже более 500 Мб также вызывает временные трудности.
Рациональный выход есть: архивация "без предела". Конечно понятие не очень точное, предел все же есть, но он гораздо дальше отстоит от предела нынешних способов архивирования информации. Кроме того, простые слова может сказать каждый, а вот на делее далеко уйдет не всякий. А что если кодировку файла сохранить, как текстовую, а затем попробовать проархивировать; затем кодировку уже готового архива вновь сохранить в виде текстового файла и снова проархивировать, и так далее, пока наконец формула Lim (Arch) при n ---> oo не достигнет своего предела Б (байты)... Может есть идеи?

[Indigo]

Ринат писал(а):

Но попробуйте проархивировать видео- или музыкальный фрагмент...

Мне казалось, что наоборот - современные алгоритмы сжатия видео- и аудио- информации достаточно эффективны за счет того, что они допускают потерю информации при сжатии.
А если Вы о том, что mp3 (к примеру) очень плохо архивируется rar'om - так это потому, что информация в mp3 и так уже очень хорошо сжата.

Ринат писал(а):

А что если кодировку файла сохранить, как текстовую, а затем попробовать проархивировать; затем кодировку уже готового архива вновь сохранить в виде текстового файла и снова проархивировать, и так далее, пока наконец формула Lim (Arch) при n ---> oo не достигнет своего предела Б (байты)... Может есть идеи?

Интуиция и опыт подсказывает, что достаточно хорошее приближение к этому пределу получается уже после первой архивации

[cepesh]

Скажите сразу, что Вы рассуждаете об архивации, ничего о ней не зная, не имея поверхностного представления об алгоритмах сжатия видео и аудио, о том, что степень сжатия одним алгоритмом варьируется для разных типов входящих данных, о том, что такое предел.
Не обижайтесь, просто стоит быть более подготовленным в вопросе, который хотите обсудить.

[dikun]

2 Ринат

Не обижайтесь, но Ваш пост выдаёт в Вас человека, практически не знакомого с алгоритмами компрессии.
Если Вы интересуетесь этой темой, может, стоит сходить на сайт, типа этого:
Сайт по методам сжатия данных

[Dan_Te]

Еще один аспект.
Есть такая математическая наука, как теория информации. Она облекает в строгую математическую форму следующий интуитивно понятный факт: любой файл содержит некоторое количество информации V, и сделать размер файла меньше V без потери информации невозможно. (Обычная архивация заключается в том, что файл содержит информацию V и имеет объем nV. "Лишний" объем позволяет увеличить скорость обработки файла. Программа-архиватор может убрать лишний объем частично или целиком, пожертвовав скоростью доступа к данным.)

[Ринат]

cepesh писал(а):

Скажите сразу, что Вы рассуждаете об архивации, ничего о ней не зная, не имея поверхностного представления об алгоритмах сжатия видео и аудио, о том, что степень сжатия одним алгоритмом варьируется для разных типов входящих данных, о том, что такое предел.
Не обижайтесь, просто стоит быть более подготовленным в вопросе, который хотите обсудить.

Конечно же я не обижаюсь, вот только в одном вы не правы... Об алгоритмах я знаю много. Достаточно перечислить Хаффмана, кодирование серий - RLE, арифметическое кодирование, Лемпеля-Зива и т.д. Об алгоритмах я читал много, а вопрос состоит вовсе не в гаданиях, как же еще сжать. В том то и дело, что при архивации видео и музыкальных фрагментов идет потеря качества, то есть информация пропадает. А на счет построения вопроса, то я вовсе не пытался тем самым создать новый закон архивации, а дать немного воли "фантазии". Поверьте, без нее ни о каком прогрессе и речи быть не может. И еще, я ведь только на второй курс перешел и не удивляйтесь, пожалуйста, если я часто буду говорить лишнее - мне еще учиться и учиться, а учеба, как известно проходит по пути проб и ошибок. Удачи!

[Ринат]

dikun писал(а):

2 Ринат

Не обижайтесь, но Ваш пост выдаёт в Вас человека, практически не знакомого с алгоритмами компрессии.
Если Вы интересуетесь этой темой, может, стоит сходить на сайт, типа этого:
Сайт по методам сжатия данных

Большое спасибо за ссылку, и я вовсе не обижаюсь, но не спешите оценивать человека взглянув на то, что он пишет. Об алгоритмах я знаю достаточно, и вопрос мой как раз таки и говорит об этом, ведь я намекнул в нем, что "существует именно много способов архивирования"... Остальной ответ выше... Спасибо за отклик.. Удачи!

[roof]

Если ты знаком с основами архивации, возможно, тебе стоит подумать вот о чем: алгоритмы сжатия, в основном используют регулярность файла, т.е. наличие в нем повторяющихся последовательностей. Из таких последовательностей строится словарь, затем каждому слову из словаря ставится в соотвествие код, причем чем чаще слово встречается в файле, тем код короче. Файлы уже сжатые какими-либо средствами (файловые архивы, видео, графика и звук) имеют нерегулярную структуру, поэтому попытка дополнительно сжать их приведет лишь к увеличению размера файла (как минимум, на размер словаря). Вот так, и чудес не бывает. А жаль... Запустил в цикле алгоритм архивации, ужал двухчасовой ДВД до размера дискетки - лепота!(Это к вопросу о фантазии )

[Ринат]

roof писал(а):

Если ты знаком с основами архивации, возможно, тебе стоит подумать вот о чем: алгоритмы сжатия, в основном используют регулярность файла, т.е. наличие в нем повторяющихся последовательностей. Из таких последовательностей строится словарь, затем каждому слову из словаря ставится в соотвествие код, причем чем чаще слово встречается в файле, тем код короче. Файлы уже сжатые какими-либо средствами (файловые архивы, видео, графика и звук) имеют нерегулярную структуру, поэтому попытка дополнительно сжать их приведет лишь к увеличению размера файла (как минимум, на размер словаря). Вот так, и чудес не бывает. А жаль... Запустил в цикле алгоритм архивации, ужал двухчасовой ДВД до размера дискетки - лепота!(Это к вопросу о фантазии )

А что, если попробовать такие алгоритмы откинуть и попробовать придумать алгоритм, работающий вообще не с символами кодировки (т.е. с ними он работать будет, но не непосредственно). Конечно, это лишь слова, что ж поделать, и Галилея считали глупцом, когда он говорил, что "она вертится"...

[roof]

Это как? Под повторяющимися последовательностями я подразумевал последовательности байт. Любой алгоритм сжатия так или иначе будет с ними работать. Или я тебя не понял?

[Dan_Te]

Цитата:

А что, если попробовать такие алгоритмы откинуть и попробовать придумать алгоритм...

Это отличная идея! Другие идеи, над которыми стоит подумать на досуге:
- телепортация или что-нибудь. Чтобы летать, быстро, но не так как мы сейчас на самолетах, а как-нибудь по-другому
- дешевая энергия, но без вредных выбросов, а какая-нибудь другая. Придумать такую энергию.

Ну и далее в том же духе.
8)

[cepesh]

[Ринат]

Dan_Te писал(а):

- телепортация или что-нибудь. Чтобы летать, быстро, но не так как мы сейчас на самолетах, а как-нибудь по-другому
- дешевая энергия, но без вредных выбросов, а какая-нибудь другая. Придумать такую энергию.
8)

Не плохой полет фантазий.

[Sanyok]

Я тоже пытался разработать "крутейший" алгоритм сжатия и потерпел фиаско.. Идея состояла в том, что:

1) Любой УЖЕ сжатый файл - это вообще-то случайная последовательность.
2) Существуют очень длинные псевдослучайные последовательности(ПСП), причем, что бы эту длинную последовательность получить, достаточно хранить небольшое количество информации (например, для полинома 16-ой степени - 32 разряда(16 для полинома и 16 для начального значения) + некоторое число разрядов для хранения длины последовательности.
3) Мне казалось очень вероятным, что какой-то небольшой кусок очень длинной ПСП может совпадать с каким-то куском сжатого файла. Если этот кусок будет больше, чем объем информации, необходимый для его порождения, цель достигнута - объем данных уменьшен.

Я написал программку для 16-разрядного полинома, причем перебирались все полиномы (а не только те, что порождают ПСП максимальной длины) и выяснилось, что .... короче, либо разрядов надо больше брать, либо все это вообще лишено смысла. Еще есть один вариант, но скорей всего, он тоже обречен на неудачу. Предположим, сгенерированная ПСП "почти" совпадает с неким куском, и есть несколько несовпадений. Если этот кусок, который мы хотим сжать, закодирован с использованием какого-либо кода, исправляющего ошибки, и ПСП вносит небольшое количество ошибок (допускающее последующее восстановление исходных данных), то задачу тоже можно считать решенной в какой-то мере...

[незваный гость]

Да-с, а я думал, тема мертва.

1) Плохая архивация mp3 или уже сжатых файлов имеет мало чего общего с информацией в файлах. Тому есть два примера: a) попробуйте сжать зашифрованный файл - получится плохо, хотя объем информации тот же; b) пусть $X = zip(T)$, тогда $rar(zip^{-1}(X)) \ll rar(X)$, хотя количество информации опять же прежнее. Если я правильно понимаю, тут важна еще модель сжимаемых данных. Именно поэтому специализированные алголитмы сжатия данных (например, losslеss JPEG) обгоняют ZIP/RAR как стоячего. У них - специализированная модель, учитывающая двумерную организацию данных. Модели количества информации хороши, когда оно (количество) известно. Сколько информации в "Войне и Мiре"? Зависит от контекста передающего/получающего. И контекст этот всегда присутствует - длина байта, кодировка, и многое другое. Сжатие повторяющегося текста, глядя назад - всего лишь одна из моделей.

2) Интересно, что в свое время разрабатывались, но большого распространения не получили, алгоритмы с предсказыванием (непрочитанных байт). Угадав правильно, нам надо передать только один бит, а то и меньше - количество правильно угаданных бит. Они требовали память мегабайтами(2-16 MB), что представлялось в 80-е весьма непрактичным. А сейчас о них не слышно почему-то. Может потому, что главное массовое распространение формата, а вовсе не степень сжатия.

3) По крайней мере пару лет назад, самым дешевым и быстрым способом передачи больших объемов информации в США была ... почта. По крайней мере одна фирма с оффисами в Нью-Йорке и Сан Франциско записывала информацию на винт компьютера и в 6 вечера отправляла системный блок. В 8 утра он уже был готов к работе на другом побережье. (Они пытались отправлять винчестер отдельно, но слишком много мороки с OS. Тогда, по-видимому, внешние винты были мало распространены.)