Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Сжатие функциональных зависимостей

Автор: ksili 30.5.2006, 06:45

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

Код


1 4 9 16 25 36 49 64 81 100          (квадраты)

или ряд

Код


1 2 3 4 5 6 7 8 9 10          (арифметическая прогрессия)

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

Автор: esperant0 30.5.2006, 09:38

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

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

Автор: ksili 31.5.2006, 09:56

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

Автор: skyboy 31.5.2006, 10:06

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

Автор: ksili 31.5.2006, 10:43

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

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

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

Автор: Akina 31.5.2006, 10:47

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

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

Автор: skyboy 31.5.2006, 11:00

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

Автор: ksili 31.5.2006, 11:18

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

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

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

Автор: skyboy 31.5.2006, 12:16

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

Автор: ksili 31.5.2006, 12:36

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

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

Автор: maxim1000 31.5.2006, 12:55

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

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

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

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

Автор: ksili 31.5.2006, 13:18

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

Автор: nostromo 31.5.2006, 13:44

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

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

Автор: Akina 31.5.2006, 14:35

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

Автор: esperant0 31.5.2006, 15:19

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

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

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

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

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

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

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

с уважением

Автор: ksili 1.6.2006, 10:02

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

Буду искать. Может кто подскажет? Буду очень благодарен

Автор: skyboy 1.6.2006, 10:50

ksili, продумывать борьбу с шумом надо исходя из твоего алгоритма. Так как по описаню я не могу понять, как он работает, то приведу на примере моего(довольно примитивного, честно говоря) решения - использования метода Лангранжа. Так вот, пусть наши данные - это координата У. А координате Х соотвествует порядковый номер текущего обрабатываемого байта. Тогда если выбросить самый отдалённые точки(я имею в виду работу со статистическими параметрами выборки - термины забыл), можно провести интерполяцию по оставшимся, а потом - явно задать блок "отброшенных" точек в виде Х=..;У=.. При восстановлении получить ряд из коэффициентов полинома, а потом скорректировать его путём наложения данных из "блока отклонений". В принципе, получается то, о чём говорил maxim1000, только вот применение изначально интерполяционного метода гарантирует, что количество записей в блоке коррекции ошибок известно уже после "отбрасывания" "неугодных" значений, а при применении аппроксимирующего метода необходимо пробежаться по всем значениям в поиске отклонений.