fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу Пред.  1, 2, 3, 4, 5  След.
 
 
Сообщение15.11.2005, 03:05 
Dan_Te писал(а):
Еще один аспект.
Есть такая математическая наука, как теория информации. Она облекает в строгую математическую форму следующий интуитивно понятный факт: любой файл содержит некоторое количество информации V, и сделать размер файла меньше V без потери информации невозможно. (Обычная архивация заключается в том, что файл содержит информацию V и имеет объем nV. "Лишний" объем позволяет увеличить скорость обработки файла. Программа-архиватор может убрать лишний объем частично или целиком, пожертвовав скоростью доступа к данным.)

любой файл можно сжать до заданного размера, подобрав алгоритм соответствующий. дело лишь в том, что общего алгоритма сжатия, который сожмет все сделать невозможно.

  
                  
 
 
Сообщение15.11.2005, 23:55 
Заслуженный участник
Аватара пользователя


23/07/05
18037
Москва
Evg_Kn писал(а):
любой файл можно сжать до заданного размера, подобрав алгоритм соответствующий. дело лишь в том, что общего алгоритма сжатия, который сожмет все сделать невозможно.


Да, это так. Вписываем в программу-компрессор текст "Войны и мира" (можно сжать каким-нибудь компрессором, ориентированным на текстовые файлы). Затем, когда мы применяем наш компрессор к какому-нибудь файлу, программа проверяет, не совпадает ли содержимое файла с текстом "Войны и мира". Если совпадает, то в заголовке сжатого файла помечается, что это за текст, а тело файла можно сделать пустым. Если не совпадает, то помечаем, что это не "Война и мир", и сжимаем, как умеем.

 Профиль  
                  
 
 
Сообщение16.11.2005, 00:31 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
А информация, точно идентифицирующая выбранный алгоритм, как раз размером с сжимаемый файл :wink:

 Профиль  
                  
 
 
Сообщение16.11.2005, 01:08 
Заслуженный участник
Аватара пользователя


23/07/05
18037
Москва
PAV писал(а):
А информация, точно идентифицирующая выбранный алгоритм, как раз размером с сжимаемый файл :wink:


Ну, всё-таки немного поменьше, мы же эту информацию в сжатом виде храним, а осмысленные текстовые файлы типа "Войны и мира" достаточно хорошо сжимаются.
А вообще, чего же Вы хотели?

 Профиль  
                  
 
 
Сообщение16.11.2005, 01:38 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
PAV писал(а):
А информация, точно идентифицирующая выбранный алгоритм, как раз размером с сжимаемый файл :wink:


Да, а кого это волнует, если, например, нам только Толстого пересылать. Вас ведь врядли смущают кодовые таблицы. А ведь это сжатое представление четырехбайтного ISO-10646. Очень характерный пример - сжатие XML файлов, когда сделав схему доступной соответствующему компрессору/декомпрессору, удается получить существенно большее сжатие, чем общецелевым алгоритмом. А схема может быть заметно больше каждого из пересылаемых сообщений.

 Профиль  
                  
 
 
Сообщение20.11.2005, 00:45 
Аватара пользователя


14/05/05
224
Баку
Поделюсь ка и я своими "фэнтези":
Я как-то отмечал на счет алгоритмов сжатия, что мол "можно использовать алгоритмы для работы вообще не с сивольными данными". Я придумал такую штуку: а что если те последовательности, которые возможно отыскать, в противном случае же просто использовать единичные символы, кодировать не символами, как это делают архиваторы, а цветом. Т.е. идея такова: просматриваем файл, находим последовательности (или единичные символы). Генерируем к каждой последовательности свой цвет (в принципе лучше использовать отдельные символы, так как их в таблице ASCII всего 256, как раз столько же цветов в таблице VGA), а затем просто выводим эти данные о цветах попиксельно на чистый экран (т.е. файл). При этом сохраняется последовательность, а на экране формируется как бы "картика файла". Вроде бы круто! Но, чисто графический файл без использования всяких фильров может по объему превосходить оригинальный кодируемый файл в десятки раз. Вот тут то и проявляется дефект. Я сравнивал различные форматы и оказалось, что наиболее приемлемым мог бы служить формат TIFF, или PNG, но форматы эти сильно искажают картинку, так как содержат фильтры сжатия данных. А неплохо было бы, если б скажем одна страница такого "графического архива" занимала объем скажем максимум в 1 КБ, с размещением на ней объема минимум в 1 МБ :) "
Интересно еще и вот что... Действительно, с 80-х гг. программеры пытались раскрыть тайну "главного" алгоритма. Были достигнуты кое-какие результаты, но почему бы не задуматься над другим?
Скажем нам надо передать ниформацию быстро (пускай это сведения о работе атомного реактора). Если информация чересчур объемна, следует сжать ее на сколько позволяет алгоритм. А если мы потерпели фиаско с жатием? Тогда в лучшем случае атомный реактор просто остановится). Может просто следует заниматься вовсе не проблемами уменьшения объема, а проблемами ускорения передачи данного объема информации? К сожалению, в наше время основная часть юзеров по всему миру продолжает использовать обычное подключение через 56Кб модем. Даже тем, кто и перешел на новые технологии (типа выделенной линии, хотя назвать эту технологию новой трудно, спутниковой связи Wi-Fi и т.д) не всегда удается получить требуемую информацию за быстрый промежуток времени. Может, в реале, стоит в серьез занятся именно разработкой новых видов передачи информации? Представляете? Поискал в google файлик, нащел - 5 Гб. Нажал на "скачать", указал папку и видно, как побежали проценты: 5 - 10 - 20 -50 -100 %! Шик!

 Профиль  
                  
 
 Re: Архивация - предела нет...
Сообщение21.12.2005, 18:56 
Заблокирован


21/12/05

38
Ринат писал(а):
Странный вопрос может назреть: уже несколько десятков лет программное обеспечение и сами "железки" развиваются в усиленном темпе, но есть понятие, алгоритм которого застрял два-три десятка лет назад... Это алгоритм архивации информации. Одна из тех проблем, которые еще не нашли решения.


Не делайте смешно моим носкам.

http://en.wikipedia.org/wiki/Algorithmi ... ity_theory

Задача просто NP-полная. И всё. Решение однозначное - минимальная последовательность, однозначно кодирующая данные (так называемая "информация") есть всегда (но может совпадать с самими данными, если они несжимаемы).

Цитата:
Рациональный выход есть: архивация "без предела".


Иными словами - сжатие с потерями. Спасибочки, даром не надо-с.

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


Полечиться попробуйте.

 Профиль  
                  
 
 
Сообщение21.12.2005, 18:56 
Заблокирован


21/12/05

38
Evg_Kn писал(а):
любой файл можно сжать до заданного размера, подобрав алгоритм соответствующий. дело лишь в том, что общего алгоритма сжатия, который сожмет все сделать невозможно.


Возможно. С экспоненциальной сложностью. Ещё Колмогоров показал, как именно.

 Профиль  
                  
 
 
Сообщение21.12.2005, 18:59 
Заблокирован


21/12/05

38
Ринат писал(а):
К сожалению, в наше время основная часть юзеров по всему миру продолжает использовать обычное подключение через 56Кб модем.


Вы в каком веке живёте? Европа давно забыла слово "модем".

 Профиль  
                  
 
 
Сообщение21.12.2005, 19:20 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Debiloid писал(а):
Вы в каком веке живёте? Европа давно забыла слово "модем".

А какая, простите, разница - 56K или 56G? Все равно найдутся задачи, где ширина трубы - критический параметр. Или надо платить за каждый перекачанный TB.

 Профиль  
                  
 
 
Сообщение21.12.2005, 19:25 
Заблокирован


21/12/05

38
незванный гость писал(а):
:evil:
Debiloid писал(а):
Вы в каком веке живёте? Европа давно забыла слово "модем".

А какая, простите, разница - 56K или 56G?


Большая. Мало реалистичных задач, требующих полосы более 1мегабита - так что нет нужды возиться с сжатием.

 Профиль  
                  
 
 
Сообщение21.12.2005, 19:44 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Debiloid писал(а):
Большая. Мало реалистичных задач, требующих полосы более 1мегабита - так что нет нужды возиться с сжатием.

Когда системе управление с временем принятия решения 5 ms нужен обмен информацией между 20 узлами порядка 3-5 KB данных/узел, причем надежно доставленных, разработчики как-то не отвечают начальству, что "мало реалистичных задач требует больше 1 Mbit". Они быстро начинают считать емкость канала - а хватит ли 100 Mbit? И какой overhead протокола? Будет ли работать TCP/IP? А UDP/IP? А что делать, если канал порвался? Какое время переключения на запасной? А время восстановления? А сколько времени займет сжатие? А кто сжимает в реальном времени? Есть ли что-нибудь кроме LZO? ...

А когда банк платит за 1 M сообщений / 1 GB, он тоже как-то не спешит выкладывать свои миллионы связистам. А начинает, подлец, жать как проклятый.

Поверьте, я видел и то и другое.

А у ламера действительно мало проблем. На то он и ламер. "Сидя на красивом холме // Я часто вижу сны, и вот что кажется мне"

 Профиль  
                  
 
 
Сообщение21.12.2005, 20:01 
Заслуженный участник
Аватара пользователя


23/07/05
18037
Москва
Debiloid писал(а):
незванный гость писал(а):
:evil:
Debiloid писал(а):
Вы в каком веке живёте? Европа давно забыла слово "модем".

А какая, простите, разница - 56K или 56G?


Большая. Мало реалистичных задач, требующих полосы более 1мегабита - так что нет нужды возиться с сжатием.


Нда... Некто Ф.Х.Уэйльс в 1936 году говорил: "Не могу представить себе, чтобы кому-нибудь потребовалось выполнять умножение со скоростью 40000 или даже 4000 операций в час" (цитата есть у Д.Кнута, Искусство программирования для ЭВМ, Том 2, Получисленные алгоритмы, "Мир", Москва, 1977, эпиграф к главе 4).

Когда разрабатывались IBM PC, адресное пространство было заложено в 1 Mb. В то время казалось, что это так много...

 Профиль  
                  
 
 
Сообщение21.12.2005, 20:04 
Заслуженный участник
Аватара пользователя


23/07/05
18037
Москва
Debiloid писал(а):
Evg_Kn писал(а):
любой файл можно сжать до заданного размера, подобрав алгоритм соответствующий. дело лишь в том, что общего алгоритма сжатия, который сожмет все сделать невозможно.


Возможно. С экспоненциальной сложностью. Ещё Колмогоров показал, как именно.


По тривиальным математическим причинам не существует способа сжать всё, а потом восстановить в первоначальном виде.

 Профиль  
                  
 
 
Сообщение21.12.2005, 20:06 
Заблокирован


21/12/05

38
Someone писал(а):
Debiloid писал(а):
Evg_Kn писал(а):
любой файл можно сжать до заданного размера, подобрав алгоритм соответствующий. дело лишь в том, что общего алгоритма сжатия, который сожмет все сделать невозможно.


Возможно. С экспоненциальной сложностью. Ещё Колмогоров показал, как именно.


По тривиальным математическим причинам не существует способа сжать всё, а потом восстановить в первоначальном виде.


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 63 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group