Кто-нибудь знает архиваторы, которые при сжатии учитывают (и потому хорошо сжимают) последовательности, члены которых подчиняются какой-нибудь функциональной зависимости?
Например, есть ряд 

или ряд

а архиватор эту зависимость распознает и сожмёт первый ряд до начального элемента и идентификатора зависимости (в данном случае y=x*x), второй ряд до начального элемента и разности прогресии (допустим так)

Все, все ряды подчиняются какой нибудь функциональной последовательности.

А самым идеальным архиватором не увеличивающим длину входных данных является ф-я сору, это и есть ответ на ваш вопрос 

esperant0, речь идёт об архиваторах уменьшающих длину входных данных, а не "неувеличиващих". И я не спрашиваю об идеальных архиваторах (что значит "идеальный"?) - назови мне хоть один архиватор, использующий описанный подход. 

ksili, как ты себе представляешь процесс сжатия? О! Ты аппроксимируй значения, считая что значения х возрастают и равны позиции элемента, а значением у будет твоя последовательность. И запоминай в коде только значения коэффициентов полинома. А касательно "идентификатора зависимости" - это типа таблица должна быть:
идентификатор описание
           1                арифметическая прогрессия с шагом 0,5
           2                геометрическая прогрессия с шагом 0,7
           3                х в степени 0,23 + номер элемента * 12
Так? И тягать за собой таблицу из безконечного количества элементов? 

не так. Таблица допустим такая:
1       арифметическая прогрессия
2       геометрическая прогрессия
3       степенная функция

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

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

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

Архиватор ОБЩЕГО назначения никогда такой фигней маяться не будет. 

Akina, после аппроксимирования восстановить данные будет невозможно.
ksili, а как быть с комбинацией (степенная функция от геометрической прогрессии, например) и как определять столь сложные взаимосвязи? И в чём я себе противоречил, так я и не понял. Описанных и названный функциональных зависимостей хоть и много, но не бесконечно. Бесконечных является разного рода суперпозиция этих зависимостей, дающая новую "модель поведения" для ряда... Да и как опредлить, что наш ряд - это целые части членов степенного ряда y=2.3^(0.2*x)? Не думаю, что подобный анализатор-архиватор создать реально... Вот использование того же полинома Лангранжа или другого метода интерполяции - ещё куда ни шло... 

Спасибо, за ответы. 

Я собственно, спрашивал о том, есть ли что-то такое среди архиваторов или нет. Я тоже думал, что такое маловероятно. Как оказалось не я один такой.

Согласен, что аппроксимация не подойдёт - меня интересует прежде всего сжатие без потерь информации 

ksili, если не военная тайна, а зачем столь хитрый подход к сжатию? Почему бы не использовать статистические или словарные алгоритмы сжатия?  

Это сообщение отредактировал(а) skyboy - 31.5.2006, 12:18

Я аспирант. Хочу придумать новый алгоритм сжатия и защитить по этой теме дисертацию. А подход, по-моему, проще не бывает.

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

обычно, пытаются архивировать зависимости в более широком смысле - не x(n+1)=f(x(n))
пример - спектр, используется в Jpeg
если ему подать гармонический сигнал - по идее, должен сжать очень хорошо
GIF расчитан на хорошее сжатие последовательностей типа x(n+1)=x(n) 
различные компрессоры для речевых сигналов расчитаны на сжатие авторегрессионных последовательностей x(n+1)=a*x(n)+b*x(n-1)+...
так что если сузить область применения, то можно найти класс зависимостей, которые хорошо аппроксимируют большое количество сигналов из этой области

касательно аппроксимации и сжатия без потерь
понятия это совсем не противоречивые
архиватор без потерь можно построить по такой схеме:
1. аппроксимация сигнала какой-то моделью (чтобы её параметры занимали значительно меньше места)
2. сохранение ошибки
так вот, если аппроксимация удачна, ошибка будет представлена очень маленькими данными, и к ним уже можно будет применять что-нибудь типа Хаффмана/арифметического кодирования

Jpeg в режиме без потерь поступает по-другому: он строит модель изображения, точно его приближающую, а потом её архивирует энтропийными методами
(но там проблема в том, что точная модель имеет дело с действительными числами и всё равно получаются потери з-за вычислений) 

maxim1000, многое из этого я знал, но всё равно спасибо за замечания. Со всем согласен.
Когда сделаю что-нибудь толковое и сравню с известными архиваторами, выложу здесь результаты.
 

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

Поэтому вопрос о целесообразности применения тех или иных методов сжатия можно рассматривать только в контексте определенного типа данных, в противном случае все это будет из разряда поиска философского камня.  

Может, еще посмотреть на принцип кодирования видеопотока, где берется базовый кадр и гонятся его изменения, по объему гораздо мЕньшие? В принципе для блочных данных это может давать значительный выигрыш. По сути то же деление на базовую аппроксимацию и отклонение... 

ksili,  послушайте мнение бывшего аспиранта.

обясняю все последовательно.

Утверждение 1:

Любая последовательность чисел подчиняеться какой нибудь функциональной зависимости( причем не одной а бесконечному числу).
( например тот же полином проходящий через точки (1,х1) (2,х2) (3,х3)  и тп.

Утверждение 2: Не существует алгоритма сжимающего хоть чуть чуть ЛЮБУЮ последовательность.

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

Вывод: вам нужно наложить ограничения на входные даннын и тогда можно думать дальше.


с уважением