2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 14:32 


29/03/18
4
Здравствуйте,

Необходимо сжать (упаковать) набор данных методом линейной интерполяции.

Дано:
Набор данных {X, Y} , где Х – временные точки, Y – значения в этих временных точках. Так же дано значение погрешности, которая допустима при сжатии данных.

Задача:
Сжать исходный набор данных «выкинув» из него значения, которые могут быть в последствии (при распаковке сжатых данных) получены из оставшихся значений с помощью линейной интерполяции.

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

Для более подробного понимания ниже приведен код реализованной функции на С++ для сжатия буфера с данными.
Входные параметры:
Times - вектор временных точек
Values - вектор значений в этих точках
Результирующий набор данных формируется в структуре resultBuf и в конце переписывается в Times и Values соответственно.
Код:
void CompressBuffer(std::vector<double>& Times, std::vector<double>& Values)
{
   struct Buffer
   {
      std::vector<double> Time;
      std::vector<double> Value;
   };
   Buffer resultBuf;               // buffer for saving results
   
   size_t SizeOfBuf = Times.size();    // number of elements in input buffer
   bool IsOk = true;               // true if interpolated values are located in tolerances
   int LeftIndex = 0;               // index of the left value
   int RightIndex = SizeOfBuf - 1;       // index of the right value

   while (LeftIndex < SizeOfBuf - 1)
   {
      for (int i = LeftIndex; i <= RightIndex; i++)
      {
         double InterpolatedValue = Interpolate(Values[LeftIndex], Values[RightIndex], Times[LeftIndex], Times[RightIndex], Times[i]);
         if (abs(InterpolatedValue - Values[i]) > abs(Values[i]) * RelativeTolerance + AbsoluteTolerance)
         {
            IsOk = false;
            break;
         }
      }
      if (IsOk == false)
      {
         RightIndex = (LeftIndex + RightIndex) / 2; // nRightIndex = centre
         IsOk = true;
      }
      else
      {
         resultBuf.Time.push_back(Times[LeftIndex]);
         resultBuf.Value.push_back(Values[LeftIndex]);
         LeftIndex = RightIndex;
         RightIndex = static_cast<int>(SizeOfBuf) - 1;
         if (LeftIndex >= SizeOfBuf - 1)
         {
            resultBuf.Time.push_back(Times[RightIndex]);
            resultBuf.Value.push_back(Values[RightIndex]);
         }
      }
   }
   // return results
   Times = resultBuf.Time;
   Values = resultBuf.Value;
}

double Interpolate(const double LeftVal, const double RightVal, const double TimeLeft, const double TimeRight, const double RequiredTime)
{
   return (LeftVal + (RequiredTime - TimeLeft) * (RightVal - LeftVal) / (TimeRight - TimeLeft));
}

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

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

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 16:19 
Заслуженный участник


20/08/14
5589
Россия, Москва
Я похожее делал по другому: брал первые две точки точно, далее для каждой проверял условие попадает ли интерполяция по реально закодированным значениям предыдущих точек в заданные границы и если попадает, то сжимал, если нет, то писал точное значение. Ну и цикл до конца массива точек.
Точность тоже не идеальна, но мне поточный алгоритм был удобнее.

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 16:24 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
Я правильно понимаю, что нужно выбрать набор точек такой, чтобы точки между двумя выбранными лежали близко к соединяющему эти две выбранные точки отрезку?
Если да - это вроде делается несложной динамикой (найти минимальное число опорных точек, достаточных для покрытия первых $k$ точек).

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 16:38 
Заслуженный участник


20/08/14
5589
Россия, Москва
Ещё вариант: фиксировать первую точку точно, потом идти по массиву точек и проверять что все промежуточные (назад от текущей до ближайшей точной) укладываются в ошибку. Как только обнаружим что не укладываются - пишем предыдущую точку точно (а до неё все укладываются в ошибку) и повторяем цикл поиска следующей точки. Последнюю точку тоже пишем точно.
Процесс можно запустить с двух сторон, и с начала и с конца, до момента встречи.
Это уже совсем близко к оптимуму.

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 16:42 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
На последовательности скажем $(0, 0), (1, 1), (2, 0), (3, 1)$ и требовании к погрешности "не больше $\frac{3}{4}$" ваш алгоритм возьмет все точки, хотя достаточно взять первую и последнюю.

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 16:45 


29/03/18
4
Dmitriy40 в сообщении #1300371 писал(а):
Ещё вариант: фиксировать первую точку точно, потом идти по массиву точек и проверять что все промежуточные (назад от текущей до ближайшей точной) укладываются в ошибку. Как только обнаружим что не укладываются - пишем предыдущую точку точно (а до неё все укладываются в ошибку) и повторяем цикл поиска следующей точки. Последнюю точку тоже пишем точно.
Процесс можно запустить с двух сторон, и с начала и с конца, до момента встречи.
Это уже совсем близко к оптимуму.

Спасибо за идеи, нужно реализовать и потестировать эффективность.

-- 29.03.2018, 15:49 --

mihaild в сообщении #1300370 писал(а):
Я правильно понимаю, что нужно выбрать набор точек такой, чтобы точки между двумя выбранными лежали близко к соединяющему эти две выбранные точки отрезку?
Если да - это вроде делается несложной динамикой (найти минимальное число опорных точек, достаточных для покрытия первых $k$ точек).

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

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 16:57 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
Динамическое программирование

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 17:37 
Заслуженный участник


20/08/14
5589
Россия, Москва
mihaild
Хороший контрпример, спасибо. Да, всё так. Но и для динамического программирования можно подобрать плохой пример. Альтернативой с гарантированным оптимальным результатом вижу лишь полный перебор всех вариантов разбиений отрезка на подотрезки и минимизация количества разбиений. Если не ошибаюсь это уже NP полная задача.

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 17:53 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
Dmitriy40 в сообщении #1300383 писал(а):
Но и для динамического программирования можно подобрать плохой пример

Если я нигде не обсчитался, то можно за что-то типа $O(N^3)$ находить гарантированно оптимальное (по числу отрезков) решение.
(скорее всего можно и быстрее, но я за две минуты не придумал)

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 17:57 


29/03/18
4
mihaild в сообщении #1300385 писал(а):
Dmitriy40 в сообщении #1300383 писал(а):
Но и для динамического программирования можно подобрать плохой пример

Если я нигде не обсчитался, то можно за что-то типа $O(N^3)$ находить гарантированно оптимальное (по числу отрезков) решение.
(скорее всего можно и быстрее, но я за две минуты не придумал)

Можете подробнее описать Вашу идею?)

 Профиль  
                  
 
 Re: Сжатие набора данных методом линейной интерполяции
Сообщение29.03.2018, 18:02 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
Отсортируем точки по абсциссе.
Пусть $f(k)$ - оптимальное число отрезков, покрывающих первые $k$ точек, причем $k$-я точка является концом последнего из этих отрезков. Как вычислить $f(k + 1)$, зная $f(1), f(2), \ldots, f(k)$?
(подсказка: сделав некоторые предварительные вычисления для всех точек, занимающие суммарно $O(N^2)$ времени, можно этот переход научиться делать за $O(k)$)
Как, зная все $f(k)$, найти ответ на задачу? (вот здесь мне $N^2$ не хватает, нужно $N^3$, но сильно сомневаюсь, что это правда необходимо)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



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

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


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

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