Сжатие данных, архивация, сложность последовательности

[икс и грек]

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

[Руст]

Без дополнительной информации о структуре последовательности, никакая конечная часть не даст полную информацию о всей последовательности.

[икс и грек]

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

[Руст]

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

[икс и грек]

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

[Руст]

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

[PAV]

Ну, это типичная задача сжатия информации. Почти дословно - определение сложности последовательности по Колмогорову.

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

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

[maxal]

PAV писал(а):

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

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

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

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

maxal писал(а):

Скорее Велшу

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

maxal писал(а):

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

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

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