2014 dxdy logo

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

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




 
 Сжатие данных, архивация, сложность последовательности
Сообщение02.08.2006, 21:19 
Пусть дана последовательность целых чисел $x_1, x_2, ..., x_n$. Для любой ли такой последовательности можно указать принцип её построения и формулу $n$-ого члена?

 
 
 
 
Сообщение02.08.2006, 21:32 
Без дополнительной информации о структуре последовательности, никакая конечная часть не даст полную информацию о всей последовательности.

 
 
 
 
Сообщение02.08.2006, 21:49 
Не совсем Вас понял. Что значит дополнительная информация о её структуре? Мой вопрос заключался в том, что если я составляю произвольную целочисленную последовательность конечной длины, то обязательно ли она будет ли она удовлетворять какой-либо формуле?

 
 
 
 
Сообщение02.08.2006, 21:55 
Формул бесконечно много, а потому и продолжений бесконечно много. Например, я определю формулу так, что пока n<10000000 значения определяются таким образом, как выпали при бросании костей, а далее нули.
Термин опреляется формой требует уточнения. Я под этим понимаю рекурсивная последовательность. И в этом смысле ответил.

 
 
 
 
Сообщение02.08.2006, 22:05 
Вообще изначально меня интересовал следующий вопрос: нам дают целочисленную последовательность конечной длины. Чтобы вывести её на экран с помощью программы, необходимо символов примерно столько же, сколько членов в последовательности. Но если мы найдём какую-нибудь формулу для выражения членов последовательности (формула должна быть по длине значительно короче самой последовательности), то заметно сократим длину программы, сэкономив память ЭВМ.

 
 
 
 
Сообщение02.08.2006, 22:17 
Это разумный вопрос. Тут не требуется, чтобы и дальнейшие члены удовлетворяли полученной формуле. Формула используется только как сокращённая кодировка заданной конечной последовательности чисел. Но для решения, кроме небольшого количества простых случаев, желательно иметь дополнительную информацию, которая может существенно сократить как получение такого кода, так и длину этого кода.

 
 
 
 
Сообщение02.08.2006, 22:18 
Аватара пользователя
Ну, это типичная задача сжатия информации. Почти дословно - определение сложности последовательности по Колмогорову.

Любую конечную последовательность можно представить некоторой формулой (например, многочленом, число коэффициентов в котором равно числу значений последовательности). Отсюда следует, в частности, что любую последовательность можно представить бесконечным числом формул. Выбрать из них самую короткую - задача, которой, по сути, занимаются испокон веков все архиваторы.

Сумеете найти новый супер-алгоритм, лучше существующих - имеете шанс стать богатым человеком. Как мне кажется, алгоритм Лемпела-Зива вроде принес своим создателям соответствующие плоды, кто знает?

 
 
 
 
Сообщение03.08.2006, 00:24 
Аватара пользователя
PAV писал(а):
Сумеете найти новый супер-алгоритм, лучше существующих - имеете шанс стать богатым человеком. Как мне кажется, алгоритм Лемпела-Зива вроде принес своим создателям соответствующие плоды, кто знает?

Скорее Велшу, который приложил руку к созданию и патентованию алгоритма LZW (Lempel-Ziv-Welch). Читайте историю.

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

 
 
 
 
Сообщение03.08.2006, 01:52 
Аватара пользователя
:evil:
maxal писал(а):
Скорее Велшу

Боюсь, что и не ему, а Unisys.

maxal писал(а):
А протолкнуть новый алгоритм компрессии, будь он даже супер-пупер, будет проблематично. Рынок перенасыщен подобными вещами и все новое приживается крайне медленно.

Похоже, что во многом процветает отношение «good enough». Для обычных данных — zip, для реального времени — lzo, для надежно сжатых и шифрованных — rar, для специальных — mp3, ape, и divx. Делаются специальные алгоритмы для сжатия XML (учитывающие схему), например.

Мое впечатление, для успеха фактор сжатия вторичен, равно как и скорость сжатия/расширения. Первичными оказываются нетехнические факторы — свободность от патентов, доступность библиотек и open source реализаций, дополнительные (побочные) бенефиты вроде надежного шифрования. Патенты — очень серьезно, эта область одна из самых тяжелых в патентном смысле (наряду с криптографией).

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group