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
17973
Москва
Evg_Kn писал(а):
любой файл можно сжать до заданного размера, подобрав алгоритм соответствующий. дело лишь в том, что общего алгоритма сжатия, который сожмет все сделать невозможно.


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

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


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

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


23/07/05
17973
Москва
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
17973
Москва
Debiloid писал(а):
незванный гость писал(а):
:evil:
Debiloid писал(а):
Вы в каком веке живёте? Европа давно забыла слово "модем".

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


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


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

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

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


23/07/05
17973
Москва
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, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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